Алгоритмы - построение и анализ (1021735), страница 252
Текст из файла (страница 252)
Приложения: математические основы 1218 Б.5 Деревья Как и слово "граф", слово "дерево*' также употребляется в несюльких родственных смыслах. Здесь представлены основные определения и математические свойства неюторых видов деревьев. Вопросы представления деревьев в памяти компьютера рассматриваются в разделах 10.4 и 22.1. Б.5.1 Свободные деревья Как уже говорилось в разделе Б.4, свободные деревья (Ггее ггее), или деревья без выделенного корня, представляют собой связный ациклический неориентированный граф.
Прилагательное "свободный" зачастую опускается, когда мы говорим о графе, являющемся деревом. Многие разработанные для деревьев алгоритмы могут работать и с лесом. Пример дерева показан на рис. Б.4а, леса— на рис. Б.4б. Лес не является деревом в силу того, что представляющий его граф не является связным. Граф на рис. Б.4в содержит цикл, а потому не может быть ни деревом, ни лесом. В следующей теореме указано несколько важных свойств деревьев. Теорема Б.2 (Свойства свободных деревьев). Пусть С = (1г, Е) — неориентированный граф. Тогда следующие утверждения равносильны. 1. С вЂ” свободное дерево.
2. Любые две вершины С соединяются при помощи единственного простого пути. 3. С вЂ” связный граф, но при удалении из Е любого ребра перестает быть таковым. 4. С вЂ” связный граф, и )Е! = ٠— 1. 5. С вЂ” ациклический граф, и )Е~ = ٠— 1. б. С вЂ” ациклический граф, но при добавлении любого ребра в Е получается граф, содержащий цикл. б) Рис. Б.4. Примеры дерева, леса и графа, который ие является деревом или лесом из- за наличия цикла Приложение Б. Множества и прочие художества 1219 к! Рис. Б.5. Иллюстрация к доказательству теоремы Б.2 Доказательство. (1)=ь(2). Поскольку дерево является связным, для любых двух вершин С имеется как минимум один соединяющий их простой путь. Пусть и и ц — вершины, соединенные двумя простыми путями р1 и рз, как показано на рис.
Б.5. Пусть ш — вершина, в которой пути впервые расходятся, т.е. следующие за ю вершины на путях р1 и рз, соответственно, х и у, причем х ~ У. Пусть я — первая вершина, в которой пути вновь сходятся, т.е. я — первая после и вершина на пути рп которая также принадлежит пути рз. Пусть р' — подпугь р1 от зц через х до г, а р" — подпуть рз от и через у до г.
Пути р' и р" не имеют общих точек, кроме конечных. Тогда путь, образованный объединением р' и пути, обратного к р", образует цикл. Это противоречит нашему предположению о том, что С является деревом. Таким образом, если С вЂ” дерево„то между вершинами не может быть больше одного соединяющего их простого пути. (2)=ь(3). Если любые две вершины С соединяются единственным простым путем, то С вЂ” связный граф. Пусть (и, ц) — ребро из Е. Это ребро представляет собой путь от и до ц, а значит, это единственный путь от и до ц.
Если мы удалим из графа путь (и, ц), пути от и до и не будет, а граф перестанет быть связным. (3)=ь(4). По условию граф С является связным, а из упражнения Б.4-3 нам известно, что )Е( > ٠— 1. Докажем по индукции, что )Е! < ٠— 1. Связный граф с одной или двумя вершинами имеет ребер на одно меньше, чем вершин.
Предположим, что С имеет и > 3 вершин и что для меньшего числа вершин выполнение условия ~Е~ < )Ц вЂ” 1 доказано. Удаление произвольного ребра из С разделяет граф на /с > 2 связных компонентов (на самом деле /с = 2). Каждый компонент удовлетворяет условию (3) теоремы, т.к. в противном случае этому условию не удовлетворяет само дерево С. Тогда, по индукции, количество ребер во всех компонентах не превышает ~Ц вЂ” /с < (Ц вЂ” 2.
Добавление удаленного ребра дает нам неравенство )Е! < ٠— 1. (4)=ь(5). Предположим, что граф С является связным и что )Е~ = (Ц вЂ” 1. Мы должны показать, что граф С ациклический. Предположим, что граф содержит цикл, состоящий из и вершин цы цз,..., ць', без потери общности можно считать, что это простой цикл.
Пусть Сь = (Уь Еь) — подграф С, состоящий из данного Часть ЧП1. Приложения: математические основы 1220 цикла. Заметим, что )Ъ~! = ~Еь~ = й. Если )с < Щ, то должна существовать веРшина пь+з Е 1г — )гь смежнаЯ с некотоРой веРшиной о; Е 1гам что следУет из связности С. Определим подграф Сь+з = Я+ы Еььг) графа С как подграф, У которого 1я+з = Ъа 0 (пя+з) и Еь+з — — Еь 0((о;,ил+1)). Заметим, что (Ъ~+г~ = = ~Ел+1~ = )с+ 1. Если ге + 1 < Щ, мы можем продолжить наше построение, аналогично определяя Сь+з и т.д.
до тех пор, пока не получим С„= Я„Е„), такой что и = Щ, Ъ'„= У и )Е„! = ))г„! = Щ. Поскольку ф— подграф С, Е„С С Е, следовательно, )Ц > )Ъ'), что противоречит предположению )Е) = ~Ц вЂ” 1. Следовательно, граф С ациклический. (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. Например, в бинарном дереве в случае узла с одним дочерним имеет значение, какой именно этот дочерний узел — левый или правый. В упорядоченных деревьях такое различие в случае одного дочернего узла не делается. На рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
