Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 253
Текст из файла (страница 253)
(5)=~(6). Предположим, что граф С ациклический и что )Е! = ~Ц вЂ” 1. Пусть й — количество связных компонентов графа С. По определению каждый связный компонент представляет собой свободное дерево; поскольку из (1) вытекает (5), сумма всех ребер во всех связных компонентах С равна ~Ц вЂ” lс. Следовательно, й должно быть равно 1, а С должно быть деревом. Поскольку из (1) вытекает (2), любые две вершины С соединены единственным простым путем.
Таким образом, добавление любого ребра к С создает цикл. (6)=в(1). Предположим, что С вЂ” ациклический граф, но добавление любого ребра в Е приводит к образованию цикла. Мы должны показать, что С вЂ” связный граф. Пусть и и и — произвольные вершины графа С. Если и и и не являются смежными, добавление ребра (и,п) создает цикл, в котором все ребра, кроме (и, о), принадлежат С. Таким образом, существует путь из и в и, но поскольку и и и выбраны произвольно, С оказывается связным графом.
Б.5.2 Деревья е корнем и упорядоченные деревья Дерево с кормим (гоо1ег) 1гее) представляет собой свободное дерево, в котором выделена одна вершина, именуемая корнем (гоо1) дерева. Зачастую вершины в дереве с корнем называют узлами4 (лодел) дерева. На рис. Б.ба показано дерево с корнем, состоящее из 12 узлов с корнем в узле 7.
Рассмотрим узел х в дереве Т с корнем т. Любой узел у на (единственном) пути от и к х называется кредкалг (апсез1ог) х. Если у является предком х, то х является лоязомкаиг (дезсепдап1) у (каждый узел является собственным предком и потомком). Если у — предок х н х ф у, то у — истинный предок (ргорег апсез1ог) х, а х, соответственно, истинный потомок (ргорег с)езсепс)ап1) у. Поддереваи с кормиле в узле х (зиЬггее гоогед аг х) называется дерево, порожденное потомками х, корнем которого является узел х.
Например, на рис. Б.ба поддерево с корнем в узле 8 содержит узлы 8, 6, 5 и 9. Если (у, х) — последнее ребро на пути от корня и дерева Т к узлу х, то узел у является родилзельским (рагел1) по отношению к х, а х — ребенкам (сЫ16), Термин "узел" зачастую используется в теории графов как синоним термина "вершина". Мы ме будем использовать термин "узел" только лля вершины дерева с корнем.
1)рнложение Б. Множества н прочие художества 1221 г'."б б~ '4) Пбб«пз ',б.-, ' З) Гзбб лы Г ббякз б или дочерним узлом по отношению к узлу у. Корень дерева — единственный узел, не имеющий родительского узла. Если два узла имеют общий родительский узел, мы будем называть такие узлы родственными, или братьями (з(Ышлз).
Узел, у которого нет дочерних узлов, называется внешним узлом (ехгегпа! поде) или лиспиви (!еа1). Узел, не являющийся листом, называется внутренним узлам (шгегпа! поде). Количество дочерних узлов узла х называется его степеньюб (деягее). Длина пути от корня г к узлу х называется глубиной (бергЬ) узла х в дереве.
Высота (Ье(БЬг) узла в дереве равна количеству ребер в самом длинном простом нисходящем пути от узла к листу; высотой дерева называется высота его корня. Высота дерева равна также наибольшей глубине узла дерева. Упорядоченное дерево (огг(егеб ггее) представляет собой дерево с корнем, в котором дочерние узлы каждого узла упорядочены. Т.е. если узел имеет к дочерних узлов, то существует первый, второй, ..., к-й дочерние узлы. Два дерева, приведенные на рис. Б.ба и рис.
Б.бб, отличаются, если рассматривать их как упорядоченные, но одинаковы, если трактовать их как обычные деревья с корнем. Б.5.3 Бинарные и позиционные деревья Бинарные деревья определяются рекурсивно. Бинарное дерево (Ьшагу ггее) Т представляет собой конечное множество узлов, которое ° либо не содержит узлов, ° либо состоит из трех непересекающихся множеств узлов: корневой узел, бинарное дерево, называемое левым поддереваи (1ей зпЬггее), и бинарное дерево, называемое правым поддеревом (г(яЬг впЬггее).
Заметим, что степень узла зависит от того, рассматриваем ли мы дерево с корнем или свободное дерево. Степень вершины в свободном дереве, как и а любом неориентироаангюм графе, равна количеству смежных вершин. В дереве с корнем степень равна количеству дочерних узлов— ролительский узел при вычислении степени не учитывается. А »к 1 г 'т (.'3 Рис. Б.б. Деревья с корнем и упорядоченные деревья Часть Ч!!!. Приложения: математические основы 1222 Бинарное дерево, которое не содержит узлов, называется пустым (ешр1у псе) или нулевьам (пи!1 ггее), и иногда обозначается как )чп.. Если левое поддерево непустое, его корень называется левым ребенком (1ей сЫ1б) корня всего дерева; аналогично, корень непустого правого поддерева называется правым ребенком (пбЬ! сЫ!с!).
Если поддерево является пустым, мы говорим, что соответствующий ребенок отсутствует (аЬзепг). Пример бинарного дерева можно увидеть на рис. Б.7а. Бинарное дерево представляет собой не просто упорядоченное дерево, в котором каждый узел имеет степень не более 2. Например, в бинарном дереве в случае узла с одним дочерним имеет значение, какой именно этот дочерний узел — левый или правый. В упорядоченных деревьях такое различие в случае одного дочернего узла не делается.
На рис. Б.7б показано бинарное дерево, отличающееся ст приведенного на рис. Б.7а позицией одного узла. Если рассматривать эти деревья как просто упорядоченные, то они являются идентичными. Пустующие места в бинарном дереве можно заполнить фиктивными листьями, как показано на рис. Б.7е, где они изображены квадратами. Так получается полностью бинарное дерево (й)11 Ьшагу ггее): каждый узел либо представляет собой лист, либо имеет степень 2. Узлы со степенью 1 в таком дереве отсутствуют. Информация о позициях узлов, которая отличает упорядоченные деревья от бинарных, может быть расширена на случай деревьев с более чем 2 дочерними узлами в каждом узле. В позиционном дереве (роз!1!она! Сгее) все дочерние узлы данного узла пронумерованы различными натуральными числами.
Если у данного узла среди дочерних нет узла с номером г', то г-й дочерний узел у данного узла отсутствует (аЬзепг). Позиционное дерево называется к-арным (lс-агу) деревом, если в нем не имеется дочерних узлов с номером, превышающим й. Таким образом, бинарное дерево представляет собой )с-арное дерево при )с = 2.
Полным 7с-арным деревом (сошр1е)е !с-агу ггее) называется /с-арное дерево, у которого все листья имеют одну и ту же глубину, а все внутренние узлы— одну и ту же степень !с. Так, на рис. Б.8 показано полное бинарное дерево высота Я В ф (б1 б) Рис. Б.7. Бинарные деревья Приложение Б. Множества н прочие художества 1223 плеве Гоьмн з х, .;',,~'...; г г ,,.ЧО,лм Рис. Б.8.
Полное бинарное дерево, которое имеет высоту 3, 8 листьев н 7 внутренних узлов юторого равна 3. Сколько листьев содержится в полном 1с-арлем дереве, высота которого равна Ь? Корень имеет й дочерних узлов на глубине 1, каждый из которых содержит по 1с дочерних узлов с глубиной 2 и т.д. Таким образом, количество листьев на глубине Ь равно 1с". Соответственно, высота полного й-арного дерева с и листьями равна 1обь и. Количество внутренних узлов полного 1с-арного дерева высоты и равно ь-~ 12 + + 16-1 '~ ~~1т й — 1 =о в соответствии с (А.5). Таким образом, полное бинарное дерево содержит 2" — 1 внутренних узлов. Упражнения Б.5-1. Нарисуйте все свободные деревья, состоящие из 3 вершин А, В и С. Изобразите все корневые деревья с этими же узлами и узлом А в качестве корня.
Нарисуйте все упорядоченные деревья с узлами А, В и С и узлом А в качестве корня. Изобразите все бинарные деревья с этими же узлами и узлом А в качестве корня. Б.5-2. Пусть С = (г', Е) — ориентированный ациклический граф, в ютором имеется вершина ио Е г', такая что имеется единственный путь от оо к любой другой вершине оба. Докажите, что неориентированная версия графа С является деревом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
