Дерево, эквивалентные определения — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Теорема)
м (rollbackEdits.php mass rollback)
 
(не показано 79 промежуточных версий 8 участников)
Строка 1: Строка 1:
== Определения ==
 
 
{{Определение
 
{{Определение
 +
|id = tree
 
|definition =
 
|definition =
'''Ациклический граф (лес)''' - граф, в котором нет циклов.
+
'''Дерево''' (англ. ''tree'') {{---}} связный ациклический [[Основные определения теории графов|граф]].
 +
 
 
}}
 
}}
 +
[[Файл:tree_def_1.png|300px|Пример дерева]]
 +
 +
 +
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Дерево''' - это связный ациклический граф.
+
'''Лес''' (англ. ''forest'') {{---}} [[Основные определения теории графов|граф]], являющийся набором непересекающихся деревьев.
 
}}
 
}}
 +
[[Файл:tree_def_2.png|400px|Примеры леса]]
  
==Теорема==
+
==Определения==
{{Теорема
+
Для графа <tex>G</tex> эквивалентны следующие утверждения:
|statement=
+
# <tex>G</tex> — дерево.
Для графа <tex>G</tex> с <tex>p</tex> вершинами и <tex>q</tex> ребрами следующие утверждения эквивалентны:
+
# Любые две вершины графа <tex>G</tex> соединены единственным простым путем.
1) <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> количество ребер, и при добавлении любого ребра для несмежных вершин появляется один простой цикл.
  
2) любые две вершины в <tex>G</tex> соединены единственной простой цепью;
+
==Доказательство эквивалентности==
 +
<tex> 1 \Rightarrow 2 </tex>  
 +
:Граф связен, поэтому любые две вершнины соединены путем. Граф ацикличен, значит путь единственен, а также [[Теорема о существовании простого пути в случае существования пути|прост]], поскольку никакой путь не может зайти в одну вершину два раза, потому что это противоречит ацикличности.
  
3) <tex>G</tex> связный граф и <tex>p = q + 1</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>.
  
4) <tex>G</tex> ациклический граф и <tex>p = q + 1</tex>;
+
<tex> 3 \Rightarrow 4 </tex>  
 +
:Очевидно, что если граф связен и ребер на одно меньше, чем вершин, то он ацикличен. Преположим, что у нас есть p вершин, и мы добавляем ребра. Если мы добавили ребро для получения цикла, то добавили второй путь между парой вершин, а значит нам не хватит его на добавление вершины и мы получим не связный граф, что противоречит условию.
  
5) <tex>G</tex> - ациклический граф, и если любую праву несмежных вершин соединить ребром <tex>x</tex>, то в графе <tex>G + x</tex> будет точно один простой цикл;
+
<tex> 4 \Rightarrow 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> — связен. Таким образом наш граф — дерево, у которого между любой парой вершин есть единственный простой путь. Очевидно, при добавлении ребра появится второй путь между парой вершин, то есть мы получим цикл.
  
6) <tex>G</tex> - связный граф, отличный от <tex>K_p</tex> для <tex>p \ge 3</tex>, и если любую пару несмежных вершин соединить ребром <tex>x</tex>, то в графе <tex>G + x</tex> будет точно один простой цикл;
+
<tex> 5 \Rightarrow 6 </tex>  
 +
:Поскольку <tex> K_p </tex> для <tex> p > 3 </tex> содержит простой цикл, то <tex>G</tex> не может им являться. <tex>G</tex> связен,  так как в ином случае можно было бы добавить ребро так, что граф остался бы ациклическим.
  
7) <tex>G</tex> - Граф, отличный от <tex>K_3 \cup K_1</tex> и <tex>K_3\cup K_2</tex>, <tex>p = q + 1</tex>, и если любую пару несмежных вершин соединить ребром <tex>x</tex>, то в графе <tex>G + x</tex> будет точно один простой цикл.
+
<tex> 6 \Rightarrow 7 </tex>
|proof=
+
:Докажем, что любые две вершины графа соединены единственной простой цепью, а тогда поскольку <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>G</tex> — связен, а значит есть вершина смежная с <tex> K_3 </tex>. Очевидно, можно добавить ребро так, что образуется более одного простого цикла. Если нельзя добавить ребра так, чтобы не нарушалось исходное условие, то граф <tex>G</tex> является <tex>K_p</tex> для <tex> p > 3 </tex>, и мы получаем противоречие с исходным условием. Значит, любые две вершины графа соединены единственной простой цепью, что и требовалось.
Для примера докажем эквивалентность первых четырёх утверждений.
 
  
<tex>1) \Rightarrow 2)</tex> Поскольку <tex>G</tex> связный граф, то любые две его вершины соединены простой цепью. Пусть <tex>P_1</tex> и <tex>P_2</tex> - две различные простые цепи, соединяющие вершины <tex>u</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_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> 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> является деревом по определению.
  
<tex>2) \Rightarrow 3)</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) \Rightarrow 4)</tex> Предположим, что в графе <tex>G</tex> есть простой цикл длины <tex>n</tex>. Этот цикл содержит <tex>n</tex> вершин и <tex>n</tex> ребер, а для любой из <tex>p - n</tex> вершин, не принадлежащих циклу,существует инцидентное ей ребро, которое лежит на геодезической , идущей от некоторой вершины цикла. Все такие ребра попарно различны; отсюда <tex>q \ge p</tex>, т. е. пришли к противоречию.
+
==Источники информации==
 
 
<tex>4) \Rightarrow 1)</tex> Предположим граф <tex>G</tex> имеет <tex>k</tex> компонент связности, и т. к. граф ациклический, то каждая компонента связности является деревом. Ввиду того, что 1) <tex> \to </tex> 3) <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> - дерево.
 
}}
 
  
==Литература==
+
* ''Харари Ф.'' Теория графов. /пер. с англ. — изд. 2-е — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
 +
* [http://en.wikipedia.org/wiki/Tree_(graph_theory) Википедия {{---}} дерево(теория графов)]
  
* Харари Фрэнк '''Теория графов''' = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
+
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Основные определения теории графов]]

Текущая версия на 19:36, 4 сентября 2022

Определение:
Дерево (англ. tree) — связный ациклический граф.

Пример дерева



Определение:
Лес (англ. forest) — граф, являющийся набором непересекающихся деревьев.

Примеры леса

Определения

Для графа [math]G[/math] эквивалентны следующие утверждения:

  1. [math]G[/math] — дерево.
  2. Любые две вершины графа [math]G[/math] соединены единственным простым путем.
  3. [math]G[/math] — связен и [math] p = q + 1 [/math], где [math]p[/math] — количество вершин, а [math]q[/math] количество ребер.
  4. [math]G[/math] — ацикличен и [math] p = q + 1 [/math], где [math]p[/math] — количество вершин, а [math]q[/math] количество ребер.
  5. [math]G[/math] — ацикличен и при добавлении любого ребра для несмежных вершин появляется один простой цикл.
  6. [math]G[/math] — связный граф, отличный от [math] K_p [/math] для [math] p \gt 3 [/math], а также при добавлении любого ребра для несмежных вершин появляется один простой цикл.
  7. [math]G[/math] — граф, отличный от [math] K_3 \cup K_1 [/math] и [math] K_3 \cup K_2 [/math], а также [math] p = q + 1 [/math], где [math]p[/math] — количество вершин, а [math]q[/math] количество ребер, и при добавлении любого ребра для несмежных вершин появляется один простой цикл.

Доказательство эквивалентности

[math] 1 \Rightarrow 2 [/math]

Граф связен, поэтому любые две вершнины соединены путем. Граф ацикличен, значит путь единственен, а также прост, поскольку никакой путь не может зайти в одну вершину два раза, потому что это противоречит ацикличности.

[math] 2 \Rightarrow 3 [/math]

Очевидно, что граф связен. Докажем по индукции, соотношение [math]p = q + 1[/math]. Утверждение очевидно для связных графов с одной и двумя вершинами. Предположим, что оно верно для графов, имеющих меньше [math]p[/math] вершин. Если же граф [math]G[/math] имеет [math]p[/math] вершин, то удаление из него любого ребра делает граф [math] G [/math] несвязным в силу единственности простых цепей; более того, получаемый граф будет иметь в точности две компоненты. По предположению индукции в каждой компоненте число вершин на единицу больше числа ребер. Таким образом, [math] p = q + 1 [/math].

[math] 3 \Rightarrow 4 [/math]

Очевидно, что если граф связен и ребер на одно меньше, чем вершин, то он ацикличен. Преположим, что у нас есть p вершин, и мы добавляем ребра. Если мы добавили ребро для получения цикла, то добавили второй путь между парой вершин, а значит нам не хватит его на добавление вершины и мы получим не связный граф, что противоречит условию.

[math] 4 \Rightarrow 5 [/math]

[math]G[/math] — ациклический граф, значит каждая компонента связности графа является деревом. Так как в каждой из них вершин на единицу больше чем ребер, то [math] p = q + k [/math], где [math]k[/math] — число компонент связности. Поскольку [math] p = q + k [/math], то [math] k = 1 [/math], а значит [math]G[/math] — связен. Таким образом наш граф — дерево, у которого между любой парой вершин есть единственный простой путь. Очевидно, при добавлении ребра появится второй путь между парой вершин, то есть мы получим цикл.

[math] 5 \Rightarrow 6 [/math]

Поскольку [math] K_p [/math] для [math] p \gt 3 [/math] содержит простой цикл, то [math]G[/math] не может им являться. [math]G[/math] связен, так как в ином случае можно было бы добавить ребро так, что граф остался бы ациклическим.

[math] 6 \Rightarrow 7 [/math]

Докажем, что любые две вершины графа соединены единственной простой цепью, а тогда поскольку [math] 2 \Rightarrow 3 [/math], получим [math] p = q + 1 [/math]. Любые две вершины соединены простой цепью, так как [math]G[/math] — связен. Если две вершины соединены более чем одной простой цепью, то мы получим цикл. Причем он должен являться [math] K_3 [/math], так как иначе добавив ребро, соединяющее две вершины цикла, мы получим более одного простого цикла, что противоречит условию. [math] K_3 [/math] является собственным подграфом [math]G[/math], поскольку [math]G[/math] не является [math] K_p [/math] для [math] p \gt 3 [/math]. [math]G[/math] — связен, а значит есть вершина смежная с [math] K_3 [/math]. Очевидно, можно добавить ребро так, что образуется более одного простого цикла. Если нельзя добавить ребра так, чтобы не нарушалось исходное условие, то граф [math]G[/math] является [math]K_p[/math] для [math] p \gt 3 [/math], и мы получаем противоречие с исходным условием. Значит, любые две вершины графа соединены единственной простой цепью, что и требовалось.

[math] 7 \Rightarrow 1 [/math]

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

См. также

Источники информации