Изменения

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

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

Для графа <tex>G эвивалентны следущие </tex> эквивалентны следующие утверждения:# <tex>G - </tex> — дерево.# Любые две вершины графа <tex>G </tex> соединены единственным простым путем.# <tex>G - </tex> — связени <tex> p = q + 1 </tex>, количество вершин где <tex>np</tex>— количество вершин, а ребер <tex> n - 1 q</tex>количество ребер.# <tex>G - </tex> — ацикличени <tex> p = q + 1 </tex>, количество вершин где <tex>np</tex>— количество вершин, а ребер <tex>n - 1q</tex>количество ребер.# <tex>G - </tex> — ацикличен, и при добавлении любого ребра для [[Основные определения теории графов|несмежных вершин ]] появляется один простой [[Основные определения теории графов|цикл]].# <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>np</tex>— количество вершин, а ребер <tex>n - 1q</tex>количество ребер, и при добавлении любого ребра для несмежных вершин появляется один простой цикл.

<tex> 1 \Rightarrow 2 </tex> :Граф связен, поэтому любые две вершнины соединены путем. Граф ацикличен, значит путь единственен, а также [[Теорема о существовании простого пути в случае существования пути|прост]], поскольку никакой путь не может зайти в одну вершину два раза, потому что это противоречит ацикличности. <tex> 2 \Rightarrow 3 </tex> :Очевидно, что граф связен. Докажем эквивалентность по индукции, соотношение <tex>p = q + 1 определения </tex>. Утверждение очевидно для связных графов с остальнымиодной и двумя вершинами. Предположим, что оно верно для графов, имеющих меньше <tex>p</tex> вершин. Если же граф <tex>G</tex> имеет <tex>p</tex> вершин, то удаление из него любого ребра делает граф <tex> G </tex> несвязным в силу единственности простых цепей; более того, получаемый граф будет иметь в точности две компоненты. По предположению индукции в каждой компоненте число вершин на единицу больше числа ребер. Таким образом, <tex> p = q + 1 </tex>. <tex> 3 \Rightarrow 4 </tex> :Очевидно, что если граф связен и ребер на одно меньше, чем вершин, то он ацикличен. Преположим, что у нас есть p вершин, и мы добавляем ребра. Если мы добавили ребро для получения цикла, то добавили второй путь между парой вершин, а значит нам не хватит его на добавление вершины и мы получим не связный граф, что противоречит условию. <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> — связен. Таким образом наш граф — дерево, у которого между любой парой вершин есть единственный простой путь. Очевидно, при добавлении ребра появится второй путь между парой вершин, то есть мы получим цикл.

* <tex> 1 5 \Rightarrow 2 6 </tex> Связность:Поскольку <tex> K_p </tex> для <tex> p > 3 </tex> содержит простой цикл, очевидно, вытекает из существования пути между любыми двумя вершинами, а ацикличность из единственностито <tex>G</tex> не может им являться. Повторив эти рассуждения в обратном порядке получим <tex> 1 \Leftarrow 2 G</tex>связен, так как в ином случае можно было бы добавить ребро так, что граф остался бы ациклическим.

* <tex> 1 6 \Rightarrow 7 </tex> :Докажем, что любые две вершины графа соединены единственной простой цепью, а тогда поскольку <tex> 2 \Rightarrow 3 </tex> Ацикличность получаем аналогично первому пункту, получим <tex> p = q + 1 </tex>. Теперь рассмотрим Любые две вершины соединены простой цепью, так как <tex> u G</tex> и — связен. Если две вершины соединены более чем одной простой цепью, то мы получим цикл. Причем он должен являться <tex> v K_3 </tex> такие, так как иначе добавив ребро, соединяющее две вершины цикла, мы получим более одного простого цикла, что ребра противоречит условию. <tex> K_3 </tex> является собственным подграфом <tex>G</tex>, поскольку <tex> uv G</tex> не существуетявляется <tex> K_p </tex> для <tex> p > 3 </tex>. Между ними<tex>G</tex> — связен, как мы знаема значит есть вершина смежная с <tex> K_3 </tex>. Очевидно, уже существует путьможно добавить ребро так, и при добавлении нового ребра мы получим второй путь. Из существования двух различных путей вытекает существование что образуется более одного простого цикла. Опять же повторив эти рассуждения в обратном порядке получим Если нельзя добавить ребра так, чтобы не нарушалось исходное условие, то граф <tex>G</tex> является <tex>K_p</tex> для <tex> 1 \Leftarrow p > 3 </tex>, и мы получаем противоречие с исходным условием. Значит, любые две вершины графа соединены единственной простой цепью, что и требовалось.

* <tex> 1 7 \Rightarrow 4 1 </tex> :Если <tex>G</tex> имеет простой цикл, то он является отдельной компонентой <tex>K_3</tex> Связность аналогично первому пунктупо ранее доказанному. Теперь рассмотрим Все остальные компоненты должны быть деревьями, но для выполнения соотношения <tex> u p = q + 1 </tex> и должно быть не более одной компоненты отличной от <tex> v K_3</tex> такие, что ребро так как в <tex>K_3</tex> <tex> uv p = q = 3 </tex> существует. Мы знаемЕсли это дерево содержит простой путь длины 2, то в <tex>G</tex> можно добавить ребро так, что это единственный путь из образуются два простых цикла. Следовательно, этим деревом является <tex>K_1</tex> или <tex>K_2</tex>. Значит <tex>G</tex> является <tex> u K_3 \cup K_1</tex> в или <tex> v K_3 \cup K_2</tex>, значит после удаления ребра которые мы исключили из рассмотрения. Значит наш граф ацикличен. Если <tex>G</tex> ациклический и <tex> v p = q + 1 </tex> станет не достижимо , то из <tex> u 4 \Rightarrow 5 </tex> и наоборот<tex> 5 \Rightarrow 6 </tex> верно, что означает утерю связности<tex>G</tex> — связен. Опять же повторив эти рассуждения в обратном порядке получим В итоге получаем, что <tex> 1 \Leftarrow 4 G</tex>является деревом по определению.

Получив эквивалентность всех утверждений первому==См. также==* [[Алгоритмы на деревьях|Алгоритмы на деревьях]]* [[Дерево поиска, по транзитивности автоматически получим эквивалентность остальных утверждений.наивная реализация|Двоичное дерево поиска]]

==ЛитератураИсточники информации==

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