Все знают о задаче о четырех красках, но — до определенного предела. Позвольте пролить немного больше света.
Итак, речь идет о раскраске карты, на которой нарисованы страны/области/регионы, которые и надо окрасить в разные цвета так, чтобы соседние страны были окрашены в разные цвета. Соседними считаются страны, имеющие общую границу любой ненулевой протяженности: одна общая точка не считается границей. Кроме стран, могут быть и моря или океаны, их тоже надо как-то красить.
Можно обозначить страны точками, а отношение соседства — линией, соединяющей две точки. Получится граф; но не тот, который титул (Монте-Кристо), а математический объект. Граф определяется так: это пара (V,E), причем V — конечное множество, а E — подмножество декартова произведения V на себя. Проще говоря, V — набор вершин, чем бы они не были, а E — подмножество множества всевозможных пар вершин. Их называют ребрами графа. А вершины, соединенные ребром, называют смежными.
Мы здесь предполагаем, что вершина не может быть смежна сама себе (для карт это очевидно: страна не может граничить сама с собой). Иногда графы с петлями рассматриваются, но не в этой задаче. Ещё мы предполагаем, что граф неориентированный (это надо оговорить), то есть пара вершин входит в любом порядке: если соединены ребром, то это взаимно.
В задаче важно, что граф планарный. Планарным называют граф, вершины которого можно нарисовать на плоскости так, что ребра не будут пересекаться. Плоский граф уже нарисован на плоскости таким образом. И задача звучит так: вершинам планарного графа надо приписать цвета так, что смежные вершины имеют разные цвета. И надо доказать, что четырех цветов точно хватит.
Казалось бы, а полный граф? В полном графе все вершины смежные. Но... если вершин достаточно много (больше четырех), то ребра непременно пересекутся...
То, что может не хватить трех цветов, показывает контрпример. Он приведен на рисунке, и в виде графа, и в виде карты. Хотя для многих карт трех цветов и довольно. А вот проверить, хватит ли трех цветов для данного графа — сложная (NP-полная) задача.
То, что пяти цветов точно хватит, нетрудно доказать. Прежде всего, установим, что в плоском графе есть вершина, из которой выходит меньше шести ребер. Можете попробовать, и увидите: нарисовать граф, из каждой вершины которого выходит более пяти ребер, можно, но ребра непременно будут пересекаться. Доказательство дам в отдельной заметке, оно любопытное.
На языке карт оно звучит так: всегда есть страна, у которой менее шести соседей.
Это само по себе любопытно, тем более что соседом считаем и море, например.
Теперь заметим, что для графа из пяти и менее вершин окраска пятью цветами проблемы не представляет. И применим индукцию, предположив, что для n вершин теорема верна (пяти цветов хватит) и докажем утверждение для графов из n+1 вершины.
Отыщем вершину А, из которой исходит менее шести ребер. Удалив ее вместе с ребрами, получим граф из n вершин, который можно раскрасить пятью красками по индуктивному предположению.
На языке карт, удалив одну страну (оставив ее белой), мы можем раскрасить карту пятью красками.
Если смежные с А вершины окрашены в четыре цвета или менее, то саму вершину А покрасим в свободный цвет, и дело с концом.
То есть, если пять соседей страны А покрашены в четыре цвета (например, синий-зеленый-синий-красный), то страну А покрасим в пятый.
Остается случай, когда все пять смежных с А вершин покрашены в пять разных цветов. Можно расположить их по порядку и пронумеровать цвета от 1 до 5. Рассмотрим граф G(1,3), состоящий только из вершин, покрашенных в цвета 1 и 3. Может оказаться так, что вершины 1 и 3 лежат в разных компонентах связности, то есть пройти по ребрам графа G(1,3) из вершины 1 в вершину 3 нельзя. Тогда можно поменять местами цвета 1 и 3 в той компоненте, которая содержит вершину 1. Теперь вершины 1 и 3 покрашены обе в цвет 3 без нарушения правил, и вершину А можно покрасить в цвет 1.
На языке карт получается, что у страны есть пять соседей, покрашенные в пять цветов; мы выделяем только те страны, что покрашены в цвета 1 и 3, и рассматриваем случай, когда из страны-1 в страну-3 не проехать по странам, покрашенным только в эти два цвета. Тогда можно поменять местами раскраску тех стран, которые покрашены в цвета 1 и 3 и в которые можно проехать таким образом из страны 1.
Как частный частый случай, просто страна-1 и страна-3 не граничат между собой и страна-1 не граничит с цветом номер 3. Тогда ее можно перекрасить в цвет номер 3, освободив цвет номер 1 для страны А.
Если граф G(1,3) связен, то попробуем граф G(2,4). Если тоже не получится, то пути из 1 в 3 в G(1,3) и из 2 в 4 в G(2,4) непременно пересекаются, что несложно установить. Это противоречит планарности графа.
На языке карт получается запутанно. Если проехать из синей страны-соседки в коричневую по синим и коричневым странам можно, то проехать из зеленой соседки в красную по зеленым и красным, не заезжая в синие и коричневые, невозможно. Для графов это довольно наглядно, а для карт — нет.
Впрочем... если мы можем проехать из синей страны в коричневую, объехав красную, то проехать из красной в зеленую, обогнув коричневую, явно не получится, если не пересекать первый путь. См. рисунок.
Доказательство завершено.
Мы видим, что черную вершину мы вообще не использовали. И кажется, что повторить доказательство для четырех цветов тоже удастся.
Но нет.
Теорема доказана, то есть утверждение верно: всегда можно раскрасить карту четырьмя цветами. Доказательство основано на проверке нескольких сотен (более тысячи) графов-карт, к которым непременно должен сводиться любой контрпример. То, что любой граф, для которого не хватит четырех красок, содержит один из этих подграфов, доказать удалось. А их проверил компьютер.
Получилась странная ситуация: доказательство есть, но "необозримо": полторы тысячи карт проверить вручную очень сложно.
Теорема верна для бесконечных графов (если на плоскости много-много стран), верна на сфере и на цилиндре. На торе нужно семь цветов. И вообще, есть удивительная общая формула, выражающая хроматическое число (оно самое) замкнутых поверхностей через эйлерову характеристику χ:
p = [7+√(49-24χ)/2]
Квадратные скобочки означают взятие целой части, если число дробное.
Для сферы x=2 и p=4, для тора x=0 и p=7, а Бутылка Клейна исключение: для нее х=0, но p=6.
Практический вывод: что карту, что глобус можно раскрасить в четыре цвета; если для морей приберечь синий цвет, то сушу можно раскрасить в три других цвета, как бы страны не дробились, сливались и не перекраивали границы.
В этом смысле можно спать спокойно.
