Изменения

В теории графов {{Определение|id = tree|definition ='''Дерево''' (англ. ''tree'') {{--- неориентированный }} связный ациклический [[Основные определения теории графов|граф, в котором две любых вершины соединены единственным простым путем]]. Другими словами, любой связный граф без циклов дерево }}[[Файл:tree_def_1. png|300px|Пример дерева]]

2{{Определение|definition ='''Лес''' (англ. ''forest'') любые две вершины в <tex>G</tex> соединены единственной простой цепью;{{---}} [[Основные определения теории графов|граф]], являющийся набором непересекающихся деревьев.}}[[Файл: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> — ацикличен и при добавлении любого ребра для [[Основные определения теории графов|несмежных вершин]] появляется один простой [[Основные определения теории графов|цикл]].# <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> количество ребер, и при добавлении любого ребра для несмежных вершин появляется один простой цикл.

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

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

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

7) <tex> 4 \Rightarrow 5 </tex> :<tex>G</tex> - Граф— ациклический граф, значит каждая компонента связности графа является деревом. Так как в каждой из них вершин на единицу больше чем ребер, отличный от то <tex>K_3 \cup K_1p = q + k </tex> и , где <tex>K_3\cup K_2k</tex>— число [[Отношение связности, компоненты связности|компонент связности]]. Поскольку <tex>p = q + 1k </tex>, и если любую пару несмежных вершин соединить ребром то <tex>xk = 1 </tex>, то в графе а значит <tex>G + x</tex> будет точно один — связен. Таким образом наш граф — дерево, у которого между любой парой вершин есть единственный простой путь. Очевидно, при добавлении ребра появится второй путь между парой вершин, то есть мы получим цикл.|proof= Для примера докажем эквивалентность первых четырёх утверждений.

<tex>1 5 \Rightarrow 26 </tex> :Поскольку <tex>GK_p </tex> связный граф, то любые две его вершины соединены простой цепью. Пусть <tex>P_1для </tex> и <texp >P_23 </tex> - две различные простые цеписодержит простой цикл, соединяющие вершины то <tex>uG</tex> и не может им являться. <tex>vG</tex>связен, и пусть <tex>w</tex> - первая вершина, принадлежащая <tex>P_1</tex> (при переходе по <tex>P_1</tex> из <tex>u</tex> так как в <tex>v</tex>), такаяином случае можно было бы добавить ребро так, что <tex>w</tex> принадлежит и <tex>P_1</tex> и <tex>P_2</tex>, но вершина, предшествующая ей в <tex>P_1</tex>, не принадлежит <tex>P_2</tex>. Если <tex>w'</tex> - следующая за <tex>w</tex> вершина в <tex>P_1</tex>, принадлежащая также <tex>P_2</tex>, то сегменты (части) цепей <tex>P_1</tex> и <tex>P_2</tex>, находящиеся между вершинами <tex>w</tex> и <tex>w'</tex>, образуют простой цикл в графе <tex>G</tex>. Поэтому если <tex>G</tex> - ациклический граф, то между любыми двумя его вершинами существует самое большое одна цепьостался бы ациклическим.

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

<tex>3 7 \Rightarrow 41 </tex> Предположим, что в графе :Если <tex>G</tex> есть имеет простой цикл длины , то он является отдельной компонентой <tex>nK_3</tex>по ранее доказанному. Этот цикл содержит Все остальные компоненты должны быть деревьями, но для выполнения соотношения <tex>np = q + 1 </tex> вершин и должно быть не более одной компоненты отличной от <tex>nK_3</tex> ребер, а для любой из так как в <tex>K_3</tex> <tex>p - n= 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 \ge pRightarrow 6 </tex>верно, тчто <tex>G</tex> — связен. е. пришли к противоречиюВ итоге получаем, что <tex>G</tex> является деревом по определению.

<tex>4 \Rightarrow 1</tex> Предположим граф <tex>G</tex> имеет <tex>k</tex> компонент связности, и т. к. граф ациклический, то каждая компонента связности является деревом. Ввиду того, что <tex>1 \Rightarrow 3</tex> <tex>q = \sum \limits_{i = 1}^k (p_i - 1) = p - k</tex>, где <tex>p_i</tex> - количество вершин в <tex>i</tex>-й компоненте связностиСм. Учитывая, что <tex>p также= q + 1</tex>, получаем, что <tex>k = 1</tex>* [[Алгоритмы на деревьях|Алгоритмы на деревьях]]* [[Дерево поиска, т. е. <tex>G</tex> - наивная реализация|Двоичное дерево.}}поиска]]

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

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