Клауди Альсина - Том 11. Карты метро и нейронные сети. Теория графов

* * *

ЭЛЕГАНТНЫЕ ПЛОСКИЕ ГРАФЫ

Не следует думать, что ребра плоского графа должны иметь какую-то причудливую форму. Любой плоский граф можно изобразить так, что его ребра будут отрезками и эти отрезки будут пересекаться только в вершинах графа. Сложно представить что-то более элегантное.

* * *

Задача звучит так: в трех домах а, Ь, с живут три семьи, враждующие между собой. Рядом с их домами находятся три колодца е, f, g . Один из колодцев всегда полон, два других пусты. Соседи хотят проложить дорожки так, чтобы из каждого дома можно было попасть к каждому колодцу. Никакие две дорожки не должны пересекаться, чтобы каждый мог избежать встреч с соседями. Можно ли проложить девять дорожек таким способом?

На рисунке слева показана первая попытка соединить дома а, Ь, с и колодцы е, f, g . Такой граф обозначается К 3,3 . Получилось множество нежелательных пересечений. На рисунке справа тот же граф изображен иначе, но избежать пересечений по-прежнему не удалось. Заметим, что если убрать дорожку от дома Ь к колодцу g , то можно проложить восемь дорожек без пересечений, как показано на двух следующих рисунках.

Можно ли добавить к этому графу недостающее ребро так, чтобы не пересекать остальные? Будет уместно привести одно интуитивно понятное утверждение (любопытно, что доказать его непросто): если простая плоская замкнутая непрерывная кривая делит плоскость на две части (внешнюю и внутреннюю), то любая непрерывная кривая, соединяющая точку внешней части и точку внутренней части, пересечет данную кривую минимум один раз. Это утверждение носит название теоремы Жордана. Посмотрим снова на рисунок выше и увидим, что в обоих случаях точка g находится внутри непрерывной замкнутой кривой, а точка Ь — вне ее.

Следовательно, задача о колодцах не имеет решения. Единственный способ, которым можно проложить дорожку из дома Ь к колодцу g — это построить мост, проходящий поверх одной из дорожек.

В задаче о колодцах представлен первый пример непланарного графа. Граф, который мы обозначили К 3,3 , не является планарным. Еще один простой пример непланарного графа — это полный граф К 5 в форме пятиугольника с пятиугольной звездой внутри, изображенный на рисунке:

Дальше все будет только усложняться. Графы К 3,3 и К 5 не являются планарными, и если мы добавим к ним еще несколько ребер и вершин, то полученные графы также не будут планарными — этому будут мешать излишние пересечения ребер. Таким образом, можно привести бесконечно много примеров непланарных графов. Благодаря теореме, открытой Куратовским, нас ожидает приятный сюрприз. Заметим, что два графа называются гомеоморфными, если после удаления всех вершин степени 2 полученные графы будут идентичными или изоморфными. Теорема Куратовского звучит так:

«Граф является планарным тогда и только тогда, когда он не содержит ни одного подграфа, гомеоморфного К 3,3 или К 5 ».

Чтобы определить, является ли граф планарным, нужно удалить все вершины степени 2 и проверить, не содержит ли полученный граф К 3,3 или К 5.

* * *

КАЗИМИР КУРАТОВСКИЙ (1896–1980)

Профессор Куратовский был одним из великих польских математиков, возглавлял группы исследователей и сотрудничал с крупнейшими математиками мира. Он занимался логикой, топологией, теорией множеств, а в 1930 году удивил весь мир знаменитой теоремой о планарных графах. Хотя определить планарность графа на практике сложно, теорема Куратовского имеет очень простую формулировку.

ПРИМЕНЕНИЕ В АРХИТЕКТУРЕ

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