Дискретная математика:
логика, группы, графы, фракталы

Акимов О.Е.

3.5. Раскраска графов и вопросы топологии

Формула для минимального числа цветов

Приведем формулу, позволяющую определить максимальное число вершин планарного графа, который можно было бы вычертить на топологической поверхности с наперед заданной величиной связанности, или, другими словами, минимальное число цветов, которое потребуется для раскраски любой политической карты, нанесенной на этой топологической поверхности. Задача мини-максимума решается через отношение равенства; если задача формулируется как максимум, то пользуются отношением меньше, если задача формулируется как минимум — отношением больше. Мы будем пользоваться равенством. Искомое число обозначим через x, напомним также, что под n понимается число вершин, m — число ребер, f — число граней и σ — значение связанности, которое удовлетворяет модернизированной формуле Эйлера. Значение x будем находить при помощи формулы Эйлера и условия Хивуда, выдвинутого им еще в 1890 г. Сейчас оно имеет несколько различных представлений; нам удобно представить его в виде

.

Если в последнее равенство подставить формулу Эйлера, получим

x² – 7x = 6(σ – 3).

Решим квадратное уравнение и отбросим один из корней, который дает с точки зрения топологии неинтерпретируемое значение:

.

Данная формула и является решением поставленной задачи мини-максимума. Целые значения x, обозначаемые как [x], позволяют найти минимальное число красок для раскраски вершин планарного графа, вычерченного на σ-связанной топологической поверхности, или максимальное число вершин для полного графа, который можно вычертить на σ-связанной поверхности так, чтобы его ребра не пересекались. В табл. 3.43 приведены значения x и [x], найденные по расчетной формуле, в зависимости от связанности σ.

Таблица 3.43

σ	x	[x]	σ	x	[x]	σ	x	[x]
1	4,000	4	6	9,000	9	11	11,264	11
2	6,000	6	7	9,522	9	12	11,640	11
3	7,000	7	8	10,000	10	13	12,000	12
4	7,775	7	9	10,447	10	14	12,346	12
5	8,425	8	10	10,866	10	15	12,679	12

Следует обратить внимание на то, что при значениях связанности меньше 10 и 11 имеет место неравенство: σ < [x]; после указанных значений ситуация меняется на противоположную: σ > [x]. Расчетная формула для x, зависящая от связанности σ, пригодна для всех топологических поверхностей, какие бы формы они ни принимали. Еще в XIX в. было доказано, что все они приводимы к одному из неприводимых поверхностей типа шара, тора и ряда кренделей с нарастающим числом отверстий и дырок (рис. 3.75 и рис. 3.76). Часто вместо связанности σ говорят о роде поверхности ρ, который на единицу меньше связанности, в результате чего расчетная формула изменится:

Как видно из табл. 3.43, формула для x прекрасно работает для всех значений связанности. Однако при получении условия Хивуда, из которого выведена окончательная расчетная формула, топологи наложили ограничение на первые два значения связанности, т.е. σ не может принимать значения, равные 1 и 2, что и повлекло за собой проблемы с доказательством равенства x = 4 для σ = 1, осуществленное Аппелем и Хейкеном с помощью компьютерного перебора около двух тысяч неприводимых конфигураций. В мире существует немало авторитетных математиков, которые не признают компьютерные «подгонки» в духе Аппеля и Хейкена в качестве полноценного математического доказательства. Но сторонники конструктивного подхода вряд ли с ними согласятся. Если традиционный формально-логический аппарат не был задействован, это еще не значит, что альтернативный подход ошибочен.