Карты метро и нейронные сети. Теория графов
Шрифт:
Это событие приобрело такую важность, что Почтовая служба США выпустила марку с этой фразой. Доказательство Аппеля и Хакена позднее было уточнено, но никому до сих пор не удалось избежать перебора множества вариантов, то есть найти доказательство, для которого не требовалось бы применение компьютера. Использование информационных технологий в математических доказательствах (не только при решении проблемы четырех красок) привело к появлению принципиально новой парадигмы по сравнению с классическими математическими доказательствами. В 1997 году Робертсон, Сандерс, Сеймур и Томас привели обновленное доказательство, в котором сочетались классические представления и новые компьютерные алгоритмы. Тем не менее «классическое» доказательство до сих пор не найдено.
Кеннет
Позднее появились новые задачи о раскраске карт. Так, Герберт Тейлор предложил обобщить проблему четырех красок следующим образом: сколько красок необходимо, чтобы раскрасить карту, в которой все страны и территории состоят из m несвязных частей, причем все территории одной страны должны быть окрашены одним цветом, а регионы одного цвета не должны иметь общей границы? При m = 1 мы возвращаемся к исходной проблеме четырех красок. В 1980 году Хивуд доказал, что для m = 2 необходимо 12 цветов. Тейлор доказал, что для m = 3 требуется 18 цветов, для m = 4 — 24 цвета. Для m >= 5 существует гипотеза, согласно которой искомым числом будет 6m, но на сегодняшний день доказательств этому не найдено. Различные задачи о раскраске карт сегодня составляют отдельный раздел теории графов, который по-прежнему притягивает интерес ученых.
* * *
БЕСКОНЕЧНОЕ ЧИСЛО ЦВЕТОВ В ПРОСТРАНСТВЕ
Если вместо плоских карт мы будем рассматривать геометрические тела в пространстве, которые нужно раскрасить так, чтобы тела с общими гранями были окрашены в разные цвета, нас ждет большой сюрприз. В этом случае потребуется не четыре и не шесть, а бесконечное количество цветов, что показано на рисунках К. Алсины и Р. Нельсена, выполненных в 2006 году.
ЗАДАЧА ПОЛА ЭРДЁША
Какое минимальное число красок необходимо, чтобы раскрасить плоскость так, чтобы любые две точки, расстояние между которыми равно единице, находились бы на областях разного цвета? Лео Мозер подтвердил, что для этого необходимо четыре краски. Но достаточно ли?
* * *
Подобно раскраске граней геометрического графа можно говорить о раскраске его ребер или вершин.
Раскраска вершин V(С) графа G множеством цветов С состоит в присвоении каждой вершине графа цвета из множества С таким образом, что смежные вершины будут окрашены в разные цвета. Хроматическое число X(G) графа G определяется так: это минимальное количество цветов, в которое можно раскрасить вершины графа С так, чтобы любые смежные вершины имели разные цвета.
Если С имеет как минимум одно ребро, то X(G) будет больше либо равно 2. Очевидно, что X(G) не может быть больше числа вершин V (граничным случаем будет раскраска каждой вершины в свой цвет). Разумеется, хроматическое число является инвариантом, так как полностью эквивалентные (изоморфные) графы имеют одинаковое хроматическое число.
Рассмотрим следующие графы:
Если n вершин графа расположены в одну линию, его хроматическое число равно 2, так как для его раскраски будет достаточно чередовать цвета. Это же справедливо и для любого дерева. Если же все вершины графа образуют цикл и число вершин четно, то хроматическое число такого графа равно 2. Если же число вершин нечетно, то хроматическое число равно 3. И наконец, если граф является колесом (граф с n вершинами, (n — 1) — я вершина которого принадлежит простому циклу, а одна вершина вне этого цикла смежна со всеми остальными), то его хроматическое число равно 3, если
внешний цикл состоит из четного числа вершин. Если же это число нечетное, хроматическое число будет равно 4.Используя принцип двойственности, можно переходить от одного типа графов к другому так, что цвета граней одного графа станут цветами вершин другого. Интересно, что вместо цветов можно использовать лингвистические категории или атрибуты. В этом случае группы вершин одного цвета или категории образуют классификацию. Это происходит при формировании списков.
При раскраске вершин графа обычно используется строгий алгоритм: вершины нумеруются по порядку, первой вершине в списке присваивается первый цвет, затем цвет присваивается второй вершине (если она смежна первой, цвет меняется, если нет, используется прежний цвет) и так далее. Однако следует проявлять осторожность: результатом работы этого алгоритма не всегда будет хроматическое число.
Следовательно, чтобы найти минимально возможное число цветов, результат этого алгоритма понадобится пересмотреть.
На следующих рисунках изображен граф, соответствующий кубу, который с помощью вышеописанного алгоритма был раскрашен в четыре цвета. Однако существует красивое решение, позволяющее раскрасить этот же граф всего двумя красками.
По сути, вышеописанный алгоритм гарантирует лишь то, что число различных цветов не будет превышать максимальную степень вершин графа плюс один. Поиск эффективных алгоритмов раскраски графа — нетривиальная задача.
В этой главе мы рассказали о том, что часто происходит в математике: задача, которая изначально кажется лишь игрой, создает основу для серьезных исследований.
* * *
ЦВЕТА, ГРАФЫ И СТИХОТВОРЕНИЯ
Иногда поэтическое вдохновение и красота стихотворения оказываются перечеркнуты последующими событиями. Именно это произошло с английским поэтом Дж. Линдоном: он, удивленный стремлением многих людей доказать, что четырех цветов достаточно для раскраски любого графа, написал такие строки:
В четыре краски красят математики,
Стремясь найти решение задачи.
Они меняют области местами
Но неизменно терпят неудачу.
Со временем эти стихи потеряли смысл: ученые потратили много сил и времени, но решили задачу о четырех красках.
Глава 3
Графы, циклы и оптимизация
Я верю, что наша нация может взять на себя обязательство достичь поставленной цели — высадить человека на поверхности Луны и благополучно вернуть его на Землю в этом десятилетии.
Джон Ф. Кеннеди, 25 мая 1961 года
Господи, теперь нам действительно нужно это сделать.
Роберт Фрейтаг (NASA)
Вторая половина XX века ознаменовалась не только стремительным развитием теории графов, но и началом ее широкого применения в задачах планирования и оптимизации. Развитию теории графов способствовал технический прогресс и расцвет информатики и вычислительной техники, но никогда прежде не проводилось столь обширного исследования методов и алгоритмов поиска решений, оптимальных по времени или денежным затратам. Масштабная программа NASA по запуску ракеты «Аполлон-2», сбор мусора и уборка улиц в крупных городах, производственные цепочки, системы распределения продукции — для всех этих задач требовались методы, позволявшие найти оптимальное решение. Исследование операций достигло своего расцвета, а теория графов вызвала интерес, который не угасает и поныне. В этой главе мы приглашаем читателя оценить возможности этой теории для решения практических задач оптимизации.
В связном графе эйлеровым циклом называется путь, содержащий все ребра графа, начальная и конечная вершины которого совпадают. При этом вершины могут повторяться, а ребра — нет.
На первом из следующих рисунков вы можете видеть эйлеров цикл. Во втором графе эйлерова цикла не существует.
Эйлер с точностью определил, когда в связном графе существует эйлеров цикл. Для этого он использовал понятие степени вершины, равное числу ребер, исходящих из данной вершины. Критерий существования эйлерова цикла выражен теоремой, которая звучит так: