Рис. 14.4. Граф смежности карты
Создав граф смежности карты, мы преобразовали проблему раскраски карты в проблему раскраски графа. Вместо раскрашивания стран на карте мы раскрашиваем вершины графа. Если карту (или граф) можно раскрасить n цветами, так что соседние страны (вершины) будут раскрашены в разные цвета, то мы говорим, что она допускает n-раскраску. Гипотезу четырех красок можно переформулировать следующим образом:
На рис. 14.5 показана карта Невады и ее соседей, а также соответствующий граф смежности. Мы раскрасили граф четырьмя цветами, а затем перенесли эту раскраску на исходную карту.
Рис. 14.5. Раскраска графа смежности порождает раскраску карты
На типичной карте могут встречаться страны, имеющие много соседей, но это невозможно для всех стран сразу. На любой карте найдется страна, имеющая пять или менее соседей. Этот важный факт называется теоремой о пяти соседях. Для его доказательства нужна формула Эйлера и немного арифметики. В терминах теории графов она формулируется так:
Пусть имеется простой планарный граф. Поскольку в нем нет петель и параллельных ребер, можно добавить ребра так, что каждая грань будет ограничена ровно тремя ребрами. Мы докажем, что этот (больший) триангулированный граф содержит вершину степени 5 или меньше, а потому такая вершина должна быть и в (меньшем) исходном графе. Предположим, что триангулированный граф имеет V вершин, E ребер и F граней (внешняя область считается гранью). Каждое ребро является общей границей двух граней, а каждая грань ограничена тремя ребрами, поэтому 3F = 2E. По формуле Эйлера, V — E + F = 2, или, эквивалентно, 6E — 6F = 6V — 12. Подставляя 4E вместо 6F, получаем
2E = 6V — 12.
Поскольку у каждого ребра два конца, сумма степеней всех вершин равна 2E. Поэтому средняя степень вершин равна
Так как средняя степень меньше шести, то должна существовать по меньшей мере одна вершина степени 5 или меньше.
Чтобы продемонстрировать полезность теоремы о пяти соседях в задачах раскрашивания графов, докажем теорему о шести красках.
Предположим, что это утверждение неверно. Тогда найдется одна или несколько карт, которые нельзя раскрасить шестью цветами. Найдем в этом множестве «плохих» карт карту с наименьшим числом стран. Пусть число стран на этой карте равно N. Такой наименьший контпример часто называют минимальным злодеем. Польза выделения минимального злодея в том, что можно с уверенностью сказать, что любую карту, содержащую N — 1 или меньше стран, можно раскрасить шестью цветами.
Рассмотрим граф смежности G минимального злодея. По теореме о пяти соседях, в G найдется вершина v степени 5 или меньше. После удаления v и всех инцидентных ей ребер из G получится новый граф H. Легко видеть, что H является графом смежности карты с N — 1 странами. Поскольку H содержит N — 1 вершин, его можно раскрасить шестью цветами. Теперь вернем удаленную вершину вместе с ребрами в граф. Поскольку v соседствует не более чем с 5 другими вершинами, найдется хотя бы один неиспользованный цвет, которым можно покрасить v. Таким образом, G можно раскрасить в шесть цветов. Это противоречит предположению о том, что G — минимальный злодей, а следовательно, любая карта допускает 6-раскраску. На рис. 14.6 эта техника использована для раскрашивания графа в красный, синий, зеленый, фиолетовый и оранжевый цвета.
Рис. 14.6. Раскрашивание минимального злодея шестью цветами
К сожалению, это доказательство не проходит, когда число доступных цветов равно 4 или 5. Когда придет время вставить вершину v обратно, может не оказаться свободного цвета для ее окрашивания. В этих случаях нужны более тонкие рассуждения.