О красках, графах и карте Англии

Не секрет, что многие математические задачи возникли в самых настоящих жизненных ситуациях и изначально являлись просто формальным способом описания проблемы. Так, в 1852 году известный математик того времени Френсис Гутри составлял карту графств Англии и обнаружил, что для такой раскраски карты, чтобы любые соседние графства были разных цветов, достаточно использовать всего четыре краски. Это наблюдение заинтересовало математическое общество Лондона, и были предприняты попытки доказать, что любую карту можно раскрасить таким образом всего в четыре цвета. Однако время шло, а привести доказательство или контрпример так и не удавалось. Тогда математики решили добавить пятый цвет – с этим утверждением мы с вами уже можем работать!

Как уже было сказано, математическая задача – это формализованная проблема. Нашим первым шагом на пути к формализации Проблемы пяти красок станет представление любой карты в виде математического объекта – плоского или, как говорят, планарного графа. Каждую область карты обозначим вершиной и соединим две вершины ребрами, если соответствующие области имеют общий участок границы. Так как карта – плоская, полученный нами граф также будет плоским, то есть его можно будет изобразить на листе бумаги без пересечения ребер. Проблема пяти красок превратилась в задачу раскраски вершин графа таким образом, чтобы соединенные ребрами вершины были разного цвета:

Итак, теперь, когда мы работаем с математическими объектами, настало время для математических методов и формул! В этот раз для доказательства мы используем индукцию по числу вершин графа. Базой индукции будем считать тот факт, что если число вершин графа меньше шести, то их все можно просто раскрасить в разные цвета.

Основное же утверждение, которое нам предстоит доказать, звучит так: если все планарные графы с V вершинами можно «правильно» покрасить в 5 цветов, то и граф G из V+1 вершины может быть «правильно» покрашен в пять цветов. Для этого мы воспользуемся следствием из знаменитой формулы Эйлера для планарных графов (попробуйте вывести его сами!): в любом планарном графе найдется вершина степени меньше шести. Найдем такую вершину в нашем графе – назовем ее u. Граф G без этой вершины G\{u} имеет только V вершин – его точно можно раскрасить «правильно». Теперь у нас возможны два варианта. Первый заключается в том, что мы может сразу покрасить u в подходящий цвет – если ее степень меньше пяти или среди пяти соединенных с u вершин встречаются не все пять цветов. Второй вариант сложнее: допустим, пять соседей u имеют различный цвет. Рассмотрим этот вариант подробнее.

Здесь нам придется ввести достаточно много дополнительных обозначений. Для начала, пронумеруем соседние с u вершины по часовой стрелке: назовем их v₁, v₂, v₃, v₄, v₅. И еще: обозначим Н_ij такой подграф нашего исходного графа, что в него входят те и только те вершины, цвет которых совпадает с вершинами v_i и v_j. Вот как это будет выглядеть:

Выберем две НЕ-соседние вершины из соседей u – например, вторую и четвертую. Придется опять рассмотреть два случая: первый – они лежат в разных связных частях графа Н₂₄, и второй – в одной связной части. Для графа G с предыдущей картинки справедлив первый вариант. В этом случае (и для любого графа) мы можем поменять местами цвета, например, в той связной части Н₂₄, где находится вторая вершина – раскраска не будет нарушена, и мы сможем покрасить u в цвет второй вершины:

Второй случай можно продемонстрировать, выбрав, например, третью и пятую из вершин-соседей. Здесь нужно действовать чуть-чуть иначе. Добавим к графу Н₃₅ вершину u. Так как третья и пятая вершины находятся в одной связной части, то между ними существует путь. Добавим к этому пути вершину u – получим двухцветный цикл, причем одна из вершин v₄ и v₂ окажется внутри, а другая снаружи – ведь мы обозначали их по часовой стрелке. Так как граф – плоский, внутренняя и внешняя части цикла окажутся несвязанными, и мы гарантированно можем рассмотреть первый случай для второй и четвертой вершин.

Итак, мы рассмотрели все возможные случаи и для каждого из них нашли способ «правильно» перекрасить наш исходный граф. Теорема о пяти красках доказана! Но что же стало с теоремой о четырех красках? Оказалось, она действительно справедлива, но доказать ее удалось только в 1976 году. Это была первая крупная математическая теорема, доказанная при помощи компьютера – пришлось свести все возможные карты к 1936 шаблонам, для каждого из которых свойства доказывались отдельно. С тех пор доказательство было усовершенствовано, но проверить его вручную по-прежнему невозможно.