?

Log in

No account? Create an account

Entries by category: история

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

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

Напомню:
Число Рамсея 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_aa
Так уж случилось, что самым интересным для меня разделом математики является теория графов. А касательно теории графов - числа Рамсея. Существует общее формальное определение чисел Рамсея, но приводить его я не вижу смысла, так как эти числа настолько сложны для вычисления, что даже для самого простого случая найдено их не так много. Итак, определим число Рамсея в простейшем случае:

Число Рамсея 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. Практического применения чисел Рамсея нет, но в процессе их поиска было разработано масса полезного инструментария как в теории графов, так и в смежных областях.