Том 11. Карты метро и нейронные сети. Теория графов - [10]
* * *
Подобно раскраске граней геометрического графа можно говорить о раскраске его ребер или вершин.
Раскраска вершин 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», сбор мусора и уборка улиц в крупных городах, производственные цепочки, системы распределения продукции — для всех этих задач требовались методы, позволявшие найти оптимальное решение. Исследование операций достигло своего расцвета, а теория графов вызвала интерес, который не угасает и поныне. В этой главе мы приглашаем читателя оценить возможности этой теории для решения практических задач оптимизации.
В связном графе эйлеровым циклом называется путь, содержащий все ребра графа, начальная и конечная вершины которого совпадают. При этом вершины могут повторяться, а ребра — нет.
На первом из следующих рисунков вы можете видеть эйлеров цикл. Во втором графе эйлерова цикла не существует.
