Изменения

Ациклический граф '''Дерево''' (англ. ''tree'') {{--- }} связный ациклический [[Основные определения теории графов|граф, в котором нет циклов]]. 

Дерево '''Лес''' (англ. ''forest'') {{- это связный ациклический --}} [[Основные определения теории графов|граф]], являющийся набором непересекающихся деревьев.

{{Определение[[Файл:tree_def_2.png|400px|Примеры леса]] ==Определения==Для графа <tex>G</tex> эквивалентны следующие утверждения:# <tex>G</tex> — дерево.# Любые две вершины графа <tex>G</tex> соединены единственным простым путем.# <tex>G</tex> — связен и <tex> p = q + 1 </tex>, где <tex>p</tex> — количество вершин, а <tex>q</tex> количество ребер.# <tex>G</tex> — ацикличен и <tex> p = q + 1 </tex>, где <tex>p</tex> — количество вершин, а <tex>q</tex> количество ребер.# <tex>G</tex> — ацикличен и при добавлении любого ребра для [[Основные определения теории графов|definition несмежных вершин]] появляется один простой [[Основные определения теории графов|цикл]].# <tex>G</tex> — связный граф, отличный от <tex> K_p </tex> для <tex> p > 3 </tex>, а также при добавлении любого ребра для несмежных вершин появляется один простой цикл.# <tex>G</tex> — граф, отличный от <tex> K_3 \cup K_1 </tex> и <tex> K_3 \cup K_2 </tex>, а также <tex> p =q + 1 </tex>, где <tex>p</tex> — количество вершин, а <tex>q</tex> количество ребер, и при добавлении любого ребра для несмежных вершин появляется один простой цикл. ==Доказательство эквивалентности==<tex> 1 \Rightarrow 2 </tex> :Графсвязен, поэтому любые две вершнины соединены путем. Граф ацикличен, значит путь единственен, а также [[Теорема о существовании простого пути в случае существования пути|прост]], поскольку никакой путь не содержащий цикловможет зайти в одну вершину два раза, называется лесомпотому что это противоречит ацикличности. }}{{Теорема<tex> 2 \Rightarrow 3 </tex> |statement:Очевидно, что граф связен. Докажем по индукции, соотношение <tex>p =Для графа q + 1</tex>. Утверждение очевидно для связных графов с одной и двумя вершинами. Предположим, что оно верно для графов, имеющих меньше <tex>p</tex> вершин. Если же граф <tex>G</tex> следующие утверждения эквивалентны:1) имеет <tex>p</tex> вершин, то удаление из него любого ребра делает граф <tex>G</tex> - деревонесвязным в силу единственности простых цепей;более того, получаемый граф будет иметь в точности две компоненты. По предположению индукции в каждой компоненте число вершин на единицу больше числа ребер. Таким образом, <tex> p = q + 1 </tex>.

2) любые две вершины в <tex>G3 \Rightarrow 4 </tex>соединены единственной простой цепью;:Очевидно, что если граф связен и ребер на одно меньше, чем вершин, то он ацикличен. Преположим, что у нас есть p вершин, и мы добавляем ребра. Если мы добавили ребро для получения цикла, то добавили второй путь между парой вершин, а значит нам не хватит его на добавление вершины и мы получим не связный граф, что противоречит условию.

3) <tex> 4 \Rightarrow 5 </tex> :<tex>G</tex> связный — ациклический граф и , значит каждая компонента связности графа является деревом. Так как в каждой из них вершин на единицу больше чем ребер, то <tex> p = q + k </tex>, где <tex>k</tex> — число [[Отношение связности, компоненты связности|компонент связности]]. Поскольку <tex>p = q + k </tex>, то <tex> k = 1</tex>;, а значит <tex>G</tex> — связен. Таким образом наш граф — дерево, у которого между любой парой вершин есть единственный простой путь. Очевидно, при добавлении ребра появится второй путь между парой вершин, то есть мы получим цикл.

4) <tex> 5 \Rightarrow 6 </tex> :Поскольку <tex> K_p </tex> для <tex> p > 3 </tex> содержит простой цикл, то <tex>G</tex> ациклический граф и не может им являться. <tex>p = q + 1G</tex>;связен, так как в ином случае можно было бы добавить ребро так, что граф остался бы ациклическим.

5) <tex> 6 \Rightarrow 7 </tex> :Докажем, что любые две вершины графа соединены единственной простой цепью, а тогда поскольку <tex> 2 \Rightarrow 3 </tex>, получим <tex> p = q + 1 </tex>. Любые две вершины соединены простой цепью, так как <tex>G</tex> — связен. Если две вершины соединены более чем одной простой цепью, то мы получим цикл. Причем он должен являться <tex> K_3 </tex>, так как иначе добавив ребро, соединяющее две вершины цикла, мы получим более одного простого цикла, что противоречит условию. <tex> K_3 </tex> является собственным подграфом <tex>G</tex>, поскольку <tex>G</tex> - ациклический графне является <tex> K_p </tex> для <tex> p > 3 </tex>. <tex>G</tex> — связен, и если любую праву несмежных вершин соединить ребром а значит есть вершина смежная с <tex>xK_3 </tex>. Очевидно, можно добавить ребро так, что образуется более одного простого цикла. Если нельзя добавить ребра так, чтобы не нарушалось исходное условие, то в графе граф <tex>G + x</tex> будет точно один является <tex>K_p</tex> для <tex> p > 3 </tex>, и мы получаем противоречие с исходным условием. Значит, любые две вершины графа соединены единственной простой цикл;цепью, что и требовалось.

6) <tex> 7 \Rightarrow 1 </tex> :Если <tex>G</tex> - связный графимеет простой цикл, то он является отдельной компонентой <tex>K_3</tex> по ранее доказанному. Все остальные компоненты должны быть деревьями, отличный но для выполнения соотношения <tex> p = q + 1 </tex> должно быть не более одной компоненты отличной от K<subtex>K_3</tex>, так как в <tex>K_3</tex> <tex>p= q = 3 </tex>. Если это дерево содержит простой путь длины 2, то в <tex>G</tex> можно добавить ребро так, что образуются два простых цикла. Следовательно, этим деревом является <tex>K_1</tex> или <tex>K_2</tex>. Значит <tex>G</subtex> для является <tex>K_3 \cup K_1</tex> или <tex>p K_3 \ge 3cup K_2</tex>, которые мы исключили из рассмотрения. Значит наш граф ацикличен. Если <tex>G</tex> ациклический и если любую пару несмежных вершин соединить ребром <tex>xp = q + 1 </tex>, то в графе из <tex> 4 \Rightarrow 5 </tex> и <tex> 5 \Rightarrow 6 </tex> верно, что <tex>G</tex> — связен. В итоге получаем, что <tex>G + x</tex> будет точно один простой цикл;является деревом по определению.

7) <tex>G</tex> - Граф, отличный от K₃ <tex>\cup</tex> K₁ и K₃<tex>\cup</tex> K₂, <tex>p = q + 1</tex>, и если любую пару несмежных вершин соединить ребром <tex>x</tex>, то в графе <tex>G + x</tex> будет точно один простой цикл=См.также==* [[Алгоритмы на деревьях|proof= Алгоритмы на деревьях]]* [[Дерево поиска, наивная реализация|Двоичное дерево поиска]]

* '''Следствие'Харари Ф.''Теория графов. /пер. с англ. — изд. 2-е — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6* [http://en.wikipedia.org/wiki/Tree_(graph_theory) Википедия {{---}} дерево(теория графов)]