Любую расположенную на плоскости карту можно раскрасить пятью красками так, чтобы две области, имеющие общий участок границы, были раскрашены в разные цвета. Эта теорема была доказана Перси Джоном Хивудом в 1890 году.
Очевидно, что задача раскраски карты сводится к поиску максимального хроматического числа планарного графа. «Гипотезу о том, что любой планарный граф можно раскрасить четырьмя красками, сформулировал в 1879 году английский математик Кели, а доказательство этой гипотезы было получено в 1976 году Хейкеном и Аппелем» [1, c. 166]. Однако большая часть доказательства была проведена авторами с помощью компьютера, что не удовлетворило многих математиков. Классического доказательства теоремы о четырех красках не существует.
Рассмотрим для примера некоторую карту и выберем любую область A. Обозначим эту область – вершиной нулевого уровня. Вершинами уровня N будут области, граничащие с территорией, охватываемой уровнем N-1.
Из данного определения следует, что:
- Каждая вершина уровня N (при N>0) соединена хотя бы с одной вершиной уровня N-1.
- Вершина уровня N может быть соединена только с вершинами уровней N, N-1 и N+1
Если вершина V уровня N соединяется с вершиной уровня N-K (при K>1), то, исходя из определения, вершину V необходимо поставить на уровень N-1. Если вершина V уровня N соединяется с вершиной V’ уровня N+K (при K>1), то, исходя из определения, вершину V’ необходимо поставить на уровень N+1.
На рисунке 1 вершиной нулевого уровня выбрана область A, вершинами первого уровня – B, C, D, E и F, вершинами второго уровня – другие окрашенные области.
Рисунок 1. Представление вершин разного уровня
Расположим вершины графа на параллельных прямых линиях, которые соответствуют уровню вершины. Некоторые вершины можно «разбить» на несколько составляющих точно так же, как можно разделить область на карте. Полученный граф представлен на рисунке 2. Количество ребер графа не изменилось.
Рисунок 2. Графическое представление графа
Общая карта в итоге будет представлять собой подграф графа R, который является бесконечной сетью «треугольников».
Для окраски полученного графа, можно воспользоваться следующим алгоритмом:
- При движении от вершины к вершине по самому низкому уровню используем попеременно две краски (красный-зеленый)
- Если возникнет ситуация, когда невозможно покрасить последнюю вершину, потому что она противоречит поставленной задачи (например, нечетное количество стран «замыкающих круг»), то используем третью краску
- На следующем уровне используем другую пару красок (синий – желтый), проверяя условие задачи на связях уровня и на связях уровня ниже (связи с уровнем выше мы не учитываем, так как движемся снизу-вверх)
- Продвигаемся вверх до нулевого уровня
На третьем этапе алгоритм может прерваться в том случае, если вершина V, которую необходимо закрасить уже соединена с вершинами всех четырех красок. Чтобы определить цвет вершины V необходимо найти множество вершин цвета C соседних с V, которые можно раскрасить в другой цвет, а вершину V окрасить в цвет C. В итоге замена цвета такой вершины будет представлять собой конечную рекурсивную функцию. Максимальная глубина рекурсии будет равна N-K, где K – уровень вершины V, N – всего количество уровней.
В поисках вершины, которая может изменить цвет, функция будет двигаться от верхнего уровня к нижнему. И самой последней возможной итерацией будет проверка вершины низшего уровня.
Надо сказать, что на низшем уровне вершины при окраске опираются только на заданную пару цветов и на связи с вершинами своего уровня. Следовательно, будет использовано максимум три цвета.
Предположим, что это не так и области A, B, C и D лежат на самом низком уровне и окрашены в разные цвета. Поскольку при окраске низшего уровня мы опирались на связь вершин в пределах лишь этого уровня, то стоит предположить, что все четыре области граничат между собой. Плюс ко всему все они граничат с областью охватываемой уровнем выше. Эту область мы можем обозначить за вершину E. Итого у нас получается полный граф, состоящий из пяти вершин A, B, C, D и E. Но по теореме Понтрягина – Куратовского: «Граф является планарным тогда и только тогда, когда он не содержит подграфов, изоморфных K3,3 и K5» [2, стр.34]. А значит на карте его отобразить не получится.
Приведенный алгоритм не является поиском хроматического числа планарного графа. В отличие от известных алгоритмов (алгоритм А.П.Ершова, алгоритм оптимальной раскраски) предложенный вариант не преследует цели минимизации цветов для раскраски. Мы сразу используем четыре цвета для планарного графа, даже в том случае, когда достаточно всего трех или двух цветов.
Список литературы:
- Асанов М.О. Дискретная математика: графы, матроиды, алгоритмы: Учебное пособие. 2-е изд., ипср. и доп. СПб.: Лань, 2010. – 368 с.
- Бояринцева Т.И. Теория графов: метод. указания. М.: Изд-во МГТУ им. Н.Э. Баумана, 2014. – 37 с.
- Харари Ф. [Harary F.] Теория графов. М.: Мир, 1973. – 300 с.[schema type=»book» name=»ЭВРИСТИЧЕСКИЙ АЛГОРИТМ 4-РАСКРАСКИ ГРАФА» author=»Сорокин Георгий Владимирович» publisher=»БАСАРАНОВИЧ ЕКАТЕРИНА» pubdate=»2017-04-22″ edition=»ЕВРАЗИЙСКИЙ СОЮЗ УЧЕНЫХ_ 28.03.2015_03(12)» ebook=»yes» ]