Виталий Сигорский - Математический аппарат инженера

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 2и v 3взаимно переставьте. На множестве обозначенных таким образом вершин постройте граф, изоморфный исходному.

11. Выполните следующие упражнения с графом (см. рис. 11, а):

а) Найдите все ориентированные маршруты от вершины а к вершине е.

б) Найдите все пути и простые пути от вершины а к вершине е.

в) Определите все простые контуры графа.

13. В орграфе (см. рис. 8, а) измените направления дуг таким образом, чтобы он преобразовался в ациклический граф. Постарайтесь найти общее правило такого преобразования.

14. Для графа (см. рис. 12) простойте:

а) часть, состоящую из четырех вершин и пяти ребер;

б) суграф с четырьмя, пятью и шестью ребрами.

15. Два графа G' = (V', E') и G" = (V", E") называются непересекающимися, если V' ∩ V" = ∅ и E' ∩ E" = ∅. Постройте непересекающиеся подграфы графа рис. 12, содержащие по три вершины.

16. Постройте блоки, на которые разбивается сепарабельный граф (см. рис. 14, а).

17. Постройте все различные деревья с восьмью вершинами (их должно быть 23).

18. Постройте все покрывающие деверья и их дополнения для графа (см. рис. 11, а). Сколько имеется существенно различных деревьев?

19. Постройте покрывающий лес несвязанного графа (см. рис. 13).

20. Постройте все прадеревья оргарфа (см. рис. 8, а) с корнем в вершине d.

21. Рассматривая компоненты несвязанного графа (см. рис. 13) как блоки, постройте соответствующий сепарабельный граф. Сколько возможно различных вариантов (без учета изолированной вершины G 2)?

22. Покажите, что приведенные на рис. 21 графы неплоские. Какое минимальное число ребер необходимо удалить из графа на рис. 21, а, чтобы он превратился в плоский? Сколько имеется различных способов такого превращения с точностью до изоморфизма?

23. Покажите, что графы на рис. 21, а и в гомеоморфные.

- 60 -

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

25. Докажите, что (p, p — k) — граф при k ≥ 2 всегда является несвязным и состоит не менее, чем из k компонент.

26. Изобразите все неизоморфные простые графы с пятью вершинами (изолированные вершины допускаются), содержащие три, пять восемь, девять и десять дуг (всего их должно быть 14).

27. Покажите, что число ребер полного графа равно 1/2 p(p — 1), где p — число его вершин.

28. Найдите общее выражение для числа ребер, при котором граф с p вершинами может быть несвязным.

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

Рис. 21. Неплоские графы.

30. Докажите: а) кубический граф имеет точку сочленения тогда и только тогда, когда он содержит мост; б) наименьшее число вершин в кубическом графе, имеющем мост, равно 10.

31. Постройте граф, изоморфный графу Понтрягина-Куратовского (см. рис. 19, б), в котором внешние ребра образуют шестиугольник. Рассматривая его как подграф полного шестиугольника, нарисуйте дополнение этого подграфа. Укажите характерные свойства полученного дополнения.