Граф дерево листья корень

Лекция № 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. Разбивая число на тройки, переводим полученное двоичное представление в восьмеричное. Получаем . Затем переводим это число в десятичное:.

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

Источник

Теория графов

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

1. Для – графа следующие утверждения эквивалентны:
   1. – дерево;
   2. Любые две несовпадающие вершины графа соединяет единственная простая цепь;
   3. – связный граф, и любое ребро есть мост;
   4. – связный граф и древовидный;
   5. – ациклический граф (лес) и древовидный;
   6. – ациклический граф (лес) и субцикличекий;
   7. – связный, субциклический и неполный, ;
   8. – древовидный и субциклический, исключая и ;

(1->2): Если – дерево, то любые две его несовпадающие вершины соединяет единственная простая цепь. От противного. Пусть существуют две цепи (см. рис.). Тогда — простой цикл. (2->3): Если любые две несовпадающие вершины графа соединяет единственная простая цепь, то – связный граф, и любое ребро есть мост. Имеем: (число компонент связности). Далее от противного. Пусть ребро — не мост. Тогда в концы этого ребра связаны цепью. Само ребро в исходном графе – вторая цепь, что противоречит условию. (3->4): Если – связный граф, и любое ребро есть мост, то – связный и древовидный (). Индукция по (числу вершин). Если , то (число ребер). Пусть равенство выполняется для всех графов с числом вершин меньше . Докажем, что оно выполняется и для вершин. Удалим из ребро , являющееся мостом. Получим две компоненты связности и , для которых верно равенство . Т.е. , . Тогда . (4->5): Если – связный и древовидный (), то – ациклический граф (лес) и древовидный (). От противного. Пусть есть цикл с вершинами и ребрами. Остальные вершин связаны с этим циклом ребрами, т.к. граф связный. Следовательно, , что противоречит условию . Остальное без док-ва.

1. Ориентированные деревья

1. Ориентированным деревом (или ордеревом, или корневым деревом) называется орграф со следующими свойствами:
• существует единственный узел, в который не входит ни один другой узел. Он называется корнем ордерева;
• во все остальные узлы входит только по одному узлу;
• каждый узел достижим из корня.
1. Ордерево обладает следующими свойствами:

1. ; 2. если в ордереве отменить ориентацию ребер, то получится обычное дерево; 3. для каждого узла существует единственный путь, ведущий в этот узел из корня; 4. подграф, определяемый множеством узлов, достижимых из узла , является ордеревом с корнем . Это ордерево называется поддеревом узла .

1. Концевая вершина ордерева называется листом. Путь из корня в лист называется ветвью. Длина наибольшей ветви ордерева называется высотой. Уровень узла ордерева – это расстояние отт корня до узла. Сам корень имеет уровень 0. Узлы одного уровня образуют ярус дерева.

Источник

Читайте также:  При сбрасывании листьев деревьями