Изменения

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

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

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

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

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

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

==См. также==* <tex> 6 \Rightarrow 7 </tex>[[Алгоритмы на деревьях|Алгоритмы на деревьях]]* [[Дерево поиска, наивная реализация|Двоичное дерево поиска]]

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

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