Изменения

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

}}[[Файл:tree_def_1.png|300px|Пример дерева]]   {{Определение|definition ='''Лес''' (англ. ''forest'') {{--- объединение }} [[Основные определения теории графов|граф]], являющийся набором непересекающихся деревьев.}}[[Файл: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> количество ребер, и полный 3-х вершинный граф не является его подмножеством при добавлении любого ребра для несмежных вершин появляется один простой цикл.

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

<tex>1 2 \Rightarrow 23 </tex> Поскольку <tex>G</tex> связный :Очевидно, что граф, то любые две его вершины соединены простой цепьюсвязен. Пусть <tex>P_1</tex> и <tex>P_2</tex> - две различные простые цепиДокажем по индукции, соединяющие вершины соотношение <tex>up = q + 1</tex> . Утверждение очевидно для связных графов с одной и <tex>v</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_2p</tex>вершин. Если же граф <tex>w'</tex> - следующая за <tex>wG</tex> вершина в имеет <tex>P_1p</tex>вершин, принадлежащая также то удаление из него любого ребра делает граф <tex>P_2G </tex>, то сегменты (части) несвязным в силу единственности простых цепей <tex>P_1</tex> и <tex>P_2</tex>; более того, находящиеся между вершинами <tex>w</tex> и <tex>w'</tex>, образуют простой цикл получаемый граф будет иметь в точности две компоненты. По предположению индукции в графе <tex>G</tex>каждой компоненте число вершин на единицу больше числа ребер. Поэтому если Таким образом, <tex>Gp = q + 1 </tex> - ациклический граф, то между любыми двумя его вершинами существует самое большое одна цепь.

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

<tex>3 4 \Rightarrow 45 </tex> Предположим, что в графе :<tex>G</tex> есть простой цикл длины — ациклический граф, значит каждая компонента связности графа является деревом. Так как в каждой из них вершин на единицу больше чем ребер, то <tex>np = q + k </tex>. Этот цикл содержит , где <tex>nk</tex> вершин и — число [[Отношение связности, компоненты связности|компонент связности]]. Поскольку <tex>np = q + k </tex> ребер, а для любой из то <tex>p - nk = 1 </tex> вершин, не принадлежащих циклу,существует инцидентное ей ребро, которое лежит на геодезической , идущей от некоторой вершины цикла. Все такие ребра попарно различны; отсюда а значит <tex>q \ge pG</tex>— связен. Таким образом наш граф — дерево, ту которого между любой парой вершин есть единственный простой путь. е. пришли к противоречиюОчевидно, при добавлении ребра появится второй путь между парой вершин, то есть мы получим цикл.

<tex>4 5 \Rightarrow 6 </tex> :Поскольку <tex> K_p </tex> для <tex> p > 3 </tex> содержит простой цикл, то <tex>G</tex> не может им являться. <tex>G</tex> связен, так как в ином случае можно было бы добавить ребро так, что граф остался бы ациклическим. <tex> 6 \Rightarrow 7 </tex> :Докажем, что любые две вершины графа соединены единственной простой цепью, а тогда поскольку <tex> 2 \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>kG</tex> компонент связности— связен, и та значит есть вершина смежная с <tex> K_3 </tex>. кОчевидно, можно добавить ребро так, что образуется более одного простого цикла. граф ациклическийЕсли нельзя добавить ребра так, чтобы не нарушалось исходное условие, то каждая компонента связности граф <tex>G</tex> является деревом<tex>K_p</tex> для <tex> p > 3 </tex>, и мы получаем противоречие с исходным условием. Ввиду тогоЗначит, любые две вершины графа соединены единственной простой цепью, что и требовалось. <tex>1 7 \Rightarrow 31 </tex> :Если <tex>G</tex> имеет простой цикл, то он является отдельной компонентой <tex>K_3</tex> по ранее доказанному. Все остальные компоненты должны быть деревьями, но для выполнения соотношения <tex>p = q + 1 </tex> должно быть не более одной компоненты отличной от <tex>K_3</tex>, так как в <tex>K_3</tex> <tex> p = \sum \limits_{i q = 1}^k (p_i - 1) = p - k3 </tex>. Если это дерево содержит простой путь длины 2, то в <tex>G</tex>можно добавить ребро так, что образуются два простых цикла. Следовательно, где этим деревом является <tex>p_iK_1</tex> - количество вершин в или <tex>iK_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>k = 1G</tex> — связен. В итоге получаем, т. е. что <tex>G</tex> - деревоявляется деревом по определению.}}==См. также==* [[Алгоритмы на деревьях|Алгоритмы на деревьях]]* [[Дерево поиска, наивная реализация|Двоичное дерево поиска]]

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

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