Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 121
Текст из файла (страница 121)
15.!09 Рис. 15.ПО Полагаем с(ея(ог) = 2 и с!ея(ев) = О, поэтому десятка степеней имеет вид (2,0,0,0,0,0,1,2,2,1). Считываем ае = 8 и, поскольку ет среди всех вершин степени 1 имеет наименьший индекс, создаем ребро (еа,ет), как показано на рис. 15.!11. Полагаем б!ей(ов) = 1 и б!е8(ет) = 0; десятка степеней теперь имеет вид (2,0,0,0,0,0,0,1,2,1). Считываем ат = 9 и, потому что пв среди всех вершин степени 1 имеет наименьший индекс, создаем ребро (ев, юд), как показано на рис. 15.! 12. Уб У Уб У Рис. 15.П1 Рис. 15.П2 Полагаем с!ея(од) = 1 и б)ей(еа) = О, поэтому десятка степеней теперь имеет вид (2, О, 0,0, О, О, О, О, 1, 1). Считываем ав = 1 и, поскольку ед среди всех вершин степени 1 имеет наименьший индекс, создаем ребро (ег, ед), как показано на рис.
!5.1!3. б Рис. 15.ПЗ Полагаем б!ей(юг) = 1 и г!ея(ед) = О, поэтому десятка степеней теперь имеет вид (1,0,0,0,0,0,0,0,0,1). Наконец, вся последовательность прочитана и бек(ог) = б!е8(ого) = 1; формируем ребро 1еы юш) и получаем искомое дерево из упражнения 15.30. П 676 ГЛАВА 15. Деревья Предыдущая теорема дает количество различных остовных деревьев на и размеченных вершинах, но не рассматривает конкретный граф с этими вершинами. Когда рассматривается определенный граф, то количество различных остовных деревьев для этого графа уменьшается, так как используются только ребра графа.
Данный раздел завершает метод определения количества остовных деревьев для графа с и размеченными вершинами. Используя это определение, сформулируем следующую, весьма впечатляющую теорему, которую приведем без доказательства. ТЕОРЕМА 16.34. (Матричная формула Кирхгофа) Пусть С вЂ” связный граф с помеченными вершинами. Пусть К = Р— А, где А — матрица смежности графа С, а Р— матрица степеней графа С. Число остовных деревьев графа С равно любому из алгебраических дополнений матрицы К. ПРИМЕР 16.36. Найдем количество остовных деревьев графа, изображенного на рис. 15.114. г Рис.
/В.гг4 Поскольку с1е3(ог) = г1е31ггз) = 2 и де3(ог) = г)е3(о4) = 3, Матрица А имеет вид К=С вЂ” А= с=[ 2 О О О О 3 О О О О 2 О О О О 3 2 О О О О 3 О О О О 2 О О О О 3 2 — 1 Π— 1 — 1 3 — 1 — 1 Π— 1 2 — 1 — 1 — 1 — 1 3 РДЗДЕП 15.5. Остоеные деревья 677 Алгебраическое дополнение Кы есть 3 — 1 — 1 с!е! — 1 2 — 1 = 3 с(еС ~ — (-1) с!ес ~ ~ + — 1 1 ( — 1 — 1 1 — 3~ ~-1 3~ +( — 1)бе! ~ ~ =3(5) — 4 — 3=8. ( — 1 21 Значит, сушествует восемь остовных деревьев.
° УПРАЖНЕНИЯ 1. Задан граф (рис. !5.!15), вершины которого упорядочены так, как помечены. а) Найдите остовное дерево, удаляя ребро из каждого цикла. б) Найдите остовное дерево поиском в ширину. в) Найдите остовное дерево поиском в глубину. е~ ее е Рис. 15.115 Рис. 15.115 2. Задан граф (рис.
15.1!6), вершины которого упорядочены так, как помечены. а) Найдите остовиое дерево, удаляя ребро из каждого цикла. б) Найдите остовное дерево поиском в ширину. в) Найдите остовное дерево поиском в глубину. 3. Задан граф (рис. 15.1!?), вершины которого упорядочены так, как помечены. а) Найдите остовное дерево, удаляя ребро из каждого цикла. б) Найдите остовное дерево поиском в ширину. в) Найдите остовное дерево поиском в глубину.
"~о еи Рис. 15.115 Рис. 15.117 678 ГЛАВА 15. Деревья У1 У7 Рис. 15.!19 Рис. 15.120 6. Задан граф (рис. !5.120), вершины которого упорядочены так, как помечены. а) Найдите остовное дерево, удаляя ребро из каждого цикла. б) Найдите остовное дерево поиском в ширину. в) Найдите остовное дерево поиском в глубину. 7. Задан граф (рис. 15.121), вершины которого упорядочены так, как помечены.
а) Найдите остовное дерево, удаляя ребро из каждого цикла. б) Найдите остовное дерево поиском в ширину. в) Найдите остовное дерево поиском в глубину. 7 з Рис. 15. 121 Рис. 15.122 8. Задан граф (рис. 15.122), вершины которого упорядочены так, как помечены. а) Найдите остовное дерево, удаляя ребро из каждого цикла. б) Найдите остовное дерево поиском в ширину. в) Найдите остовное дерево поиском в глубину.
4. Задан граф (рис. 15.!1 а) Найдите остовное б) Найдите остовное в) Найдите остовное 5. Задан граф (рис. !5.!1 а) Найдите остовное б) Найдите остовное в) Найдите остовное 8), вершины которого упорядочены так, как помечены. дерево, удаляя ребро из каждого цикла. дерево поиском в ширину. дерево поиском в глубину. 9), вершины которого упорядочены так, как помечены. дерево, удаляя ребро из каждого цикла.
дерево поиском в ширину. дерево поиском в глубину. РЛЗДЕЛ 15.З. Остовныв деревья 679 9. Задан граф Кз. а) Найдите остовное дерево, удаляя ребро из каждого цикла. б) Найдите остовное дерево поиском в ширину. в) Найдите остовное дерево поиском в глубину.
10. Задан граф Кзин а) Найдите остовное дерево, удаляя ребро из каждого цикла. б) Найдите остовное дерево поиском в ширину. в) Найдите остовное дерево поиском в глубину. 11. Задан граф Петерсена. а) Найдите остовное дерево, удаляя ребро из каждого цикла. б) Найдите остовное дерево поиском в ширину. в) Найдите остовное дерево поиском в глубину. 12. Используя алгоритм ПТС поиска точек сочленения, найдите точки сочленения и компоненты двусвязности для графа, изображенного на рис.
!5.123. Ув уо уу ую уи уу Рис. Ы.!24 Рис. 15. /23 13. Используя алгоритм ПТС поиска точек сочленения, найдите точки сочленения и компоненты двусвязности для графа, изображенного на рис. 15.124. 14. Используя алгоритм ПТС поиска точек сочленения, найдите точки сочленения и компоненты двусвязности для приведенных ниже графов. а) б) ч, ч, чв уо у~ 6ВО ГЛЯ8А 15. Деревья в) и !б 15. Для графа С, представляюшего собой простой цикл, опишите его остовные деревья, полученные поиском в ширину и в глубину. Если С имеет п вершин, то сколько у него остовных деревьев? 16. Если С вЂ” граф, представляющий собой цикл, но необязательно простой изменится ли описание его остовных деревьев? Почему? Может ли граф С иметь точку сочленения? 17.
Докажите, что ребро графа С принадлежит всем его остовным деревьям тогда и только тогда, когда это разрезающее ребро. 18. Найдите для графа С необходимые и достаточные условия равенства остов- ных деревьев, полученных поиском в глубину и в ширину? 19. Покажите, что остовное дерево, полученное поиском в глубину для К„ при п > 3, является простым путем, а остовное дерево, полученное поиском в ширину, таковым не является. 20. Найдите такое а, что если и ) а, то К„имеет два остовных дерева без общих ребер. 21. Докажите, что если Е' — разрезающее множество графа С, то каждое остов- ное дерево содержит ребро из Е'. 22. Сколько остоиных деревьев имеет граф Кз? Сколько остовных деревьев име- ет Ка? Сколько остовных деревьев имеет К„? 23. Сколько остовных деревьев имеет граф Кз „? 24.
Если С вЂ” граф с и вершин и е ребер, то сколько ребер можно удалить, не нарушив связности оставшегося графа? 26. Пусть Т и Т' — различные остовные деревья графа С. Пусть е — ребро дерева Т, которое не является ребром дерева Т', и Т, — это дерево Т, из которого удалено ребро е. Докажите, что в дереве Т' имеется такое ребро е', добавив которое в Т„ получим граф, который будет опять остовным деревом графа С. 26. Используя алгоритм преобразования дерева в последовательность, определи- те соответствующие последовательности для каждого из приведенных ниже деревьев.
РАздел 15.5. Остоеные деревья 881 а) б) "о ~Х 3 б з б 7 з б Г) в) "о "г ог "з З б 7 б б 27. Используя алгоритм преобразования дерева в последовательность, определите последовательности, соответствующие каждому из следующих деревьев. а) б) "о Уз оз б в) г) б "га "в 28. Используя алгоритм перевода дерева в последовательность, постройте соответствующие деревья для приведенных ниже последовательностей. а) 1,2,3,3,2,3. б) 1,3,3,5,5,4,4. в) 1,2,2,2,5,4,5,6.
29. Используя алгоритм перевода дерева в последовательность, постройте соответствующие деревья для приведенных ниже последовательностей. а) 1,4,2,3,2,3. б) 1,4,3,3,4,4,4. в) 1,5,2,5,3,6,5,5. 682 ГЛАВА 15. Деревья 30. Используя матричную формулу Кирхгофа, определите число остовных деревьев для каждого из приведенных ниже графов.
а) б) в) У уг уз а у У 2 уз 31. Используя матричную формулу Кирхгофа, определите число остовных деревьев для каждого из приведенных ниже графов. а) б) в) уа уг уа а уа 32. Сколько остовных деревьев имеет граф К„,„р 15.6. МИНИМАЛЬНЫЕ ОСТОВНЫЕ ДЕРЕВЬЯ Взвешенный граф определен в предыдущей главе как граф, каждому ребру которого приписано положительное число, назывемое весом. Этот вес может описывать расстояние, стоимость или другие данные. Например, если бы вершины представляли города, то вес мог бы быть расстоянием между городами или стоимостью перелета из одного города в другой.
Вес остовного дерева взвешенного графа С равен сумме весов, приписанных ребрам остовного дерева. Минимальным остоиным деревом назывется такое остовное дерево графа С, что вес Т меньше или равен весу любого другого остовного дерева графа С. Мы рассмотрим два способа построения минимального остовного дерева взвешенного графа С. Первый называется алгоритмом Крускала. Идея метода состоит в том, чтобы формировать дерево Т(Е, И), выбирая ребра с наименьшим весом так, чтобы не возникал цикл. Алгоритм Крускала (1) Выбрать в графе С ребро е минимального веса, не принадлежащее мно- жеству Е и такое, что его добавление в Е не создает цикл в дереве Т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
