Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 119
Текст из файла (страница 119)
Если корень а имеет двух сыновей, с и с', и если поиск в глубину начинается от с, он может достичь с' только путем возврата в вершину а; поэтому не существует пути из с в с', который не проходит через а. (2) Предположим, что существует сын с вершины а такой, что между с или одним из его потомков и собственным предком вершины а не существует обратное ребро. Пусть р — родитель а. Поскольку не существует обратного ребра между с или одним из его потомков и собственным предком вершины а, по предыдущей теореме каждое ребро из а или одного из ее потомков должно идти в а или одного из ее потомков.
Таким образом, каждый путь, имеющий начало в вершине с, должен заканчиваться в с или в одном из ее потомков либо проходить через а. Поэтому единственный путь из с в р проходит через а, и а является точкой сочленения. Обратно, предположим, что для всех сыновей с вершины а существует обратное ребро из с в собственного предка вершины а. Пусть с и с'— сыновья вершины а, а Ь и Ь' — собственные предки вершины а, так что е = (И, 6) и е = (г(',Ь') — обратные ребра, где Н и Ы' — потомки вершин с и с' соответственно.
Таким образом, существует путь р,,ь из с в а в 6 и путь р; ь из с' в г(' в Ь'. Поскольку существует путь р из 6 в Ь', который не проходит через а, путь р,ь, за которым следует путь р и путь, обратный к р, ь, является путем из с Раздел 15.5. Осп овные деревья 667 в с', который не проходит через а. Пусть и и ю — две вершины графа О(Ъ;Е). Если о и ю — потомки вершины а, то из вершин о и ю в с и с' соответственно сушествуют пути, которые не проходят через а, где с и с' — сыновья вершины а. Поскольку существует также путь из с и с', который не проходит через а, то существует путь из и в с, далее в с' и далее в ю, который не проходит через а.
Если и — потомок вершины а, а ю — нет, то поскольку существует путь из о к сыну с вершины а, путь р,ь из с в Ь, где Ь вЂ” собственный предок вершины а, и путь вдоль дерева из вершины Ь в ю, и ни один из этих путей не содержит а, то существует путь из о в ю, не содержащий а. Если ни и, ни ю не являются потомками вершины а, то существует путь вдоль дерева из и в ю, не содержаший а.
Таким образом, всегда сушествует путь из о в ю, не содержащий а, и поэтому а не является точкой сочленения. Для нахождения точек сочленения графа О используем предыдущую теорему и попытаемся выяснить, имеется ли в дереве Т сын с такой, что между с или одним из его потомков и собственным предком вершины а не существует обратного ребра. Прежде всего нам нужен такой способ упорядочения вершин, при котором если вершина а является собственным предком вершины Ь, то значение, приписываемое а, больше значения, приписываемого Ь.
Это можно сделать путем присваивания вершинам порядкового номера их поступления в дерево. Тогда, если с является п-ой вершиной, попавшей в дерево, то ей будет присвоено значение счета и, которое мы обозначим через ЗС(с). Используя это упорядочение, присвоим с наименьшее значение вершины а такой, что между а и с или одним из ее потомков существует обратное ребро.
Обозначим это значение через ОР(с) и назовем его ОР-значением вершины с. Как отмечалось раннее, при поиске в глубину, пока у вершины о имеется смежная с ней неиспользованная вершина ю, мы проходим путь от о в ю. И только в случае, когда нельзя продвигаться дальше, мы покидаем шаг 4. Желательно, чтобы новый алгоритм делал то же самое, но, кроме того, по мере добавления в дерево новой вершины ю присваивал новое значение счета величине ЗС(ю).
Временно положим ОР(ю) = ЗС(ю). Будем определять ОР- значения для вершины ю по восходящему принципу. Дойдя до листа 1, сравним его ОР-значение со значением счетчика или ЗС-значения всех вершин, смежных с 1, исключая его родителя, и присвоим ОР(1) значение, минимальное из всех перечисленных. При возврате к родителю и сравним его текущее ЗС-значение с ОР-значением того сына с, от которого произошел возврат. Если ОР(с) > ЗС(р), то никакой потомок вершины с не имеет обратного ребра к собственному предку вершины р, и согласно предыдущей теореме р является точкой сочленения. Далее, положим ОР(р) равным минимуму из его текушего значения и значения ОР(с). Если новых ребер из р больше нет, положим ОР(р) равным минимуму из его текущего значения и ЗС-значений всех вершин таких, что между р и этими вершинами существует обратное ребро. Продолжаем, пока не завершится поиск в глубину. Заметим, что если достигнута точка сочленения а, и мы удалим те (еще неудаленные) ребра, вершиной которых является а и ее потомки, но оставим вершину а, то получим остовное дерево одной из компонент двусвязности графа С.
Формально процедура выражается следующим алгоритмом. Используем рекурсивное свойство, позволяющее алгоритму вызывать самого себя. Используем 666 ГЛАВА тз. Деревья счетчик, изначально установленный на О. Как и ранее, предположим, что начальной меткой для каждой вершины будет метка "нов". Алгоритм поиска точек сочленения — ПТС(о) (1) Пометить о символом "исп".
(2) Присвоить 1 значение 1+ 1. (3) Положить ОР(с) = ЗС(и) =1. (4) Пока имеется невыбранная вершина, смежная с с, выполнять следующее: (а) Выбрать вершину ю, которая является смежной с ю. (б) Если ю имеет метку "нов", то: (г) добавить (с,ю) в РЕБРА ДЕРЕВА; (В) положить и = рагепс(ю); (111) вызвать ПТС(ю); (1т) если ОР(ю) > ЗС(с), то о — точка сочленения. Ребра, ниже и, которые охватывают компоненту, удаляются; (т) положить ОР(и) = ппп(ОР(и), ОР(ю)).
(г) Если ю имеет метку "исп" и ю не является рагепс(ю), то ОР(с) = ппп(ОР(о), ЗС(ю)). ПРИМЕР 16.27. Рассмотрим граф, изображенный на рис. 15.75, и соответствующее дерево (рис. 15.76). Ь а с Рис. 15.76 Рис. 15.75 Из пути аЬйд7" дерева определяем, что ОР(а) = ЗС(а) = 1, ОР(Ь) = ЗС(Ь) = 2, ОР(г!) = ЗС(с!) = 3, ОР(д) = ЗС(д) = 4 и ОР(Г) = ЗС(7) = 5. Из вершины 7 находим обратное ребро из 7 в с( и присваиваем ОР(7) = ЗС(г() = 3. Возвращаемся в вершину д, поскольку à — сын д, то ОР(д) = ш!п(ОР(Г), ОР(д)) = гпш(4,3) = 3. Поскольку ОР(д) = 3 > ЗС(Ы) и д — сын вершины г(, г( — точка сочленения, а дерево на рис.
15.77, сформированное ребрами (7",д) и (с(,д), охватывает компоненту двусвязности (рис. !5.78). Рис. 15.7В Рис. Ы.77 РА812ЕЛ 166 0стоеные деревья 669 Возвращаемся в вершину 8, поскольку д — сын вершины 8, полагаем ОР(г1) = ппп((ОР(д), ОРЯ) = ппп(3,3) = 3. Затем, так как существует обратное ребро из г( в а, присваиваем ОРЯ = ЗС(а) = 1. Возвращаемся в Ь. Поскольку 8 — сын вершины Ь, присваиваем ОР(Ь) = ш)п(ОР(8), ОР(Ь)) = ппп(1,2) = 1. Потому что ОР(Ь) > ЗС(а), вершина а — точка сочленения (а — корень с двумя сыновьями), и дерево (рис.
!5.79), сформированное ребрами (8,Ь) и (Ь,а), охватывает компоненту двусвязности, изображенную на рис. )5.80. Рис. 15.7д Рис. 15.80 Возвращаемся в вершину а; поскольку Ь вЂ” сын вершины а, сравниваем их ОР-значения и находим, что ОР(а) = ппп((ОР(а), ОР(Ь)) = пцп(1,1) = 1, поэтому ОР(а) остается неизменным. Из того, как сформирован путь асей дерева, находим ОР(с) = ЗС(с) = 6, ОР(е) = ЗС(е) = 7 и ОР(й) = ЗС(й) = 8. А так как вершина й не имеет обратных ребер, ОР(й) остается неизменным. Из того, что ОР(й) > ЗС(е) и й — сын вершины е, следует, что е — точка сочленения и ребро (е, й) — остовное дерево компоненты двусвязности, изображенной на рис.
!5.81. Возвращаемся в е; поскольку й — сын вершины е, имеем ОР(е) = шш(ОР(е), ОРЯ) пцп(7,8) = 7, поэтому ОР(е) остается неизменным. Но существует обратное ребро из е в а, значит ОР(е) = ЗС(а) = 1. ОР(с) = пцп(ОР(с),ОР(е)) = шш(1, 6) = 1. Поскольку ОР(е) > ЗС(а), то, как и ожидалось, вершина а — опять найдена как точка сочленения, дерево (рис. 15.82), сформированное ребрами 1а, с) и (с,е), охватывает бикомпоненту, изображенную на рис.
15.83. ,! Рис. 15.88 Рис. 15.82 Рис. 15.81 Наконец, возвращаемся в вершину а, и процесс завершен. П Заметим, что множество из п вершин размечено, если каждой вершине приписано единственное целое число между 1 и п. Таким образом, имеем вершины ш,еа, цз,...,е„. Если рассмотреть все графы, имеющие п размеченных вершин, то сколько остовных деревьев можно построить? Другими словами, сколько имеется остовных деревьев для п размеченных вершин? Ответ на этот вопрос дает формула Кэли. Это число остовных деревьев для К„. ТЕОРЕМА 16.26.
(Формула Кали для дерева) Число остовных деревьев для п размеченных вершин равно и" ~. 670 ГЛАВА тб. Деревья ДОКАЗАТЕЛЬСТВО. Для доказательства утверждения покажем, что каждое остовное дерево однозначным образом можно представить в виде последовательности ам аз, аз,...,ан а длины и — 2 такой, что для 1 < к < и — 2 элемент последовательности аь может быть любым целым числом между 1 и и, и обратно, каждой последовательности ам аз,аз,..., а„з длины и — 2 такой, что для 1 < й < и — 2 выполняется 1 < аь < и, соответствует единственное остовное дерево.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
