Сколько нужно красок?

Кандидат технических наук Евгений Гик.

Ещё в середине XIX века была высказана гипотеза, что для раскрашивания произвольной географической карты, на которой любые соседние страны должны быть окрашены в разные цвета, достаточно четырёх красок. Но только спустя столетие, в 1976 году, американские математики К. Аппель и В. Хейкен с помощью компьютера доказали эту старинную гипотезу, превратив её в теорему. На рис. 1 шесть стран окрашены именно в четыре цвета (внешняя область — тоже страна) и соседние страны имеют разные цвета.

Рис. 1.
Рис.2.
Рис. 3.
Рис. 4.
Рис. 5.
Рис. 6.

Очевидно, любой карте можно поставить в соответствие граф, вершины которого отвечают странам, а если две страны имеют общую границу, то вершины соединяются ребром. При этом рёбра не пересекаются между собой — такой граф называется плоским. На рис. 2 изображена карта с семью странами (внешняя область — страна), на рис. 3 — соответствующий ей граф с семью вершинами.

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

Головоломка. Двое играют в следующую игру. На первом ходу один игрок ставит вершину, другой её раскрашивает. Далее на каждом ходу первый ставит новую вершину, и либо она остаётся изолированной, либо он соединяет её рёбрами с ранее поставленными вершинами; при этом рёбра не должны пересекаться (граф плоский); второй игрок раскрашивает эту вершину и т.д. Какого количества красок достаточно иметь второму игроку, чтобы в возникающем графе любые две вершины, соединённые ребром, были раскрашены в разные цвета?

Решение. После знакомства с задачей о четырёх красках ответ будет весьма неожиданный — не хватит никакого числа красок! Другими словами, первый игрок может действовать таким образом, что второму придётся использовать всё новые и новые краски, и так до бесконечности. Простая и довольно изящная «победная» стратегия показана на рис. 4. (Краски, как обычно, обозначаются цифрами; если требуется новая краска, она получает очередной номер).

Первый игрок ставит вершину, а второй обозначает её цифрой 1 (рис. 4.1) — первая краска. Теперь первый игрок ставит изолированную вершину (она также окрашена в краску 1) и добавляет новую вершину, соединяя её с 1; второй игрок, естественно, ставит 2 (рис. 4.2). Для наглядности рис. 4.2 расположим под рис. 4.1 так, чтобы вершина 2 оказалась под 1.

Ближайшими ходами первый игрок дублирует рис. 4.1 и 4.2 (на рис. 4.3 этот фрагмент обведён пунктиром), затем опять ставит новую вершину и соединяет её с 1 и 2, вынуждая второго поставить на ней 3. Рис. 4.3 расположим под рис. 4.1, 4.2, чтобы вершина 3 оказалась под 1 и 2. Далее первый игрок опять дублирует всю предыдущую игру (рис. 4.4, пунктиром), а новую вершину соединяет с 1, 2 и 3, второй игрок должен поставить на ней 4, рис. 4.4 расположим под рис. 4.1, 4.2, 4.3 и т. д.

Осталось убедиться, что при такой стратегии первого игрока второму не хватит никакого числа красок. Предположим противное: пусть ему достаточно определённого числа k красок. Тогда в какой-то момент получаем рис. 5 пунктиром, причём вершина k расположена под k-1. Теперь первый игрок ставит новую вершину и соединяет её с 1, 2, 3 … k (остальные части графа изображены на рисунке схематически). В результате второй игрок вынужден использовать (k+1)-тую краску. Противоречие!

Но как же быть с гипотезой в задаче о четырёх красках? Всё дело в том, что если в графе, возникающем в процессе игры, стереть все краски, то его легко перекрасить, ограничившись четырьмя красками. Например, граф на рис. 4.3 можно раскрасить в две краски (рис. 6), а не в три. Гипотеза верна для любого графа или географической карты, которые ещё не раскрашены. Но если вершины (страны) раскрашивать в процессе построения графа (карты), как в нашем случае, то, как мы видим, никаких красок не хватит!

Другие статьи из рубрики «Математические досуги»

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