Математический аппарат инженера - [21]

- 57 -

Рис. 19. Графы Понтрягина - Куратовского:

а - полный пятиугольник; б — двудольный граф.

Свойства планарности не нарушаются, если некоторое ребро разбить на два введением новой вершины второй степени или заменить два ребра, инцидентные вершине второй степени, одним ребром, удалив эту вершину. Два графа называют гомеоморфными (изоморфными с точностью до вершин второй степени), если после удаления из них вершин второй степени и объединения инцидентных этим вершинам ребер, они оказываются изоморфными (Рис. 20). Очевидно, граф, гомеоморфный плоскому графу, также плоский.

Строго доказывается, что граф является плоским тогда и только тогда, когда он не содержит подграфа, гомеоморфного одному из графов Понтрягина - Куратовского.

Рис. 20. Гомеоморфные графы.

Планарность является существенным свойством графов, которые моделируют коммуникации и связи между объектами на плоскости (дороги между населенными пунктами, водопроводные и газопроводные сети, линии передач электроэнергии, межсоединения на печатных платах электронных устройств и кристаллах интегральных схем). Плоскими графами представляются различные карты, с которыми, в частности, связана известная проблема четырех красок: всегда ли можно раскрасить области, на которые плоский граф делит поверхность, так, чтобы никакие две смежные области не были окрашены в одинаковый цвет и чтобы при этом было использовано не более четырех цветов? Доказано, что для такой раскраски в любом случае достаточно пяти красок, но никто еще не привел примера, когда пять красок действительно необходимы. Проблема остается нерешенной, несмотря на огромные усилия многих выдающихся математиков, которые штурмуют ее более столетия.

14. Графы и отношения.Пусть на множестве Х задано бинарное отношение А. Ему соответствует ориентированный граф, вершины которого отображают элементы из X, а дуга (х_i, x_j), где (х_i, x_j ∈ X), существует тогда и только тогда, когда(х_iАx_j). Обратно, множество ориентированных дуг графа (без строго параллельных дуг), заданных упорядоченными парами (х_i, x_j), можно рассматривать как бинарное отношение на множестве X.

Если бинарное отношение хАy устанавливает связь между элементами х из множества Х и элементами у из множества Y (х ∈ X, у ∈ У), то граф такого отношения будет ориентированным биграфом.

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

- 58 -

Задачи и упражнения

1. Какие части города (см. рис. 7) нужно соединить мостами, чтобы задача о кенигсбергских мостах имела положительное решение? Достаточно ли для этого одного дополнительного моста?

2. Постройте граф отношений между сотрудниками Вашего подразделения: а) x_i связан по работе с x_j; б) x_i подчинен x_j ( x_j, x_j ∈ X, где X — множество сотрудников подразделения). Охарактеризуйте полученные графы: что в них общего и чем они различаются? В каких случаях может получиться несвязный граф?

3. Постройте граф района, в котором Вы живете, отметив направления ребер для улиц с односторонним движением. Преобразуйте полученный граф в орграф. Можно ли проложить путь между любыми двумя вершинами, не нарушая установленных направлений движения и не выезжая за пределы района?

4. На графе, построенном в задаче 3, укажите (хотя бы приблизительно) расстояния между смежными вершинами. Найдите кратчайшие маршруты, соединяющие интересующие Вас вершины.

5. Существует ли эйлеров цикл для графа, построенного в задаче 3, и что он означает? Попытайтесь найти для этого графа гамильтонов цикл (если он существует).

6. Пометьте вершины и ребра графа (см. рис. 14, а) буквами или цифрами и выполните следующие упражнения:

а) Запишите все ребра как неупорядоченные пары вершин и отметьте кратные ребра и петли.

б) Определите степени всех вершин, а также суммы степеней всех вершин и всех нечетные вершин графа (что можно сказать об этих суммах?).

в) Является ли граф однородным (если нет, то добавлением ребер преобразуйте его в однородный)?

г) К какому типу относится рассматриваемый граф (простой, мультиграф, псевдограф)?

д) Запишите матрицу смежности графа.

7. Пометьте вершины и ребра орграфа (см. рис. 8, а) буквами или цифрами и выполните следующие упражнения:

а) Запишите все ребра как неупорядоченные пары вершин и отметьте параллельные ребра.

б) Определите положительные и отрицательные степени всех вершин и соответственно их суммы (что можно сказать об этих суммах?).

в) Запишите матрицу инцидентности графа.

8. Докажите, что кубический граф имеет четное число вершин. Обобщается ли свойство четности вершин на однородные графы высших степеней?

9. Постройте графы, соответствующие следующим матрицам смежности:

- 59 -

Охарактеризуйте полученные графы и запишите для них матрицы инцидентности.

10. Расположите на плоскости четыре вершины, как в графе на рис. 11, а, но обозначения вершин v