Портал создан при поддержке Федерального агентства по печати и массовым коммуникациям.

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

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

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

Рис. 1.
Рис. 1.
Рис.2.
Рис.2.
Рис. 3.
Рис. 3.
Рис. 4.
Рис. 4.
Рис. 5.
Рис. 5.
Рис. 6.
Рис. 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), а не в три. Гипотеза верна для любого графа или географической карты, которые ещё не раскрашены. Но если вершины (страны) раскрашивать в процессе построения графа (карты), как в нашем случае, то, как мы видим, никаких красок не хватит!


Случайная статья


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