Карты метро и нейронные сети. Теория графов

Любопытно, что если карту можно раскрасить двумя цветами, то все вершины соответствующего графа будут иметь четную степень. Если в нем будет хотя бы одна вершина с нечетной степенью, то как минимум одна грань графа будет граничить с двумя гранями и для раскраски понадобится уже три цвета. Чтобы доказать обратное утверждение, нужно выполнить несколько действий. Сначала докажем, что если мы проведем на плоскости n линий случайным образом, то полученную карту можно будет раскрасить всего двумя красками (вспомните, например, шахматную доску).

Используем метод доказательства по индукции, который заключается в том, что мы докажем это утверждение для n = 1 и посмотрим, будет ли верным это утверждение для n + 1, если оно верно для n.

При n = 1 (а) доказательство тривиально. Допустим, что это утверждение верно для n прямых (b), и рассмотрим карту, на которой изображена n + 1 прямая (с). Если мы удалим одну из линий, то получим карту из n прямых, которую можно раскрасить двумя цветами (верно по индукции). Следовательно, при добавлении (n + 1)-й прямой вверху (или справа) от добавленной прямой все цвета останутся без изменений, а с другой стороны от этой прямой все области изменят цвет на противоположный. Таким образом, карту из n + 1 прямой можно раскрасить всего двумя красками. С учетом соответствующих различий можно заметить, что любую карту из n окружностей, случайным образом распределенных на плоскости, также можно раскрасить двумя красками. И в случае с прямыми, и в случае с окружностями все вершины полученного графа будут иметь четную степень. В любом графе, вершины которого имеют четную степень, б'oльшую двух, при удалении цикла получится граф, вершины которого по-прежнему будут иметь четную степень. Как и все графы такого типа, его можно будет представить в виде прямых или окружностей. Теорема о двух красках доказана.

Применительно к задачам раскраски во многих случаях интерес представляют только графы, степень каждой вершины которых не превышает 3. Если одна из вершин графа имеет степень больше 3, то можно провести окружность С с центром в этой вершине, которая не будет касаться никакой другой вершины, затем удалить элементы графа внутри этой окружности и получить новый граф с вершинами степени 3, соответствующими пересечениям С и исходных ребер. Если мы раскрасим полученную карту, а затем удалим построенную окружность и вернемся к исходному графу, то задача будет решена, как показано на следующих рисунках. Таким образом, в задачах о раскраске графов иногда можно рассматривать только плоские графы, каждая вершина которых имеет степень 3.

Доказательство теоремы о трех красках сложнее, чем предыдущей, поэтому мы не будем приводить его здесь. Сама теорема звучит так:

«Плоский граф с вершинами степени 3 можно раскрасить тремя красками тогда и только тогда, когда все его грани ограничены четным числом ребер».

* * *

ОХРАННИКИ В МУЗЕЯХ И РАСКРАСКА ГРАФОВ

В 1973 году, анализируя задачу о расположении охранников в залах музея, Виктор Клее задался вопросом: если музей имеет форму многоугольника с n сторонами, какое количество охранников необходимо для того, чтобы они могли просматривать все стены, не двигаясь с места? На первом рисунке изображен выпуклый многоугольник, который легко просматривается одним охранником, стоящим в углу. Однако в случае с невыпуклым многоугольником, изображенным на следующем рисунке, одного охранника уже недостаточно. Ответ задачи таков: для многоугольника с n сторонами достаточно [n/3] охранников. (Знак [] обозначает целую часть отделения, то есть результат деления с отброшенными десятичными знаками.)

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

* * *

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

Четырех цветов достаточно

В 1852 году Френсис Гутри, изучая различные карты, предположил, что их можно раскрасить в четыре цвета так, чтобы страны с общими границами имели разные цвета. В то время Френсис уже завершил обучение в университете, поэтому он обратился к своему брату Фредерику, который изучал математику у известного преподавателя Огастеса де Моргана. Де Морган не смог дать ответ и познакомил с задачей своих коллег, среди которых был сэр Уильям Гамильтон. В 1878 году

Математики Френсис Гутри (слева), который предположил, что любую карту можно раскрасить в четыре цвета, и Артур Кэли, который представил эту задачу Лондонскому математическому обществу.

Артур Кэли представил формальное изложение этой задачи на всеобщее рассмотрение в Лондонском математическом обществе.

В 1879 году была опубликована статья, в которой доказывалось, что четырех цветов достаточно. Автором остроумного доказательства был лондонский адвокат Альфред Кемпе. С 1879 по 1890 год (одиннадцать лет!) его решение считалось верным, а задача о четырех красках — решенной.

В 1890 году Перси Хивуд удивил всех, обнаружив неустранимую ошибку в доказательстве Кемпе. Требовалось найти новое доказательство. Сам Хивуд и многие другие математики потратили немало времен и сил, пытаясь решить эту задачу. Никому не удавалось найти карту, для раскраски которой требовалось бы пять красок. Поэтому было логичным предположить, что четырех красок должно быть достаточно для любой карты. Как часто бывает в математике, неудачные попытки решить одну задачу позволили получить результаты, применимые в других областях (геометрии, топологии, комбинаторике).

Любопытно, что было найдено решение этой задачи для карт, расположенных на поверхностях неправильной формы. Например, для тора (геометрического тела в форме бублика) нужно семь красок, для ленты Мёбиуса (чтобы изготовить ее, нужно склеить края вытянутого прямоугольника, предварительно развернув один из них) — шесть цветов. Также было найдено верное доказательство того, что для любой карты достаточно пяти цветов; были обнаружены характерные свойства карт, для раскраски которых достаточно всего двух или трех красок. Однако доказательство гипотезы о четырех красках (для карты на плоскости или на поверхности сферы) попрежнему не было найдено. Его пришлось ждать очень долго.

* * *

ДЕНЕШ КЁНИГ(1884–1944)

Венгерский математик Денеш Кёниг получил образование в Будапеште и Гёттингене. Именно в Гёттингене он прослушал доклад Минковского о проблеме четырех красок, который произвел на него большое впечатление. Кёниг решил посвятить себя изучению и преподаванию теории графов. В 1936 году он написал книгу, которая чрезвычайно способствовала росту популярности теории графов во всем мире. В отличие от множества других задач, решить проблему четырех красок ему так и не удалось.

* * *

В 1950-е годы было показано, что четырьмя красками можно раскрасить любые карты, на которых изображено не более чем 38 стран. Немецкий математик Генрих Хееш, следуя путем Кемпе, понял, что в решении задачи помогут новые возможности, предлагаемые компьютерами. Для них рассмотрение любой карты сводилось к перебору различных вариантов.

С 1970 по 1976 год математики Кеннет Аппель и Вольфганг Хакен из Иллинойского университета в Урбана-Шампейн с помощью компьютера путем перебора многих тысяч вариантов окончательно доказали: «Четырех цветов достаточно».