Карты метро и нейронные сети. Теория графов
Шрифт:
На рисунке слева показана первая попытка соединить дома а, Ь, с и колодцы е, f, g. Такой граф обозначается К3,3. Получилось множество нежелательных пересечений. На рисунке справа тот же граф изображен иначе, но избежать пересечений по-прежнему не удалось. Заметим, что если убрать дорожку от дома Ь к колодцу g, то можно проложить восемь дорожек без пересечений, как показано на двух следующих рисунках.
Можно ли добавить к этому графу недостающее ребро так, чтобы не пересекать остальные? Будет уместно привести одно интуитивно понятное утверждение (любопытно, что доказать его непросто): если простая плоская замкнутая непрерывная кривая делит плоскость на две части (внешнюю и внутреннюю), то любая непрерывная кривая, соединяющая точку внешней части и точку внутренней части, пересечет данную кривую минимум один раз. Это утверждение носит название теоремы Жордана. Посмотрим снова на рисунок выше и увидим, что в обоих случаях точка g находится внутри непрерывной замкнутой кривой, а точка Ь — вне ее.
Следовательно, задача о колодцах не имеет решения. Единственный способ, которым можно проложить дорожку из дома Ь к колодцу g — это построить мост, проходящий поверх одной из дорожек.
В задаче о колодцах представлен первый пример непланарного графа. Граф, который мы обозначили К3,3, не является планарным. Еще один простой пример непланарного графа — это полный граф К5 в форме пятиугольника с пятиугольной звездой внутри, изображенный на рисунке:
Дальше все будет только усложняться. Графы К3,3 и К5 не являются планарными, и если мы добавим к ним еще несколько ребер и вершин, то полученные графы также не будут планарными — этому будут мешать излишние пересечения ребер. Таким образом, можно привести бесконечно много примеров непланарных графов. Благодаря теореме, открытой Куратовским, нас ожидает приятный сюрприз. Заметим, что два графа называются гомеоморфными, если после удаления всех вершин степени 2 полученные графы будут идентичными или изоморфными. Теорема Куратовского звучит так:
«Граф является планарным тогда и только тогда, когда он не содержит ни одного подграфа, гомеоморфного К3,3 или К5».
Чтобы определить, является ли граф планарным, нужно удалить все вершины степени 2 и проверить, не содержит ли полученный граф К3,3 или К5.
* * *
КАЗИМИР КУРАТОВСКИЙ (1896–1980)
Профессор Куратовский был одним из великих польских математиков, возглавлял группы исследователей и сотрудничал с крупнейшими математиками мира. Он занимался логикой, топологией, теорией множеств, а в 1930 году удивил весь мир знаменитой теоремой о планарных графах. Хотя определить планарность графа на практике сложно, теорема Куратовского имеет очень простую формулировку.
ПРИМЕНЕНИЕ В АРХИТЕКТУРЕ
При работе над архитектурными проектами интерес представляет анализ графа доступности пространств. Если этот граф не является планарным, нужно будет построить несколько этажей и лестниц. Если же полученный граф является планарным, то допустимо расположение всех нужных помещений на одном этаже.
* * *
Дерево — это очень простой граф, все вершины которого соединены так, что отсутствуют циклы, как, например, на следующем рисунке:
В дереве можно проложить маршрут между любыми двумя вершинами.
Далее приведены все возможные деревья с числом вершин от 1 до 8.
Последовательность чисел, обозначающих количество всех возможных деревьев для каждого числа вершин, выглядит так: 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159…
Если дерево имеет р вершин, то в нем всегда будет р — 1 ребер, но для каждого значения р можно изобразить рр– 2 разных деревьев (формула Кэли). Понятие дерева впервые ввел Кэли в 1857 году. Деревья образуют очень важный класс графов, так как в них все вершины соединены минимально возможным числом ребер. Благодаря этому деревья находят интересное применение в самых разных областях: при проектировании электрических цепей, телефонных сетей, при поиске маршрутов между населенными пунктами и так далее.
Следующая простая и красивая теорема дает характеристику деревьям, а также имеет крайне важное практическое значение:
«Граф G является деревом тогда и только тогда, когда между любыми двумя различными его вершинами u и v существует единственный путь. Это равносильно следующему утверждению: С является связным графом, если он имеет р вершин и р — 1 ребро».
Несмотря на простоту этой теоремы, число возможных деревьев по мере увеличения р возрастает очень быстро.
Причина этому такова. Пусть G — дерево. Даны две вершины G, u и v. Так как граф G является связным, то существует по меньшей мере один путь между u и v. Если бы между этими вершинами существовало два пути, С1 и С2, то в графе G образовался бы цикл, что невозможно. Разумеется, если между двумя произвольными вершинами графа существует единственный путь, граф является связным и не содержит циклов.
* * *
ДЕРЕВЬЯ И ВЕРОЯТНОСТИ
При анализе вероятностей различных событий (например, в играх) возможные альтернативные исходы и соответствующие вероятности часто представляют в форме дерева, где вершины соответствуют возможным исходам, а ребра — значениям вероятностей возможных исходов. Соответствующие расчеты выполняются на основе дерева. На рисунке представлено дерево, соответствующее игре, в которой нужно бросить сначала монету, затем — кубик. В теории игр, которая широко применяется в экономике, подобные представления используют очень часто.