Свойство деревьев дискретная математика

§3 Деревья и их свойства.

Т.1(о весячей вершине)/ во всяком конечном дереве с числом вершин n>1 существует висячая вершина.

Найдется вершина v степени

Возьмем произвольную вершину дерева

Случай 2: v –не висячая к этой вершине будет смежная с вершиннойv. т.е. vv ` не

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

Двигаясь от вершины v в обратном направлении находим хотя бы еще одну висячую вершину.

Т.2/ для (n,m) графа следующ утверждения эквивалентны:

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

Док –во: 1 2 док во от противного дано: G- дерево док-ть: m=n-1 воспользуемся теоремой о висячей вершине пусть висячей вершиной является вершина v будем выполнять просмотр дерева начиная с висячей вершины v , при просмотре добовляем каждый раз одно ребро и одну вершину т.к. циклов нет вершины каждый раз разные выполнив просмотр всего дерева получаем чтд 2 3 дано G – связен m=n-1 док-ть: G – не имеет циклов док-во: случай первый kКол-во ребер кол-во вершин граф имеет к=1 связный компонент т.е. связен чтд 4 5 дано: граф G, две вершины. доказать: если любые две не смежные вершины соеденить ребром то получ граф имеет ровно один цикл. док-во: пусть граф G имеет цикл => найдется две вершины соеденяемые по меньшей мере двумя простыми цепями это противоречит условию => циклов в графе нету соеденим вершины u и v ребром по условию они соеденены цепью => получим цикл не трудно видеть этот цикл будет единственным т.к. убрав ребро мы получили бы что в графе еще есть ребра но граф ациклический. 5  дано: G- ациклич если любые 2 не смежные вершины соединить ребром то получается равно 1 цикл док-ть: G-дерево т.е. требуется док-ть связность графа k>1 возьмем две вершины и соеденим их ребром но не получим цикла чтд Остов графа G=(V,E) пусть Н – суграф графа G суграф Н называют остовым графом G если на каждом связном компоненте порождается дерево В случае связного графа G остов называют каркасом покрывающим деревом или стягивающим графом G=(V,E) – это (n,m) – граф Т.(о циклическом ранге)/ Число ребер которые необходимо удалить в произвольном графе G для получения остова не зависит от последовательности их удаления и равно гдеk – число связанных компонентов. (m- число ребер n- число вершин) Док – во: а) G – связен тогда k=1 тогда остов есть дерево которое будет содержать n вершин и n-1 ребер тогда m-(n-1)= m-n+1= б) G – не связен имеет k>1 связных компонетов => m_i – кол-во ребер в i связный компоненте n_i – кол-во вершин =>чтд. Свойство дерева

1. Циклический ранг любого дерева равен нулю. Число — циклич ранг или цикломатическое число.

Т.(о центре дерева)/ Центр любого дерева состоит из одной вершины или двух смежных вершин Док-во: G=(V,E) – это (n,n-1) – граф(дерево) Случай 1 n=1 ●- это граф вершина. центр состоит из одной вершины теорема выполняется Случай 2 n=2 —это граф звено в этом случае центр состоит из двух вершин Случай 3 n>2 По теореме о висячей вершине в дереве есть хотя бы одна висячая вершина. Удалим в дереве все висячие вершины вместе с инцидентными ребрами. Не трудно видеть что в полученном дереве эксцентриситеты оставшихся вершин уменьшается на единицу. И соотношение между эксцентриситетами сохранится. Центр останется таким же как в исходном графе. Процесс удаления всяческих вершин пока не останется одна вершина или две вершины соединенные ребром тогда все сводится к первому или второму случаю. Т.е. центр состоит из одной вершины или двух смежных. Чтд Т.(Кэли)/ Число помеченных деревьев порядка n равно ( Кэли для доказательства использовал отобрадение функций) (Кергоф при док-ве этой теоремы использовал последовательности для чисел от 1 до n из множества причем числа могли повторятся.) Док- во: Подсчитаем число различных таких последовательностей. n – способов поставить на первое место любое число столькоже на второе и тд Док – во Прюфера: Далее доказывается взаимнооднозначное соответствие м/у последовательностями указанного вида и помеченными деревьями. Имеется дерево Т пометим его вершины от 1 до n Выберем в дереве вершину с наименьшим номером пусть это b₁ с ней смежная некоторая вершина а₁ Возьмем ребро e₁=b₁a₁ и рассмотрим дерево Т-e₁ полученное дерево обозначим Т₁ В этом дереве проделываем ту же процедуру выбор вершины с наименьшим номером и т д продолжая процедуру получим: — две вершины соединенных ребром выпишем: Каждому дереву (помеченному) соответствует единственная числовая последовательность построенная таким образом для каждой последn-2 соответствует единичное дерево. Чтд Ориентированное дерево. А— предок B…K – потомки вершины А С,В – непосредственный потомок вершины А(сын) D,E,F – сын для В В – непосредственный предок F для К непосредственный отец О./ Ориентированный деревом называется симметрический орентированный граф G(V,E) В катором одна вершина не имеет предков а все остальные вершины имеют только по одному непосредственному предку. Вершиныназывается корнем дерева Бинарным деревом называется ордерево в котором каждая вершина имеет не более двух непосредственных потомков. Полным бинарным деровом называется бинарн дерево в котором каждая вершина не является листом(лист-висячая вершина дерева) имеет ровно два непосредственных потомка. Взвешенный граф В реальный задачах часто приходится использовать дополнительную информацию (стоимость проезда расстояние между объектами электроники и т д ) это (n,m)-граф Взвешанным графом назыв пару (G,W) где G-граф а W-функция которая каждому ребру ставит в соотношение число— называемое весом ребрагде Весом графа называют суммарный вес его ребер Рассмотрим связный неор граф остов лин веса тогда, остовом является суграф являющийся деревом Для данного взвешенного графа нужно найти остов минимального веса что: Применяется для проектирование дорог создание электроники.

1. Выберем — ребро минимального строим дерево Т₁(2 вершины a и bи ребро)
2. На некотором шаге имеем дерева Т_k (имеем k+1 вершин) если k+1k а другой не принадлежит Т_k выбирается ребро наименьшего веса, если же k+1=n то остов по строению.

i		ei	W(ei)
1		2.5	1
2		2.1	1
3		5.3	1
4		1.4	2
5		2.7	3
6		4.6	9
Ростов=17

Источник

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

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

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. Узлы одного уровня образуют ярус дерева.

Источник

Лекция 11

Дерево. Лес (ациклический граф). Остовный подграф. Остов. Взвешенный граф. Минимальный остов. Кодирование деревьев.

Базовые понятия и утверждения

1. Определение и основные свойства деревьев.

Определение. Граф называется деревом, если он связный и в нем нет циклов.

Одноэлементный граф, т.е. граф, имеющий одну вершину и не имеющий ребер, также считается деревом.

Граф называется лесом (или ациклическим графом), если в нем нет циклов. Очевидно, что каждая компонента связности леса — дерево.

Пример 1. Граф (рис. 3.19) не является ни деревом, ни лесом. Граф (рис. 3.20) — дерево. Граф (рис. 3.21) — лес, состоящий из четырех деревьев.









Пример 2. Представьте диаграммами все (с точностью до изоморфизма) деревья с пятью вершинами.

◄ Имеется три различных (с точностью изоморфизма) дерева с пятью вершинами (рис. 3.22 — 3.24). ►









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

1) граф — дерево в том и только в том случае, когда в нем нет циклов и ;

2) граф — дерево в том и только в том случае, когда он связный и ;



3) граф — дерево в том и только в том случае, когда он связный, и каждое его ребро является мостом;

4) граф — дерево в том и только в том случае, когда любые две вершины графа можно соединить простой цепью, притом единственной;



5) граф — дерево в том и только в том случае, когда в нем нет циклов и добавление к нему нового ребра приводит к образованию единственного простого цикла.

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

2. Остовы графа. Подграф графа называется остовным подграфом, если множество его вершин совпадает с множеством вершин графа .

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

Пусть — связный граф. Если содержит хотя бы один цикл, то удалив из графа некоторое ребро этого цикла, мы уменьшим число циклов графа по крайней мере на единицу, сохранив при этом его связность. Ясно, что, последовательно разрушая циклы данного графа, можно прийти к остову графа. Поскольку дерево с вершинами имеет ровно ребро, то для получения остова нужно удалить из графа ребро, т.е. число ребер, равное цикломатическому числу связного графа .

Пусть теперь — произвольный граф с компонентами связности. Из каждой компоненты связности этого графа удалим ребро так, чтобы получился остов этой компоненты. В результате получим некоторый остовный подграф графа . Подсчитаем общее число ребер, которое нам пришлось для этого удалить. Сложив равенства , , получим:



.

Таким образом, чтобы получить остовный подграф, нужно, последовательно разрушая циклы графа, удалить из него число ребер, равное его цикломатическому числу.

Пример 3. Построим остов графа , диаграмма которого изображена на рис. 3.25. Удалим из графа ребро ; получим граф (рис. 3.26). Из графа удалим ребро ; получим граф (рис. 3.27). Из графа удалим ребро ; получим граф (рис. 3.28), который является одним из остовов графа .

Источник

Читайте также:  Выпиливание дерева лобзиком узоры