Ветвь дерева как графа

Лекция № 14. Деревья

1. Основные определения

Дерево – связный граф без циклов. Лес (или ациклический граф) – неограф без циклов. Компонентами леса являются деревья. Теорема 14.1.Для неографаGсnвершинами без петель следующие условия эквивалентны:

1. G– дерево;
2. G– связной граф, содержащийn– 1 ребро;
3. G– ациклический граф, содержащийn– 1 ребро;
4. Любые две несовпадающие вершины графаGсоединяет единственная цепь;
5. G– ациклический граф, такой, что если в него добавить одно ребро, то в нем появится ровно один цикл.

Теорема 14.2.НеографGявляется лесом тогда и только тогда, когда коранг графаv(G)=0. Висячая вершина в дереве – вершина степени 1. Висячие вершины называются листьями, все остальные – внутреннимивершинами. Если в дереве особо выделена одна вершина, называемая корнем, то такое дерево называется корневым, иначе – свободным. Корневое дерево можно считать орграфом с ориентацией дуг из корня или в корень. Очевидно, что для любой вершины корневого дерева, кроме корня, . Для корня, для листьев. Вершины дерева, удаленные на расстояние k (в числе дуг) от корня, образуют k-й ярус (уровень) дерева. Наибольшее значение k называется высотой дерева. Если из какой-либо вершины корневого дерева выходят дуги, то вершины на концах этих дуг называют сыновьями (в английской литературе – дочери (daughter)).

1. Центроид дерева

Ветвь к вершине v дерева – это максимальный подграф, содержащий v в качестве висячей вершины. Вес вершиныk – наибольший размер ее ветвей. Центроид (или центр масс) дерева C – множество вершин с наименьшим весом: C = v| c(v) = >. Вес любого листа дерева равен размеру дерева. Высота дерева с корнем, расположенным в центроиде, не больше наименьшего веса его вершин. Свободное дерево порядка n с двумя центроидами имеет четное количество вершин, а вес каждого центроида равен n/2. Теорема 14.3 (Жордана).Каждое дерево имеет центроид, состоящий из одной или двух смежных вершин.Пример 14.1. Найти наименьший вес вершин дерева, изображенного на рис. 14.1, и его центроид. Рис. 14.1 Решение. Очевидно, что вес каждой висячей вершины дерева порядка n равен n – 1. Висячие вершины не могут составить центроид дерева, поэтому исключим из рассмотрения вершины 1, 2, 4, 6, 12, 13 и 16. Для всех остальных вершин найдем их вес, вычисляя длину (размер) их ветвей. Число ветвей вершины равно ее степени. Вершины 3, 5 и 8 имеют по две ветви, размеры которых равны 1 и 14. К вершине 7 подходят четыре ветви размером 1, 2, 2 и 10. Таким образом, ее вес . Аналогично вычисляются веса других вершин:,,. Минимальный вес вершин равен 8, следовательно, центроид дерева образуют две вершины с таким весом: 11 и 15.

1. Десятичная кодировка

Деревья представляют собой важный вид графов. С помощью деревьев описываются базы данных, деревья моделируют алгоритмы и программы, их используют в электротехнике, химии. Одной из актуальных задач в эпоху компьютерных и телекоммуникационных сетей является задача сжатия информации. Сюда входит и кодировка деревьев. Компактная запись дерева, полностью описывающая его структуру, может существенно упростить как передачу информации о дереве, так и работу с ним. Существует множество способов кодировки деревьев. Рассмотрим одну из простейших кодировок помеченных деревьев с выделенным корнем – десятичную. Кодируя дерево, придерживаемся следующих правил.

1. Кодировка начинается с корня и заканчивается в корне.
2. Каждый шаг на одну дугу от корня кодируется единицей.
3. В узле выбираем направление на вершину с меньшим номером.
4. Достигнув листа, идем назад, кодируя каждый шаг нулем.
5. При движении назад в узле всегда выбираем направление на непройденную вершину с меньшим номером.

Кодировка в такой форме получается достаточно компактной, однако она не несет в себе информации о номерах вершин дерева. Существуют аналогичные кодировки, где вместо единиц в таком же порядке проставляются номера или названия вершин. Есть деревья, для которых несложно вывести формулу десятичной кодировки. Рассмотрим, например, графы-звезды , являющиеся полными двудольными графами, одна из долей которых состоит из одной вершины. Другое обозначение звезд –. На рис. 14.2 показаны звезды, а также приведены их двоичные и десятичные кодировки. Корень дерева располагается в центральной вершине звезды. Легко получить общую формулу: . (14.1) Рис. 14.2 Если корень поместить в любой из висячих вершин, то код такого дерева будет выражаться большим числом. Более того, существует зависимость. Аналогично рассматриваются и цепи (рис. 14.3). Цепи обозначаются как. Рис. 14.3 В звездах только два варианта расположения корня с различными десятичными кодировками. В цепи же число вариантов кодировок в зависимости от положения корня растет с увеличением n. Рассмотрим самый простой вариант, расположив корень в концевой вершине (листе). Для получим двоичную кодировку 10 и десятичную 2, для– 1100 и 12, для– 111000 и 56, для– 11110000 и 240. Общая формула для десятичной кодировки цепи с корнем в концевой вершине имеет вид . (14.2) Пример 14.2. Записать десятичный код дерева, изображенного на рис. 14.4, с корнем в вершине 3. Рис. 14.4 Решение. На основании правила кодировки, двигаясь по дереву, проставим в код единицы и нули. При движении из корня 3 к вершине 7 проходим четыре ребра. В код записываем четыре единицы: 1111. Возвращаясь от вершины 7 к вершине 2 (до ближайшей развилки), проходим три ребра. Записываем в код три нуля: 000. От вершины 2 к 5 и далее к 8 (меньший номер): 11; от 8 назад к 5 и от 5 к 9: 01; от 9 к корню 3: 000. И, наконец, от 3 к 6 и обратно: 10. В итоге, собирая все вместе, получим двоичный код дерева: 1 111 000 110 100 010. Разбивая число на тройки, переводим полученное двоичное представление в восьмеричное. Получаем . Затем переводим это число в десятичное:.

Для продолжения скачивания необходимо пройти капчу:

Источник

Дерево (структура данных)

Узел является экземпляром одного из двух типов элементов графа, соответствующим объекту некоторой фиксированной природы. Узел может содержать значение, состояние или представление отдельной информационной структуры или самого дерева. Каждый узел дерева имеет ноль или более узлов-потомков, которые располагаются ниже по дереву (по соглашению, деревья ‘растут’ вниз, а не вверх, как это происходит с настоящими деревьями). Узел, имеющий потомка, называется узлом-родителем относительно своего потомка (или узлом-предшественником, или Корневые узлы [ ]

Самый верхний узел дерева называется корневым узлом. ‘Быть самым верхним узлом’ подразумевает отсутствие у корневого узла предков. Это узел, на котором начинается выполнение большинства операций над деревом (хотя некоторые алгоритмы начинают выполнение с «листов» и выполняются, пока не достигнут корня). Все прочие узлы могут быть достигнуты путём перехода от корневого узла по рёбрам (или ссылкам). (Согласно формальному определению, каждый подобный путь должен быть уникальным). В диаграммах он обычно изображается на самой вершине. В некоторых деревьях, например, Листовые узлы [ ]

Узлы самого нижнего уровня дерева называются Внутренние узлы [ ]

Внутренний узел — любой Поддеревья [ ]

Поддерево — часть деревообразной структуры данных, которая может быть представлено в виде отдельного дерева. Любой узел дерева T вместе со всеми его узлами-потомками является поддеревом дерева T. Для любого узла поддерева либо должен быть путь в корневой узел этого поддерева, либо сам узел должен являться корневым. Т.е. поддерево связано с корневым узлом целым деревом, а отношения поддерева со всеми прочими узлами определяются через понятие соответствующее поддерево (по аналогии с термином «соответствующее Упорядочивание деревьев [ ]

Существует два основных типа деревьев. В натуральные числа) называется деревом с именованными рёбрами или упорядоченным деревом со структурой данных, заданной перед именованием и называемой структурой данных упорядоченного дерева.

Упорядоченные деревья являются наиболее распространёнными среди древовидных структур. Двоичное дерево поиска — одно из разновидностей упорядоченного дерева.

Представление деревьев [ ]

Существует множество различных способов представления деревьев. Наиболее общий способ представления изображает узлы как записи, расположенные в динамически выделяемой памяти с указателями на своих потомков, предков (или и тех и других), или как элементы Деревья как графы [ ]

• Перебор всех элементов дерева
• Перебор ветви дерева
• Поиск элемента
• Вставка нового элемента в определённую позицию
• Удаление элемента
• Удаление ветви дерева (называется Общее применение [ ]

Прочие деревья [ ]

• B-дерево ( B+ дерево , R-дерево
• Список с пропусками
• T-дерево
• T-пирамида
• Ссылки [ ]

• ISBN 0-201-89683-4 . Section 2.3: Trees, pp.308–423.
• Томас Кормен , Клиффорд Штайн . Introduction to Algorithms , Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7 . Section 10.4: Representing rooted trees, pp.214–217. Chapters 12–14 (Binary Search Trees, Red-Black Trees, Augmenting Data Structures), pp.253–320.

Дополнительные источники [ ]

Эта страница использует содержимое раздела Википедии на русском языке. Оригинальная статья находится по адресу: Дерево (структура данных). Список первоначальных авторов статьи можно посмотреть в истории правок. Эта статья так же, как и статья, размещённая в Википедии, доступна на условиях CC-BY-SA .

Источник

Теория графов – деревья

Деревья – это графики, которые не содержат ни одного цикла. Они представляют иерархическую структуру в графической форме. Деревья относятся к простейшему классу графов. Несмотря на их простоту, они имеют богатую структуру.

Деревья предоставляют целый ряд полезных приложений, от простого семейного дерева до сложных в структурах данных компьютерной науки.

дерево

Связный ациклический граф называется деревом. Другими словами, связный граф без циклов называется деревом.

Края дерева известны как ветви . Элементы деревьев называются их узлами . Узлы без дочерних узлов называются листовыми узлами .

Дерево с ‘n’ вершинами имеет ‘n-1’ ребер. Если у него есть еще одно ребро, превышающее ‘n-1’, то это дополнительное ребро, очевидно, должно соединиться с двумя вершинами, что приводит к образованию цикла. Затем он становится циклическим графом, что является нарушением для графа дерева.

Пример 1

График, показанный здесь, является деревом, потому что у него нет циклов, и он связан. Он имеет четыре вершины и три ребра, т. Е. Для ‘n’ вершин ‘n-1’ ребер, как указано в определении.

Примечание. Каждое дерево имеет как минимум две вершины первой степени.

Пример 2

В приведенном выше примере вершины «a» и «d» имеют степень один. А две другие вершины ‘b’ и ‘c’ имеют второй уровень. Это возможно, потому что для того, чтобы не формировать цикл, в диаграмме должно быть как минимум два отдельных ребра. Это не что иное, как два ребра со степенью один.

лес

Несвязный ациклический граф называется лесом. Другими словами, непересекающаяся коллекция деревьев называется лесом.

пример

Следующий график выглядит как два подграфа; но это один несвязный граф. На этом графике нет циклов. Отсюда ясно, что это лес.

Охватывающие деревья

Пусть G – связный граф, тогда подграф H в G называется остовным деревом в G, если –

Остовное дерево T неориентированного графа G является подграфом, который включает в себя все вершины G.

пример

В приведенном выше примере G является связным графом, а H является подграфом G.

Ясно, что граф H не имеет циклов, это дерево с шестью ребрами, которое на единицу меньше общего числа вершин. Следовательно, H – остовное дерево группы G.

Circuit Rank

Пусть «G» связный граф с «n» вершинами и «m» ребрами. Остовное дерево ‘T’ группы G содержит (n-1) ребер.

Следовательно, количество ребер, которые нужно удалить из ‘G’, чтобы получить остовное дерево = m- (n-1), которое называется рангом схемы G.

Эта формула верна, потому что в остовном дереве вам нужно иметь ребра n-1. Из «m» ребер вам нужно сохранить «n – 1» ребер в графе.

Следовательно, удаление ребер n – 1 из m дает ребра, которые нужно удалить из графа, чтобы получить остовное дерево, которое не должно образовывать цикл.

пример

Посмотрите на следующий график –

Для графика, приведенного в примере выше, у вас есть m = 7 ребер и n = 5 вершин.

пример

Пусть ‘G’ – связный граф с шестью вершинами, а степень каждой вершины равна трем. Найдите звание цепи «G».

По сумме теоремы о степени вершин

Теорема Кирхгофа

Теорема Кирхгофа полезна для нахождения числа связующих деревьев, которые могут быть сформированы из связного графа.

пример

Матрица «А» заполняется так, как если между двумя вершинами есть ребро, то она должна быть задана как «1», иначе «0».

Источник