Деревья эквивалентные определения дерева

Теорема об эквивалентных определениях дерева

Пусть , , тогда следующие утверждения попарно эквивалентны:

1. дерево, то есть связный граф без циклов;

4. связный граф, но при удалении любого ребра становится несвязным;

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

Доказательство. Покажем, что из .

: дерево, по теореме о числе ребер в дереве .

: По лемме о числе связных компонент в графе без циклов

: Если в графе имеется цикл, то удаление ребра из цикла

оставляет граф связным, что противоречит условию.

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

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

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

Дадим индуктивное определение корневого дерева.

1. Граф, имеющий единственную вершину и пустое множество ребер, называется корневым деревом с корнем .

2. Пусть – корневые деревья с корнями и каждое . При этом при .

3. Пусть , тогда граф , где и , называется корневым деревом с корнем . Деревья называются поддеревьями дерева .

Определение. Упорядоченным корневым деревом называется корневое дерево , в котором задан порядок его поддеревьев и каждое поддерево – упорядоченное дерево.

Получим оценку числа упорядоченных корневых деревьев. Для этого введем кодировку упорядоченных корневых деревьев. Кодировать будем согласно индуктивному определению корневого дерева.

1. Дереву поставим в соответствие пустое слово.

2. Пусть упорядоченное корневое дерево имеет поддеревья и каждому поддереву поставлен в соответствие код .

3. Тогда кодом дерева будет код .

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

Из определения кода дерева следует, что код дерева – это слово из нулей и единиц.

Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:

Источник

Дерево, эквивалентные определения

Для графа [math]G[/math] эквивалентны следующие утверждения:

1. [math]G[/math] — дерево.
2. Любые две вершины графа [math]G[/math] соединены единственным простым путем.
3. [math]G[/math] — связен и [math] p = q + 1 [/math] , где [math]p[/math] — количество вершин, а [math]q[/math] количество ребер.
4. [math]G[/math] — ацикличен и [math] p = q + 1 [/math] , где [math]p[/math] — количество вершин, а [math]q[/math] количество ребер.
5. [math]G[/math] — ацикличен и при добавлении любого ребра для несмежных вершин появляется один простой цикл.
6. [math]G[/math] — связный граф, отличный от [math] K_p [/math] для [math] p \gt 3 [/math] , а также при добавлении любого ребра для несмежных вершин появляется один простой цикл.
7. [math]G[/math] — граф, отличный от [math] K_3 \cup K_1 [/math] и [math] K_3 \cup K_2 [/math] , а также [math] p = q + 1 [/math] , где [math]p[/math] — количество вершин, а [math]q[/math] количество ребер, и при добавлении любого ребра для несмежных вершин появляется один простой цикл.

Доказательство эквивалентности

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

Очевидно, что граф связен. Докажем по индукции, соотношение [math]p = q + 1[/math] . Утверждение очевидно для связных графов с одной и двумя вершинами. Предположим, что оно верно для графов, имеющих меньше [math]p[/math] вершин. Если же граф [math]G[/math] имеет [math]p[/math] вершин, то удаление из него любого ребра делает граф [math] G [/math] несвязным в силу единственности простых цепей; более того, получаемый граф будет иметь в точности две компоненты. По предположению индукции в каждой компоненте число вершин на единицу больше числа ребер. Таким образом, [math] p = q + 1 [/math] .

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

[math]G[/math] — ациклический граф, значит каждая компонента связности графа является деревом. Так как в каждой из них вершин на единицу больше чем ребер, то [math] p = q + k [/math] , где [math]k[/math] — число компонент связности. Поскольку [math] p = q + k [/math] , то [math] k = 1 [/math] , а значит [math]G[/math] — связен. Таким образом наш граф — дерево, у которого между любой парой вершин есть единственный простой путь. Очевидно, при добавлении ребра появится второй путь между парой вершин, то есть мы получим цикл.

Поскольку [math] K_p [/math] для [math] p \gt 3 [/math] содержит простой цикл, то [math]G[/math] не может им являться. [math]G[/math] связен, так как в ином случае можно было бы добавить ребро так, что граф остался бы ациклическим.

Докажем, что любые две вершины графа соединены единственной простой цепью, а тогда поскольку [math] 2 \Rightarrow 3 [/math] , получим [math] p = q + 1 [/math] . Любые две вершины соединены простой цепью, так как [math]G[/math] — связен. Если две вершины соединены более чем одной простой цепью, то мы получим цикл. Причем он должен являться [math] K_3 [/math] , так как иначе добавив ребро, соединяющее две вершины цикла, мы получим более одного простого цикла, что противоречит условию. [math] K_3 [/math] является собственным подграфом [math]G[/math] , поскольку [math]G[/math] не является [math] K_p [/math] для [math] p \gt 3 [/math] . [math]G[/math] — связен, а значит есть вершина смежная с [math] K_3 [/math] . Очевидно, можно добавить ребро так, что образуется более одного простого цикла. Если нельзя добавить ребра так, чтобы не нарушалось исходное условие, то граф [math]G[/math] является [math]K_p[/math] для [math] p \gt 3 [/math] , и мы получаем противоречие с исходным условием. Значит, любые две вершины графа соединены единственной простой цепью, что и требовалось.

Если [math]G[/math] имеет простой цикл, то он является отдельной компонентой [math]K_3[/math] по ранее доказанному. Все остальные компоненты должны быть деревьями, но для выполнения соотношения [math] p = q + 1 [/math] должно быть не более одной компоненты отличной от [math]K_3[/math] , так как в [math]K_3[/math] [math] p = q = 3 [/math] . Если это дерево содержит простой путь длины 2, то в [math]G[/math] можно добавить ребро так, что образуются два простых цикла. Следовательно, этим деревом является [math]K_1[/math] или [math]K_2[/math] . Значит [math]G[/math] является [math]K_3 \cup K_1[/math] или [math]K_3 \cup K_2[/math] , которые мы исключили из рассмотрения. Значит наш граф ацикличен. Если [math]G[/math] ациклический и [math] p = q + 1 [/math] , то из [math] 4 \Rightarrow 5 [/math] и [math] 5 \Rightarrow 6 [/math] верно, что [math]G[/math] — связен. В итоге получаем, что [math]G[/math] является деревом по определению.

См. также

Источники информации

• Харари Ф. Теория графов. /пер. с англ. — изд. 2-е — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
• Википедия — дерево(теория графов)

Источник

Лекция № 15 Деревья Эквивалентные определения дерева

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

Существует несколько определений дерева.

1) Связный граф с n вершинами и n – 1 ребрами.

2) Связный граф без циклов.

3) Граф, в котором каждая пара вершин соединена точно одной цепью.

Докажем эквивалентность этих определений.

1)  2). Докажем, что в связном графе с n вершинами и n – 1 ребрами нет циклов. Предположим противное, т.е. цикл есть и e = (u, v) – ребро этого цикла. Удалим это ребро. Тогда граф останется связным, т.к. из u в v можно добраться по другой половинке цикла. В графе G\e n вершин, n – 2 ребер и он связан, т.е. у него 1 компонента связности, k = 1. По 3-й теореме о связности должно быть m = n – 2  n – 1 – противоречие. Следовательно, циклов нет.

2)  3). Хотя бы одна цепь, соединяющая u и v должна быть, т.к. граф связный. Предположим, что цепей не одна, а хотя бы две. Тогда, по свойству 3 маршрута, из них можно составить цикл – противоречие, т.е. 2-й цепи нет.

3)  1). Из 3) следует, что граф связный. Так как каждая пара вершин соединена точно одной цепью, то удаление любого ребра увеличит на 1 число компонент связности. Пусть в графе m ребер. По 3-й теореме о связности должно быть m  n – 1. Удалив 1 ребро, получим m – 1 n – 2, т.к. станет k = 2. Удалив 2 ребра, получим k = 3 и m – 2 n – 3, и т.д. Удалим n – 1 ребер, получим k = n и m – (n – 1) n – n. Но, т.к. k = n, то ребер больше нет. Следовательно, они были удалены за n – 1 шагов, поэтому m = n – 1, ЧТД.

Задание 1. Пусть Т – дерево, Т₁, Т₂ – его поддеревья. Доказать, что – тоже дерево.

Задание 2. В дереве n > 1. Доказать, что имеется по крайней мере 2 висячих вершины.

4.2. Остов

Def. Пусть G = (V, E) – неориентированный граф с n вершинами. Остовным деревом (остовом) графа G называется дерево T = (V, E₁), E₁  E.

Остов можно построить с помощью алгоритма поиска любого вида (в глубину и в ширину). Для этого во время поиска в G параллельно строится новый граф Т: если найдена новая еще непомеченная вершина u в списке инцидентности вершины v, то ребро (v, u) добавляется в строящийся граф. Если исходный граф несвязный, то задача не имеет решения.

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

Задача построения остова имеет большое прикладное значение. Она возникает при прокладке трасс и сетей коммуникаций, которые должны связать n заданных точек. Обычно требуют, чтобы остов обладал некоторым оптимальным свойством. Например, если каждое ребро имеет некоторый вес, то остов должен иметь минимальный вес.

Алгоритм Краскала. Этот алгоритм применяется для построения остова минимального веса. Пусть имеем граф G = (V, E), в котором каждому ребру присвоен вес (e) – некоторое вещественное число. Основная идея алгоритма: начиная с полностью несвязного графа Т = (V, ), присоединяем к нему ребра графа G в порядке возрастания их веса; если после присоединения очередного ребра в Т может образоваться цикл, то это ребро не присоединяем, а переходим к следующему. Можно доказать, что таким образом строится остов минимального веса.

Машинная реализация алгоритма Краскала. Сложность машинной реализации заключается в следующем.

1). Перед выполнением необходимо, чтобы ребра графа были отсортированы в порядке возрастания веса. Эта операция имеет сложность О(m 2 ), а если граф близок к полному, то О(n 4 ) – достаточно высокая.

2). Существенным моментом алгоритма является проверка на наличие цикла при добавлении ребра. В любом графе при добавлении ребра цикл появляется, если только присоединяемые ребра принадлежат одной компоненте связности. Следовательно, для контроля образования цикла необходимо каждой вершине приписать номер ее компоненты связности и следить, чтобы номера компонент двух соединяемых вершин всегда различались. После соединения вершин их компоненты связности сольются в одну, значит, надо соответствующим образом поменять их номера.

begin T:= ; for i:=1 to n do КОМП[i]:= i;

begin a:=НАЧАЛО[e[j]];

if КОМП[a] <> КОМП[b] then

begin Т:= T ;

if КОМП[i] = КОМП[b] then

КОМП[i] := КОМП[a];

end.Оценим вычислительную сложность без сортировки. Просмотр списка ребер – O(m) операций. Внутренний цикл по i от 1 до n – повторяется n – 1 раз, по числу добавляемых ребер. Итого О(m) + О(n 2 ) = О(n 2 ).

Источник