Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике Упражнения8.1. Пусть 8.2. Покажите, что простой граф G на 8.3. Пусть 8.4. Пусть G — простой 8.5. Покажите, что 8.6. Найдите 8.7. Покажите, что ребра простого графа можно ориентировать таким образом, чтобы получился сильно связный граф, тогда и только тогда, когда граф 8.8. Ассоциированным ориентированным графом D (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. Покажите, что последовательность 8.14. Докажите или опровергните: для любого паросочетания М существует такое максимальное паросочетание М, что ММ. 8.15. Квадратная матрица Р с действительными неотрицательными элементами называется бистохастической, если сумма элементов в каждой строке и в каждом столбце равна 1. Матрица подстановок — это ( 8.16. Пусть G — двудольный граф с двудольным разбиением (X, Y). Покажите, что если граф G имеет полное паросочетание X с К, то существует такая вершина 8.17. 8.18. а) Покажите, что Примечание. Связный б) Покажите, что 8.19. Покажите, что связный граф G 8.20. Пусть М и N — реберно-непересекающиеся паросочетания графа G, причем 8.21. Покажите, что если 8.22. Покажите, что дерево Т имеет совершенное паросочетание тогда и только тогда, когда 8.23. Докажите теорему Холла, используя теорему Татта (см. упражнение 5.3.1 в оаботе [8.35]). 8.24. Докажите теорему Холла, используя теорему Менгера (см. работу [8.36], теорема
|
1 |
Оглавление
|