Вопросы и задачи

5.1. Сколько существует неориентированных графов с n вершинами?

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

5.3. Доказать, что если число ребер неориентированного графа с n вершинами при n > 2 больше С^2n-1, то он связный.

5.4. Доказать, что не существует неориентированного графа, степени всех вершин которого попарно различны.

5.5. Найти все попарно неизоморфные неориентированные графы с четырьмя вершинами и тремя ребрами.

5.6. Установить, какие из изображенных на рис. 5.47 графов изоморфны, а какие — нет.

5.7. Привести пример неориентированного графа с четырьмя вершинами, изоморфного своему дополнению (самодополнительного). Доказать, что число вершин любого самодополнительного неориентированного графа равно 4k или 4k +1.

5.8. Найти группы автоморфизмов графов, изображенных на рис. 5.48.

5.9. Пусть симметрическая матрица А порядка n, в каждой строке которой находится одинаковое нечетное число t ненулевых элементов, является матрицей смежности неориентированного графа. Показать, что число вершин графа n четное. (Учесть, что а_ii = 0.)

5.10. Доказать, что отношение взаимной достижимости в ориентированном графе есть эквивалентность.

5.11. Установить, является ли ориентированный граф, изображенный на рис. 5.49, связным. Найти все его компоненты и бикомпоненты.

5.12. Конденсация ориентированного графа G = (V, Е) есть ориентированный граф G' = (V/p, E'), где р — отношение взаимной достижимости (см. задачу 5.10), а для любых u',

(v' ∈ V'), u' ≠ v',

(u',v') ∈ E' ⇔ (∃u ∈ u'), (∃v ∈ v'), (u,v) ∈ E.

Доказать, что G — бесконтурный граф тогда и только тогда, когда G изоморфен своей конденсации G'.

5.13. Найти все ориентированные графы с двумя вершинами, являющиеся гомоморфными образами ориентированного графа, изображенного на рис. 5.50.

5.14. Установить, является ли конденсация ориентированного графа (см. задачу 5.12) его гомоморфным образом. Построить примеры.

У к а з а н и е: выяснить, может ли конденсация ориентированного графа содержать петли.

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

5.16. Пусть f: V → V — биекция множества вершин ориентированного графа G = (V, Е) в себя. Сопоставим ей матрицу S с элементами

Доказать:

а) S^-1 = S^T (т.е. S — ортогональная матрица);

б) если f — автоморфизм графа G, то матрица смежности В' автоморфного образа f(G) есть В' = S^TBS.

5.17. Доказать, что если неориентированный граф k-регулярный, т.е. степени всех его вершин одинаковы и равны k, то число k есть собственное число матрицы смежности графа.

У к а з а н и е: доказать, что вектор x = (1, 1, ..., 1) размерности n = |V| есть собственный вектор матрицы смежности k-регулярного графа G.

5.18. Написать алгоритм нахождения множества предшественников Г^-1(v) для каждой вершины графа по спискам смежности. Оценить сложность алгоритма.

5.19. Что является компонентами связности в ориентированном дереве?

5.20. Найти остовное дерево наименьшего веса для неориентированного графа с десятью вершинами, заданного следующим сциском ребер с метками (вершина, вершина, метка):

(v₁, v₂, 1), (v₂, v₃, 5), (v₃, v₄, 4), (v₄, v₅, 8), (v₅, v₆, 3), (v₆, v₈, 5), (v₈, v₉, 11), (v₉, v₁₀, 8), (v₁₀, v₁, 7), (v₂, v₁₀, 5), (v₂, v₇, 8), (v₃, v₇, 7), (v₃, v₅, 3), (v₄, v₁₀, 4), (v₆, v₇, 6), (v₈, v₇, 12), (v₉, v₇, 9).

5.21. Найти условия, необходимые и достаточные для единственности остовного дерева наименьшего веса.

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

5.23. Используя алгоритм Демукрона, найти порядковую функцию сети, заданной следующими матрицами смежности:

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

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

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

5.27. Доказать, что в связном ориентированном графе найдется вершина, при поиске в глубину из которой глубинный остовный лес является деревом. Верно ли обратное?

У к а з а н и е: используйте результат задачи 5.15.

5.28. Найти все возможные глубинные остовные леса, получающиеся при поиске из вершины v₁:

а) для неориентированного графа с 10 вершинами и множеством ребер

E = {{v₁,v₂}, {v₁,v₃}, {v₂,v₃}, {v₂,v₄}, {v₄,v₅}, {v₅,v₆}, {v₆,v₇}, {v₅,v₇}, {v₇,v₈}, {v₈,v₉}, {v₉,v₁₀}, {v₈,v₁₀}};

б) для ориентированного графа с 10 вершинами и множеством дуг

E = {(v₁,v₂), (v₁,v₃), (v₃,v₂), (v₂,v₄), (v₂,v₁₀), (v₄,v₅), (v₅,v₆), (v₇,v₆), (v₇,v₅), (v₇,v₈), (v₈,v₉), (v₉,v₁₀), (v₁₀,v₈)}.

У к а з а н и е: рассмотреть различные порядки расположения вершин в списках смежности.

5.29. Выполнить поиск в глубину для неориентированных графов, изображенных на рис. 5.47, из различных стартовых вершин.

5.30. Выполнить поиск в ширину из вершины v₂ для ориентированного графа из задачи 5.28.

5.31. Выполнить поиск в ширину из вершины v₅ для ориентированного графа, изображенного на рис. 5.38. После остановки алгоритма продолжить поиск из вершины v₈. Сравнить стоимости прохождения со значениями порядковой функции сети, приведенными на рисунке.

5.32. Для ориентированных графов, заданных множеством дуг с указанием меток (вершина, вершина, метка), решить задачу транзитивного замыкания (в полукольце В) и задачу вычисления кратчайших расстояний (в полукольце R⁺):

а) (v₁, v₂, 8), (v₁, v₁, 2), (v₁, v₃, 5), (v₂, v₁, 3), (v₃, v₂, 2);

б) (v₁, v₂, 2), (v₁, v₄, 10), (v₂, v₃, 3), (v₃, v₅, 4), (v₅, v₄, 5), (v₂, v₄, 7), (v₄, v₃, 6);

в) (v₁, v₂, 10), (v₁, v₄, 5), (v₂, v₁, 6); (v₂, v₃, 7), (v₂, v₄, 2), (v₂, v₅, 9), (v₃, v₃, 8), (v₃, v₄, 10), (v₄, v₃, 5), (v₄, v₅, 4), (v₄, v₂, 7), (v₅, v₁, 8), (v₅, v₃, 4);

г) (v₁, v₂, 2), (v₁, v₃, 3), (v₂, v₃, 6); (v₃, v₂, 5), (v₂, v₄, 6), (v₃, v₅, 2), (v₄, v₅, 3), (v₅, v₄, 4), (v₆, v₄, 1), (v₇, v₅, 5), (v₆, v₇, 4), (v₇, v₂, 6);

д) (v₁, v₂, 1), (v₂, v₃, 3), (v₃, v₄, 4); (v₅, v₄, 5), (v₅, v₆, 1), (v₆, v₁, 1), (v₁, v₇, 2), (v₂, v₇, 1), (v₄, v₇, 1), (v₇, v₃, 2), (v₇, v₅, 1), (v₇, v₆, 1);

5.33. Ориентированный граф задан матрицей смежности, содержащей метки соответствующих ребер:

Решить задачу о кратчайших путях для данного ориентированного графа, обратив внимание на то, что метки некоторых дуг равны 0 или отрицательны. Выяснить, применим ли здесь алгоритм Флойда -Уоршела -Клини. Можно ли изменить метки дуг таким образом, чтобы алгоритм Флойда -Уоршела -Клини стал неприменимым?

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