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