Упражнения

8.1. Пусть -степени простого графа G. Покажите, что G — -связный если

8.2. Покажите, что простой граф G на вершинах — -связный, если

8.3. Пусть — простой -связный граф, — множество вершин, Покажите, что если то существует к вершинно-непересекающихся -путей из а в В.

8.4. Пусть G — простой -связный граф, Покажите, что существует цикл, проходящий через два произвольно заданных ребра вершины.

8.5. Покажите, что

8.6. Найдите -связный граф на 7 вершинах и 18 ребрах.

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

8.8. Ассоциированным ориентированным графом D (G) неориентированного графа G называется граф, полученный заменой каждого ребра графа G на две противоположно направленные дуги, имеющие те же концевые вершины. Покажите, что

а) существует взаимно-однозначное соответствие между путями графа G и ориентированными путями графа D (G); б) граф - реберно-связный тогда и только тогда, когда граф -реберно-связный.

Примечание. Ориентированный граф G называется к-реберно-связным тогда и только тогда, когда для разрушения всех путей между любыми двумя вершинами s и t графа G необходимо удалить не менее к ребер.

8.9. Найдите простой граф, имеющий последовательность степеней (5, 4, 4, 4, 3, 3, 3, 3, 3), с максимально возможной реберной связностью.

8.10. Покажите, что последовательность неотрицательных целых является последовательностью степеней дерева тогда и только тогда, когда

8.11. Покажите, что последовательность неотрицательных целых является псследовательностью степеней графа тогда и только тогда, когда четна

8.12. Покажите, что последовательность неотрицательных целых является последовательностью степеней простого графа тогда и только тогда, когда четна и б) для

8.13. Покажите, что последовательность (реализуемая простым графом) является последовательностью степеней простого -связного графа тогда и только тогда, когда для б) где — число ребер графа G [8.6].

8.14. Докажите или опровергните: для любого паросочетания М существует такое максимальное паросочетание М, что ММ.

8.15. Квадратная матрица Р с действительными неотрицательными элементами называется бистохастической, если сумма элементов в каждой строке и в каждом столбце равна 1. Матрица подстановок — это (-матрица, содержащая точно по одной 1 в каждой строке и каждом столбце. Покажите, что бистохастическую матрицу Р можно определить как где каждая матрица подстановок, каждое неотрицательное число и

8.16. Пусть G — двудольный граф с двудольным разбиением (X, Y). Покажите, что если граф G имеет полное паросочетание X с К, то существует такая вершина что Для любой вершины по крайней мере одно максимальное паросочетание содержит ребро

8.17. -фактором графа G называется -однородный остовный подграф графа G. Очевидно, что -фактор — это совершенное паросочетание. Граф G называется -факторизуемым, если он является объединением нескольких реберно-непересекающихся -факторов. Покажите, что -факторизуемы.

8.18. а) Покажите, что можно определить как объединение связных

Примечание. Связный -фактор является гамильтоновым циклом.

б) Покажите, что объединение -фактора и связных -факторов.

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

8.20. Пусть М и N — реберно-непересекающиеся паросочетания графа G, причем Покажите, что существуют такие непересекающиеся паросочетания М и N, что

8.21. Покажите, что если — двудольный граф, а то существует k таких непересекающихся паросочетаний графа G, что для где — число ребер

8.22. Покажите, что дерево Т имеет совершенное паросочетание тогда и только тогда, когда Для всех вершин Т, где — число нечетных компонент в

8.23. Докажите теорему Холла, используя теорему Татта (см. упражнение 5.3.1 в оаботе [8.35]).

8.24. Докажите теорему Холла, используя теорему Менгера (см. работу [8.36], теорема ),