Изменения

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

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

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

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

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

|proof= * <tex> 1 2 \Rightarrow 2 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> 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> p = q + k </tex>, где <tex>k</tex> — число [[Отношение связности, компоненты связности|компонент связности]]. Поскольку <tex> p = q + k 3 </tex>содержит простой цикл, то <tex> k = 1 G</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>GK_3</tex> <tex> p = q = 3 </tex> — связен. Если две вершины соединены более чем одной это дерево содержит простой цепьюпуть длины 2, то мы получим цикл. Причем он должен являться в <tex> K_3 G</tex>, можно добавить ребро так как иначе добавив ребро, соединяющее две вершины что образуются два простых цикла. Следовательно, мы получим более одного простого цикла, что противоречит условию. этим деревом является <tex> K_3 K_1</tex> является собственным подграфом или <tex>GK_2</tex>, поскольку . Значит <tex>G</tex> не является <tex> K_p K_3 \cup K_1</tex> для или <tex> p K_3 \ge 3 cup K_2</tex>, которые мы исключили из рассмотрения. Значит наш граф ацикличен. Если <tex>G</tex> — связен, а значит есть вершина смежная с ациклический и <tex> K_3 p = q + 1 </tex>. Очевидно, можно добавить ребро так, что образуется более одного простого цикла. Если нельзя добавить ребра так, чтобы не нарушалось исходное условие, то граф из <tex>G4 \Rightarrow 5 </tex> является и <tex>K_p5 \Rightarrow 6 </tex> для верно, что <tex> p \ge 3 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> можно добавить ребро так, что образуются два простых цикла. Следовательно, этим деревом является <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> является деревом по определению.наивная реализация|Двоичное дерево поиска]]}}==ЛитератураИсточники информации==

* [http://en.wikipedia.org/wiki/Tree_(graph_theory) Википедия — свободная энциклопедия{{---}} дерево(теория графов)]