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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство эквивалентности)
(Определения)
Строка 13: Строка 13:
 
# G - связен и <tex> p = q + 1 </tex>, где <tex>p</tex> - количество вершин, а <tex>q</tex> количество ребер
 
# G - связен и <tex> p = q + 1 </tex>, где <tex>p</tex> - количество вершин, а <tex>q</tex> количество ребер
 
# G - ацикличен и  <tex> p = q + 1 </tex>, где <tex>p</tex> - количество вершин, а <tex>q</tex> количество ребер
 
# G - ацикличен и  <tex> p = q + 1 </tex>, где <tex>p</tex> - количество вершин, а <tex>q</tex> количество ребер
# G - ацикличен и при добавлении любого ребра для несмежных вершин появляется цикл
+
# G - ацикличен и при добавлении любого ребра для несмежных вершин появляется простой цикл
# G - связный граф, отличный от <tex> K_p </tex> для <tex> p \ge 3 </tex>, а также при добавлении любого ребра для несмежных вершин появляется цикл
+
# G - связный граф, отличный от <tex> K_p </tex> для <tex> p \ge 3 </tex>, а также при добавлении любого ребра для несмежных вершин появляется простой цикл
# G - граф, отличный от <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> количество ребер, и при добавлении любого ребра для несмежных вершин появляется цикл
+
# G - граф, отличный от <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> количество ребер, и при добавлении любого ребра для несмежных вершин появляется простой цикл
  
 
==Доказательство эквивалентности==
 
==Доказательство эквивалентности==

Версия 02:50, 27 ноября 2011

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


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

Определения

Для графа G эвивалентны следущие утверждения:

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

Литература

  • Харари Фрэнк Теория графов = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
  • Википедия — свободная энциклопедия