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

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

Текущая версия на 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] является деревом по определению.

См. также

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