Изменения

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

[[Файл:2 2tree_def_1.gifpng|300px|thumb|Пример дерева]]

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

[[Файл:2 3tree_def_2.gifpng|300px400px|thumb|Пример Примеры леса]] 

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

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

* <tex> 3 4 \Rightarrow 4 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> — связен. ПреположимТаким образом наш граф — дерево, что у нас которого между любой парой вершин есть p вершинединственный простой путь. Очевидно, и мы добавлеям при добавлении ребра. Если мы добавили ребро для получения цикла, то добавили появится второй путь между парой вершин, а значит нам не хватит его на добавление вершины и то есть мы получим не связный граф, что противоречит условиюцикл.

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

* <tex> 5 6 \Rightarrow 6 7 </tex> Поскольку :Докажем, что любые две вершины графа соединены единственной простой цепью, а тогда поскольку <tex> K_p 2 \Rightarrow 3 </tex> для , получим <tex> p \ge 3 = 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> K_3 </tex>. Очевидно, можно было бы добавить ребро так, что образуется более одного простого цикла. Если нельзя добавить ребра так, чтобы не нарушалось исходное условие, то граф остался бы ациклическим<tex>G</tex> является <tex>K_p</tex> для <tex> p > 3 </tex>, и мы получаем противоречие с исходным условием. Значит, любые две вершины графа соединены единственной простой цепью, что и требовалось.

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

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

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

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