Рис. 18. Дерево как часть графа (выделено жирными линиями):
а — дерево; б — остов (покрывающее дерево).
Деревья играют важную роль в различных прикладных задачах, когда, например, речь идет о связи каких-либо объектов минимальным числом каналов (линий связи, дорог, коммуникаций) с определенными свойствами. С помощью дерева определяется система координат при моделировании цепей и систем различной физической природы. Деревья используются в качестве моделей при рассмотрении иерархических систем объектов, структурных формул органических соединений и т. п.
13. Планарность. Граф называют плоским (планарным), если существует изоморфный ему граф (геометрическая реализация), который может быть изображен на плоскости без пересечения ребер. Например, хотя в одном из графов на Рис. 10 ребра пересекаются, изоморфные ему не имеют пересечений, следовательно, он плоский.
На Рис. 19 показаны два неплоских графа, играющие фундаментальную роль в теории планарности и называемые графами Понтрягина - Куратовского. Полный пятиугольник (Рис. 19,а) представляет собой простой неплоский графе минимальным числом вершин (полный графе четырьмя вершинами - плоский, а удаление из пятиугольника хотя бы одного ребра также превращает его в плоский граф). Двудольный граф (Рис. 19, б) является моделью известной задачи о трех домах и трех колодцах: можно ли проложить от домов к каждому колодцу дороги так, чтобы они не пересекались (враждующие соседи должны иметь возможность пользоваться всеми колодцами, но не хотят встречаться на дорогах).
- 57 -
Рис. 19. Графы Понтрягина - Куратовского:
а - полный пятиугольник; б — двудольный граф.
Свойства планарности не нарушаются, если некоторое ребро разбить на два введением новой вершины второй степени или заменить два ребра, инцидентные вершине второй степени, одним ребром, удалив эту вершину. Два графа называют гомеоморфными (изоморфными с точностью до вершин второй степени), если после удаления из них вершин второй степени и объединения инцидентных этим вершинам ребер, они оказываются изоморфными (Рис. 20). Очевидно, граф, гомеоморфный плоскому графу, также плоский.
Строго доказывается, что граф является плоским тогда и только тогда, когда он не содержит подграфа, гомеоморфного одному из графов Понтрягина - Куратовского.
Рис. 20. Гомеоморфные графы.
Планарность является существенным свойством графов, которые моделируют коммуникации и связи между объектами на плоскости (дороги между населенными пунктами, водопроводные и газопроводные сети, линии передач электроэнергии, межсоединения на печатных платах электронных устройств и кристаллах интегральных схем). Плоскими графами представляются различные карты, с которыми, в частности, связана известная проблема четырех красок: всегда ли можно раскрасить области, на которые плоский граф делит поверхность, так, чтобы никакие две смежные области не были окрашены в одинаковый цвет и чтобы при этом было использовано не более четырех цветов? Доказано, что для такой раскраски в любом случае достаточно пяти красок, но никто еще не привел примера, когда пять красок действительно необходимы. Проблема остается нерешенной, несмотря на огромные усилия многих выдающихся математиков, которые штурмуют ее более столетия.
14. Графы и отношения.Пусть на множестве Х задано бинарное отношение А. Ему соответствует ориентированный граф, вершины которого отображают элементы из X, а дуга (хi, xj), где (хi, xj ∈ X), существует тогда и только тогда, когда(хiАxj). Обратно, множество ориентированных дуг графа (без строго параллельных дуг), заданных упорядоченными парами (хi, xj), можно рассматривать как бинарное отношение на множестве X.
Если бинарное отношение хАy устанавливает связь между элементами х из множества Х и элементами у из множества Y (х ∈ X, у ∈ У), то граф такого отношения будет ориентированным биграфом.
Следует заметить, что в общем случае орграф представляет нечто большее, чем бинарное отношение. Любое бинарное отношение, определенное на некотором множестве, можно представить соответствующим орграфом, вершины которого соответствуют элементам этого множества. Однако орграф с параллельными дугами позволяет отражать более общие связи между объектами, чем бинарные отношения.
- 58 -
Задачи и упражнения
1. Какие части города (см. рис. 7) нужно соединить мостами, чтобы задача о кенигсбергских мостах имела положительное решение? Достаточно ли для этого одного дополнительного моста?