Category: история

Category was added automatically. Read all entries about "история".

Поиск циркулярных предрамсеевских графов


В этом посте я хочу привести некоторые красно-синие реберные раскраски полных графов, связанные с числами Рамсея.

Напомню:
Число Рамсея R(r, b) - это наименьшее натуральное число n такое, что при любой красно-синей реберной раскраске полного графа порядка n, в нем найдется красная клика порядка r, либо синяя клика порядка b.

Рассмотрим числа Рамсея для 3 ≤ r ≤ 5, 3 ≤ b ≤ 5. Известно, что R(3, 3) = 6, R(3, 4) = 9, R(3, 5) = 14, R(4, 4) = 18, R(4, 5) = 25, 43 ≤ R(5, 5) ≤ 49.

Меня интересуют полные графы порядка меньше R(r, b) с красно-синей реберной раскраской, которые не содержат ни красных клик порядка r, ни синих клик порядка b. Если порядок такого графа равен R(r, b) - 1, то я называю этот граф предрамсеевским.

Интересно существование предрамсеевских графов в классе циркулярных графов (точнее циркулярными являются графы, содержащие только красные и только синии ребра рассматриваемого графа), так как такие графы обладают определенной простотой, симметрией и наглядностью.

В результате перебора всех циркулярных графов для чисел R(3, 3), R(3, 4), R(3, 5), R(4, 4), R(4, 5) в этом классе оказался предрамсеевский граф. Ниже они приведены:

Collapse )

R(4, 4). Шаг 2: определение точной окрестности вершины.

В продолжение о числе Рамсея R(4, 4) (http://r-aa.livejournal.com/22283.html).

Снова возникает вопрос, сколько вообще существует реберных раскрасок полного графа с R(4, 4) - 1 = 17 вершинами в красный и синий цвета, таких что в графе не найдется полного подграфа одного цвета с 4-мя вершинами. Как обычно, интересуют только разные раскраски с точностью до изоморфизма.

Простой перебор на компьютере тут уже помочь не может, так как количество раскрасок слишком велико: 2 ^ 136. Однако искомые раскраски обладают множеством свойств, позволяющих существенно сузить круг поиска. В этом сообщении я хочу остановиться только на поиске таких свойств.

Как и ранее, красное ребро в полном графе соответствует наличию ребра в нераскрашенном графе, а синее - его отсутствию. Дальше я буду пользоваться обеими абстракциями, не останавливаясь на этом.

Рассмотрим несколько свойств искомого графа:

I. Для любой вершины v графа deg_r(v) = deg_b(v) = 8.

Допустим обратное, тогда без ограничения общности можно считать, что deg_r(v) >= 9 для какой-то вершины. Тогда в ее окрестности найдется либо полный синий подграф с 4-мя вершинами, либо красный треугольник (http://r-aa.livejournal.com/18990.html), что сразу приводит к полному красному подграфу с 4-мя вершинами. Противоречие.

II. Количество ребер в искомом графе равно 68.

Прямо следует из предыдущего пункта.

III. Общая форма окрестности любой вершины.

Фиксируем произвольную вершину в графе. Она соединена с 8 вершинами красными ребрами и с 8 вершинами синими ребрами. Таким образом можно говорить о красной и синей окрестности вершины. В красной окрестности вершины нет красных треугольников и полных синих подграфов с 4-мя вершинами. Структура такого 8-вершинного графа описана в сообщении http://r-aa.livejournal.com/18990.html при рассмотрении R(3, 4). Аналогично определяется структура синей окрестности.

IV. Точная форма окрестности любой вершины.

В предыдущем пункте определена общая форма окрестности вершины V. Однако, этого не достаточно, так как в окрестности вершины остаются ребра, цвет которых мы не можем определить. Чтобы определить цвет этих ребер, нужно сделать еще одно усилие.

Рассмотрим красную окрестность вершины V. В этой окрестности есть вершины двух типов: a - лежащая на зеленой диагонали (то есть она может лежать на синей диагонали) и b - лежащая на красной диагонали.

Если вершина лежит на синей диагонали, то ее собственная красная окрестность включает в себя вершину V, две вершины из красной окрестности V и 5 вершин из синей окрестности V. Если вершина лежит на красной диагонали, то ее собственная красная окрестность включает в себя вершину V, три вершины из красной окрестности V и 4 вершин из синей окрестности V.
Значит для любой вершины из красной окрестности вершины V мы можем определить количество вершин из синей окрестности вершины V, с которыми она соединена красными ребрами. Существуют три возможных варианта: оба зеленых ребра из красной окрестности вершины V являются синими, только одно и оба являются красными. Рассмотрим их:

1) Оба зеленых ребра из красной окрестности точки V - синие.

Подсчитаем количество красных ребер в графе: (>= 16) (синяя окрестность вершины V) + 8 (ребра вершины V) + 10 (красная окрестность вершины V) + 2 * 2 * 5 (красные ребра между окрестностями) + 2 * 2 * 4 (красные ребра между окрестностями).
Итого >= 70, но в графе всего 68 красных ребер. Противоречие.

2) Одно зеленое ребро из красной окрестности вершины V синее, а другое красное.

Количество красных ребер в графе >= 16 + 8 + 11 + 1 * 2 * 5 + 3 * 2 * 4 = 69 > 68. Противоречие.

3) Оба зеленых ребра из красной окрестности точки V - красные.

Количество красных ребер в графе >= 16 + 8 + 12 + 4 * 2 * 4 = 68 = 68.

Значит вариант 3) - единственный возможный. В заключение можно проиллюстрировать точный вид окрестности точки с красными и синими ребрами.



Таким образом, остается определить расположение ребер между окрестностями разных цветов. Об этом позже.

R(4, 4). Шаг 1

Нахождения этого числа Рамсея - элементарная процедура.

По теореме Рамсея R(r, b) <= R(r - 1, b) + R(r, b - 1), тогда R(4, 4) <= 2 * R(3, 4) = 18.

Существует же раскраска полного графа с 17 вершинами, такая, что в графе не найдется ни полного красного подграфа с 4 вершинами, ни полного синего подграфа с 4 вершинами.



Таким образом R(4, 4) = 18.

Вопрос же о том, бывают ли другие (не изоморфные данному) такие графы, гораздо более сложный. Я оставлю его на какое-то время. Напишу только, что этот вопрос можно пытаться прояснить аналитически, так как искомый граф обладает массой свойств (регулярный, гамильтонов, возможно автоморфный), к тому же для него фиксирована окрестность любой вершины. Но об этом позже.

Задачка о цапле

Пусть дан связный ненаправленный невзвешенный граф в узком смысле (то есть без петель и кратных ребер). В нем выделены две вершины: A и B.

Пойдем по порядку.

I. Найти кратчайший путь, соединяющий данные вершины.

Это просто задача обхода графа в ширину, начиная с одной из выделенных вершин. Алгоритм линеен по числу ребер и вершин.

II. Найти кратчайший ЧЕТНЫЙ путь, соединяющий данные вершины.

Для этой задачи также есть простое решение. Сначала для каждой вершины v (будем ее называть также v0) создадим копию v1. После этого каждому ребру (u, v) сопоставим два ребра (u0, v1) и (u1, v0). На рисунке ниже ребра исходного графа изображены черным цветом, а построенные новые ребра - серым. После этого найдем кратчайший путь из A0 в B0. Соответствующий ему путь в исходном графе удовлетворяет требованиям задачи. Алгоритм также линеен по числу ребер и вершин.

III. Найти кратчайший ПРОСТОЙ ЧЕТНЫЙ путь, соединяющий данные вершины.

А вот тут уже все сложнее. Пока у меня есть некоторые наметки, но до конца еще не довел.

P.S.
Цапля тут при том, что в исходной задаче по кочкам ходила цапля и она должна была на кочку B прийти той же лапой, что стояла на кочке A.

R(3, 5)

В продолжение разговора о числах Рамсея R(3, 3) и R(3, 4) пришло время рассмотреть число R(3, 5).

Сначала установим само значение числа. Рассмотрим полный граф с ребрами, раскрашенными в красный и синий цвета. Пусть количество вершин графа равно N. Тогда по определению красной и синей степеней вершины для любой вершины v выполнено равенство deg_r(v) + deg_b(v) = N - 1.

Предположим, что в графе нет красных треугольников и полных синих подграфов с пятью вершинами.
Для любой вершины графа выполняются два неравенства:

deg_r(v) < R(2, 5) = 5
deg_b(v) < R(3, 4) = 9

откуда

N - 10 < deg_r(v) < 5

Данное неравенство невыполнимо при N >= 14. То есть R(3, 5) >= 14.
Нетрудно найти граф, имеющий 13 вершин, в котором нет красных треугольников и синих подграфов с пятью вершинами, то есть R(3, 5) = 14. Интереснее найти все такие графы. Для этого нужно запускать полный перебор по всем графам из 13 вершин, в которых красная степень каждой вершины равна 4. Я перебирал графы, которые можно представить в виде объединения двух гамильтоновых циклов (есть предположение, что среди других графов нет нужных). Все найденные графы оказались изоморфными. Таким образом существует только одна раскраска полного графа с 13 вершинами (которую можно представить в виде объединения двух красных гамильтоновых циклов), в котором нет красных треугольников и полных синих подграфов с пятью вершинами.

Вот эта раскраска.

R(3, 3)

 R(3, 3) = 6

Про это я уже писал в посте http://r-aa.livejournal.com/13819.html.

Тут интересно другое - сколько существует раскрасок полного графа из 5 вершин таких, что в графе не окажется ни красных, ни синих треугольников.

Определение:
Красной степенью вершины (deg_r(v)) назовем количество инцидентных ей красных ребер, аналогочно вводится синяя степень (deg_b(v)).

Итак, получим все возможные раскраски. Пусть есть полный граф с 5 вершинами. В нем нет красных и синих треугольников. Из доказательства для R(3, 3) = 6 следует, что красная и синяя степень любой вершины равна 2. Здесь и далее я иногда буду опускать синие ребра (соответственно полный синий подграф будет заменяться на вполне несвязный подграф). Итак, красная степень всех вершин равна двум. Удалим все синие ребра. Очевидно, что граф останется связным. Также нетрудно видеть, что связный регулярный граф степени 2 гамильтонов. То есть простой цикл из красных ребер и есть единственно возможная раскраска.

Числа Рамсея

Так уж случилось, что самым интересным для меня разделом математики является теория графов. А касательно теории графов - числа Рамсея. Существует общее формальное определение чисел Рамсея, но приводить его я не вижу смысла, так как эти числа настолько сложны для вычисления, что даже для самого простого случая найдено их не так много. Итак, определим число Рамсея в простейшем случае:

Число Рамсея R(k, m) это наименьшее число n такое, что в любом графе с n вершинами, найдутся либо k попарно смежных, либо m попарно несмежных.

Теорема Рамсея гарантирует существование чисел Рамсея для любых k и m. Таким образом можно говорить о содержании в бесконечном графе высокоорганизованной структуры любой сложности. Но об этом позже (быть может). А пока хочется остановиться на числах Рамсея. Для удобства перефразируем определение:

Число Рамсея R(k, m) это наименьшее число n такое, что в любом полном графе с n вершинами, ребра которого раскрашены в красный и синий цвета, найдется либо подграф с k вершинами, все ребра которого окрашены в красный цвет, либо подграф с m вершинами, все ребра которого окрашены в синий цвет.

Чтобы понять сложность вычисления чисел Рамсея, то следует отметить что число R(5, 5) до сих пор не найдено.

Можно заметить три очевидных факта, касающихся чисел Рамсея:

1. R(k, m) = R(m, k)
2. R(1, m) = 1
3. R(2, m) = m

Остальные числа вычисляются индивидуально.

Задача о вычислении R(3, 3) известна как "задача о вечеринке": среди любых 6 человек найдется либо 3 попарно знакомых, либо 3 попарно незнакомых. Другими словами R(3, 3) <= 6. Доказательство строится следующим образом (в терминах второго приведенного определения):

Изобразим граф с шестью вершинами и возьмем одну из них - A:

Вершина A соединена с пятью другими вершинами (красными и синими ребрами). Без ограничения общности можно считать, что она соединена красными ребрами по крайней мере с тремя вершинами - B, C, D. Далее, если одно из ребер BC, CD, BD красное (например BC), то имеем красный треугольник (ABC). Если же все они синие, то BCD - синий треугольник. Конец доказательства.

Имея в виду то, что число 5 не удовлетворяет требованиям задачи, получаем R(3, 3) = 6.

Дальше докажем, что R(3, 4) = 9. Сначала установим, что R(3, 4) > 8. Для этого достаточно привести пример раскраски графа из 8 вершин, не содержащего красных треугольников и полных синих подграфов из 4 вершин:



Осталось доказать, что полный граф из 9 вершин так раскрасить нельзя. Допустим, такая раскраска возможна. Будем рассуждать как в предыдущем доказательстве. Возьмем одну из вершин (A), с остальными вершинами она соединена 8 ребрами. Пусть k из них покрашены в красный цвет, а остальные 8-k - в синий.
Если k >= R(2, 4) = 4, то A соединена красными ребрами хотя бы с четырьмя вершинами (B, C, D, E). Если две из этих вершин соединены красным ребром, то сразу имеем красный треугольник, а если нет, то BCDE - полный синий граф из четырех вершин. Значит k < 4.
Аналогичным образом 8-k < R(3, 3) = 6.
Из этих двух неравенств имеем (k < 4) && (k > 2) => k = 3.
Так как наши рассуждения не зависят от выбора вершины, то можно утверждать, что из любой вершины выходит ровно три красных ребра, а значит общее число красных ребер в графе равно 3 * 9 / 2. Но это число не является целым, мы пришли к противоречию. Следовательно требуемой раскраски не существует и R(3, 4) = 9. Конец доказательства.

P.S. Данное доказательство пока не слишком сложное, но все же сложнее вычисления R(3, 3). Для больших параметров доказательства значительно усложняются. Дело в том, что не существует системного метода поиска чисел Рамсея (есть только грубые оценки), а с ростом параметров начинается очень обширное комбинаторное многообразие, не позволяющее найти решение даже компьютеру...

P.P.S. Практического применения чисел Рамсея нет, но в процессе их поиска было разработано масса полезного инструментария как в теории графов, так и в смежных областях.

Код Прюфера

Продолжу тему хранения деревьев. Для кодирования структуры дерева можно использовать код Прюфера. Код является оптимальным по объему. Суть состоит в следующем:

Пусть дано дерево с n вершинами, которые пронумерованы числами от 1 до n. Код Прюфера является массивом из n-2 элементов, каждый из которых есть номер одной из вершин (номера могут повторяться). По данному коду дерево восстанавливается однозначным образом.

Алгоритм кодирования:
V = [1, ... , n] - номера вершин дерева.
P = [ ] - массив с кодом, пока пустой.
Для i от 1 до n-2 выполняем последовательность шагов:
1. Выбираем из дерева висячую вершину с минимальным номером - vi.
2. Находим вершину wi - смежную с vi.
3. Присваиваем P[i] = wi.
4. Удаляем из дерева вершину vi.

Восстановление дерева труда не составляет.

Ниже приведен пример дерева и его код Прюфера (1, 5, 2, 6, 1, 6, 6, 3).


P.S. Кроме самого практического использования код Прюфера ценен тем, что из него прямо следуют теорема Кэли, а именно, что у полного графа с n вершинами количество пронумерованных остовов равно n^(n-2).

Питер Дарман, "Униформа Второй мировой"

Попалась мне тут книга под названием "Униформа Второй мировой" за авторством некоего Питера Дармана. Откуда этот автор родом, узнать мне не удалось, но в информации о других книгах мелькали какие-то издательства Нью-Йорка, так что вполне возможно, что он американец. В книге много картинок различных видов униформ всех стран по очереди. Есть грамотная форма:



Есть странная форма:
 

Вроде бы довольно обычное описание всяких ремней, подсумков, нашивок, воротников. Однако как же не нагадить при случае на СССР? Первой страной, описанной в книге является Германия, представляет ее автор так:
 
«Германские солдаты относились к числу наиболее профессиональных и стойких бойцов Второй мировой войны...»
 
Много видов униформы, действительно грамотной и продуманной. Только под Сталинградом форма подкачала, но в этом виноваты русские, потому что не предупредили, что в России зимой холодно. После Германии идут остальные страны, видимо, в порядке значимости их участия в войне. США:
 
«Америка оказала решающий вклад в победу союзников во Второй мировой войне, предоставив для этого колоссальные материально-технические ресурсы. Американские военные были, как правило, прекрасно экипированы обмундированием, оружием и снаряжением...»
 
Великобритания:
 
«Британские военнослужащие вступили в войну в 1939 г., имея оружие и снаряжение, разработанные до или во время Первой мировой войны, ожидая, что новый военный конфликт окажется похожим на тот, который случился четверть века тому назад. Несмотря на поражение 1940-1941 гг. боевой дух британского "Томми" (как в народе издавна называли солдат британской армии) остался прежним: неудержимым в атаке и стойким в обороне.»
 
Англичане были настолько неудержимы в атаке, что почти год после объявления войны Германии вообще ничего не делали. Ну да ладно. Дальше идет Италия:
 
«Участие Италии во Второй мировой войне закончилось бесславным поражением... Однако здесь следует учитывать, что они не были заинтересованы в этой войне, участвовали в ней против своей воли...»
 
Любимая песня. Но здесь не об этом. От итальянцев по значимости отстает Япония:
 
«...Японские солдаты отличались фанатической храбростью и неприхотлиивостью. Но в войне техники, каковой была Вторая мировая война, для того чтобы сокрушить экономическую мощь Соединенных Штатов, одного фанатизма было недостаточно.»
 
Что это он про экономическую мощь начал, наверное действительно американец. После Японии идет Советский Союз:
 
«Важнейшим отличительным признаком Красной Армии были массированные атаки пехоты, крупных сил танков и авиации, перемалывание немцев. Средний "Иван" был похож на свое вооружение: простое и неприхотливое...»

И представлена фотография типичного "Ивана" на фоне гармони и со стаканом, все как полагается:

 
Вот так и получается у Дармана: немцы стойкие, англичание неудержимые, японцы храбрые, а "Иваны" простые и с гармошками. После Советского Союза идут разные франции, венгрии, австралии, но это уже не интересно. Описание советской формы построено в основном по принципу "вот шапка, вот штаны, а еще Сталин плохой". Ниже еще несколько цитат о военной форме Советского Союза:
 
«...советские солдаты в большинстве носили обмундирование, разработанное еще в начале века.»
 
Заметим, что у англичан форма разработана «до или во время Первой мировой войны», а у нас «в начале века». По сути одно и то же, но акценты совсем разные.
 
«Типичным для так называемого "равенства" в Красной Армии был тот факт, что офицеры носили шапки из натурального меха, а солдаты и сержанты - из искусственного.»
 
Не хватало на всех натурального меха, дальше что? А немцы бумагой утеплялись. Не до жиру, что было, то и носили.
 
«В начале войны с Германией Красная Армия находилась в сильно ослабленном состоянии. Сталин на протяжении нескольких лет проводил свои безумные чистки... Первым результатом явилась крайне неудачная зимняя война против Финляндии... Однако эти потери не идут ни в какое сравнение с трагедией первых нескольких недель операции "Барбаросса". И никакие новые уставы и формы одежды не могли быстро ликвидировать тот ущерб, который советский диктатор нанес своей армии.»
 
Еще одна любимая песня западных авторов - безумные чистки. Сейчас я пост допишу и тоже устрою безумную чистку дома - выкину весь мусор. Вообще это совсем другая тема, которой нужно уделять огромное количество времени, но Дарман не упустит возможность об этом сказать в книжке про униформу.
 
«Типичный солдат Красной Армии вел тоскливую, трудную жизнь. Он был лишен почти всякого комфорта, имел скудный рацион и, особенно перед войной, нестандартную амуницию. Тот факт, что он, вероятно, жил все же лучше, чем средний заводской рабочий или колхозник, вряд ли приносил большое утешение. Даже качество одежды у него было весьма низким. Такимим были те мужчины и женщины, силами которых Сталин рассчитывал разбить мощь нацистской Германии.»
 
Солдаты остальных стран, надо полагать, по мнению автора вели веселую, легкую жизнь. А еще, видимо, подразумевается, что Сталин рассчитывал разбить мощь нацистской Германии, но все-таки не разбил... В общем буду искать другие книги этого товарища. Все-таки скорее это американец, так как английские писатели чуть менее бессовестны в своих оценках.

Марк Солонин, "Мозгоимение! Фальшивая История Великой войны".

Это одна из книжек, купленная на недавно проходившей XXI Международной Книжной выставке-ярмарке, куда мы зашли с новоиспеченной четой Петуховых. Консультант (или как можно назвать человека, который сидит на стенде?) по поводу этой книги так прямо и сказал: "могли бы вместо ЭТОГО взять что-нибудь действительно серьезное".

В общем он оказался прав, в книжке автор обсуждает бредовые теории, заезженные опровержения, разбавляя при этом свои "рассуждения" неуместным стебом. Какое-то странное отношение к читателю выражает данный товарищ. Вроде того, что издают историки и "историки" глупые книжки, быдлочитатель все это кушает, а я, мудрый Марк Солонин, вам сейчас объясню, что можно кушать, а что нельзя, ибо уж я-то правду знаю, так как написал аж четыре монографии. В комментарии от издателя указано:

«При минимуме цифр и технических подробностей, опираясь на здравый смысл, четкую логику и неоспоримые факты, автор высмеивает неуклюжие уловки шарлатанов от истории, пытающихся заморочить людям готову преднамеренным враньем.»

«"Генеральное соглашение между НКВД и Гестапо", "тайный сталинский сценарий начала войны", "план обороны 41-го года", "сквозная транспортировка частей Красной Армии к Ла-Маншу", "секретные переговоры Сталина с Вольфом в Мценске" и многое, многое другое - вот образчики того феерического бреда, который разоблачает автор.»


В, общем прочитав книгу, я так и не понял, зачем мне понадобилось знакомиться с разоблачениями разного рода бреда, содержащими откровенную банальщину или являющиемися таким же бредом, разбавленным ерничаньем (автору самому очень нравится это слово). Очень не хочется что-нибудь цитировать из книги, но мимо одного абзаца пройти не смог. В главе, где обсуждается обеспечением Красной Армии радиосвязью, Марк Солонин решил подумать, а нужна ли она вообще:

«Для большего эффекта они еще и навязали легкомысленной публике тезис о том, что якобы отсутствовавшая радиосвязь является якобы единственным техническим средством связи. Удивительно, но публика заглотила даже этот крючок без наживки. Почему-то никто не вспомнил о том, что Наполеон, Суворов и Кутузов командовали огромными армиями не только без радиосвязи, но даже без простого проводного телефона. Почему-то все забыли о том, что превосходным средством связи может считаться сигнальный костер, сигнальная ракета, мотоцикл, автомобиль, легкомоторный самолет...»

Вот ведь. Костры надо было жечь. И всего-то.