Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 118
Текст из файла (страница 118)
(3) Заменить метку вершины ео с "нов" на "исп" и положить и = ео (4) Пока имеются невыбранные вершины, смежные с ю, выполнять следующие действия: а) Выбрать вершину ю, смежную с ш 662 ГЛЛВК 75. Йерееья б) Если ю имеет метку "нов", добавить (и, ю) в РЕБРА ДЕРЕВА, поменять метку ю на "исп", положить ш = о и повторить шаг 4. в) Если ю имеет метку "исп" и не является родителем о, добавить (и,ю) в ОБРАТНЫЕ РЕБРА и повторить шаг 4.
(5) Если и ~ а, положить о = (и) и повторить шаг 4. Заметим, что пока для вершины о имеется смежная с ней неиспользованная вершина ю, мы продлеваем путь от о к ш. Только в том случае, когда двигаться дальше нельзя, переходим к шагу 5, возвращаемся к родителю вершины о. ПРИМЕР 16.23. Рассмотрим граф, изображенный на рис. 15.6!. Ь а с Ь Рис. 15.б1 2 а Ь~ Рис.
15.52 Рис. 15.бЗ Теперь выбираем вершину, смежную с вершиной Н. Можно выбрать а, г" или д. Выбор определит форму дерева, поэтому поиск в глубину не продуцирует дерево единственным образом. Предположим, что следующей вершиной выбираем д.
Вершина д имеет метку "нов", поэтому добавляем ребро (б,д) в РЕБРА ДЕРЕВА и меняем метку вершины д на "исп", как показано на рис. 15.64. Из вершины д выбираем вершину (, так как она является смежной с д. Вершина ! имеет метку "нов", поэтому добавляем ребро (д, 1) в РЕБРА ДЕРЕВА и меняем метку вершины ! на "исп", как показано на рис. 15.65. Произвольным образом выбираем вершину а в качестве корня. Меняем метку а с "нов" на "исп". Поскольку вершина Ь смежна с а и имеет метку "нов", добавляем ребро (а,Ь) в РЕБРА ДЕРЕВА и меняем метку вершины Ь на "исп", как показано на рис.
15.62. От вершины Ь переходим к вершине 0, поскольку она является смежной с Ь. Вершина б имеет метку "нов", поэтому добавляем ребро (Ь, б) в РЕБРА ДЕРЕВА и меняем метку вершины Н на "исп", как показано на рис. 15.63. РАЗДЕЛ 15.5. Остоеные деревья 663 Рис. !5.55 Рис. /5.54 Из вершины 7 выбираем вершину И, так как она является смежной с вершиной 7. Однако вершина й уже имеет метку "исп", поэтому добавляем ребро (Н, 7) в ОБРАТНЫЕ РЕБРА, как показано на рис. 15.66.
Поскольку больше нет ребер для проверки на смежность с вершиной 7, кроме родителя, возвращаемся к вершине д. (Далее не будем упоминать родителя как возможную смежную вершину.) Но иных ребер для проверки на смежность с вершиной д тоже нет, поэтому возвращаемся к вершине с1. Здесь единственной вершиной для проверки является а, но вершина а уже имеет метку "исп", поэтому ребро (Ы,Я добавляем в ОБРАТНЫЕ РЕБРА и возвращаемся в вершину Ь, как показано на рис.
15.67. Рис. !5.58 Рис. 15.57 Рис. 15.55 Ребер для проверки на смежность с вершиной Ь больше нет; возвращаемся к вершине а. Заметим, что если бы была возможность достичь каждую вершину, построив путь из Ь, то пока дерево не построено полностью, нам не надо было бы возвращаться в вершину а. Вернувшись в вершину а, можем выбирать с или е. Предположим, что выбрана вершина с. А так как вершина с имеет метку "нов", добавляем ребро (а,с) в РЕБРА ДЕРЕВА и меняем метку вершины с на "исп", как показано на рис. 15.68.
Вершина е смежна с вершиной с и имеет метку "нов"; добавляем ребро (с,е) в РЕБРА ДЕРЕВА и меняем метку е на "исп", как показано на рис. 15.70. Допустим теперь, что выбрана вершина а, потому что она является смежной с вершиной е. Но вершина а уже имеет метку "исп", поэтому добавляем ребро (е, а! в ОБРАТНЫЕ РЕБРА и возвращаемся в вершину е, как показано на рис. 15.70. Поскольку вершина Ь смежна с е, добавляем ребро (е, й! в РЕБРА ДЕРЕВА и меняем метку вершины Ь на "исп", как показано на рис. 15.71. бб4 ГЛАВА 15.
Деревья Рис. 15. 7! Рис. 15.70 Рис. 15.69 Больше нет вершин для проверки из вершины 6, поэтому возвращаемся в вершину е. Но больше нет вершин для проверки из аршины е, поэтому возвращаемся в вершину с. Поскольку нет больше вершин для проверки из вершины с, возвращаемся в вершину а. Других вершин для проверки из вершины и тоже нет, поэтому процесс завершен. П ПРИМЕР 15.24.
Найти остовное дерево графа, изображенного на рис. 15.72. "а аа !7 аб Рис. 15.72 Предположим, что все вершины графа имеют метку "нов". Пусть оо — первая выбранная вершина. Добавим ребра (ио, оь), (оь, огв), (о!в, огт), (огт, ош) " (огь, Иь) в РЕБРА ДЕРЕВА и заменим метки вершин оо,ого о!а, о!т, ош и ош на и. Из вершины о~ь находим, что вершины оь и о!а — смежные с вершиной о!ь, но они уже отмечены меткой "исп", поэтому ребра (огь, ига) и (о~*, оь) добавляются в ОБРАТНЫЕ РЕБРА.
Теперь последовательно возвращаемся в огь, огт, затем в огв и, наконец, в оь. Находясь в оь, добавляем ребра (оь, оы), (оы, огз), (оьз, ош), (ош, о!) и (оп,о4) в РЕБРА ДЕРЕВА и меняем метки вершин оы,огз,ош,оп и оа на и. Вершины оо и огь — смежные с вершиной о4, но они уже имеют метку "исп", поэтому ребра (оа,оо) и (о4, о!4) добавляются в ОБРАТНЫЕ РЕБРА. Возвращаемся в вершину оы, откуда находим, что вершина оы является смежной с оп. Но оы уже отмечена меткой "исп", поэтому добавляем ребро (оп, оы) в ОБРАТНЫЕ РЕБРА.
Осуществляем возврат, пока не достигаем вершины ио. На этот момент имеем дерево с обратными ребрами, изображенное на рис. 15.73. РАЗДЕЛ тд.д, Остовные деревья 666 "и и и Рис. 15.73 Находясь в вершине ео, выбираем вершину, смежную с ео, например, ез, добавляем ребро (ео, ез) в РЕБРА ДЕРЕВА и меняем метку вершины ез на "исп".
Продолжаем процесс, добавляя (из,ев),(ев,еэ),(ед,е1о) и (е1о,еа) в РЕБРА ДЕРЕВА, и меняем метки вершин ее,ед,о1о и еа на "исп". Теперь мы находимся в вершине ез. Вершина ев является смежной с еа, ио ев уже отмечена меткой "исп", поэтому добавляем ребро (еа,ее) в ОБРАТНЫЕ РЕБРА. Возвращаясь в е|о, находим, что вершина ет — смежная с е1о, поэтому добавляем (иш,ет) в РЕБРА ДЕРЕВА, меняя метку вершины ет на и. Вершина ет — смежная с вершиной ов, ио ев уже отмечена меткой "исп", поэтому добавляем ребро (ет, ев) в ОБРАТНЫЕ РЕБРА. Возвращаясь в вершину е1о, находим, что ез — смежная с его. Вершина ез уже отмечена меткой и, поэтому добавляем ребро (езо, ез) в ОБРАТНЫЕ РЕБРА.
Осуществляем возврат в вершину ев. Вершина ез — смежная с ев, добавляем ребро (ев,е1) в РЕБРА ДЕРЕВА, меняя метку вершины е1 иа "исл". Находясь в вершине еы определяем, что вершина ео — смежная с еы и поскольку ио уже отмечена меткой "исп", добавляем ребро (еы ео) в ОБРАТНЫЕ РЕБРА. Возвращаясь в ов, находим, что вершина ез — смежная с ев, поэтому добавляем ребро (ев, ез) в РЕБРА ДЕРЕВА и меняем метку вершины из на "исп". Из вершины ез находим, что вершина ео — смежная с вершиной ез и отмечена меткой "исп", добавляем ребро (ез, ео) в ОБРАТНЫЕ РЕБРА. Построение дерева закончено, и на рис.
15.?4 оно изображено вместе с обратными ребрами. хм Рис. 15.74 П Если граф не связный, то алгоритм ПОДГ будет применяться не ко всему графу, а только к его компоненте, содержащей вершину, выбранную в качестве корня. По этой причине алгоритм поиска остовного дерева в глубину можно использовать для проверки связности графа, для чего необходимо просто реализовывать алгоритм. Если какая-либо вершина не достижима, то рассматриваемый граф 666 Гплои 15 деревья не является связным.
Алгоритм также может быть использован для построения остовного дерева каждой компоненты несвязного графа. Следует, как и прежде, выбрать вершину для корня первого дерева и построить остовное дерево. Затем выбрать одну из недостижимых вершин и построить второе дерево. Продолжать процесс, пока не останется вершин.
Лес остовных деревьев, построенных таким образом, называется вставным лесом. Алгоритм построения остовного дерева в глубину можно также использовать для проверки графа на наличие точек сочленения. Для этого потребуется следующая теорема. ТЕОРЕМА 15.25. Если Т вЂ” глубинное остовное дерево графа С(г', Е) и (а, 6)— ребро графа С(Ъ; Е), то либо а является потомком Ь, либо Ь вЂ” потомком а. ДОКАЗАТЕЛЬСТВО. Если (а, Ь) — ребро дерева Т, то вывод очевиден. Если это не так, то одна из вершин, например, а, должна быть помещена в дерево первой. Но поскольку вершина Ь не была помещена в дерево на шаге 4 алгоритма ПОДГ, то поиск продолжается из вершины а до тех пор, пока не будет найдена вершина Ь. Поэтому вершина Ь является потомком а.
ТЕОРЕМА 15.26. Пусть Т вЂ” глубинное остовное дерево графа С()г, Е). Вершина а Е $~ является точкой сочленения графа С(Ъ;Е) тогда и только тогда, когда вершина а (1) либо является корнем дерева Т и имеет более одного сына, либо (2) вершина а не является корнем дерева Т, и существует такой сын с, что между с, или одним из его потомков, и собственным предком вершины а не существует обратного ребра. ДОКАЗАТЕЛЬСТВО. (1) Если а — корень дерева Т и имеет только одного сына с, то между любой вершиной дерева Т и вершиной с существует путь. Поэтому для двух вершин е и ш, ни одна из которых не совпадает с а, существует путь из е в с в ш, который не проходит через а, и, следовательно, а не является точкой сочленения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
