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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство эквивалентности)
(Доказательство эквивалентности)
Строка 20: Строка 20:
 
* <tex> 1 \Rightarrow 2 </tex> Граф связен, значит любые две вершнины соединены путем, ацикличен, значит путь единственен, а так же прост, так как никакой путь не может зайти в одну вершину два раза, потому что это противоречит ацикличности.
 
* <tex> 1 \Rightarrow 2 </tex> Граф связен, значит любые две вершнины соединены путем, ацикличен, значит путь единственен, а так же прост, так как никакой путь не может зайти в одну вершину два раза, потому что это противоречит ацикличности.
  
* <tex> 2 \Rightarrow 3 </tex>
+
* <tex> 2 \Rightarrow 3 </tex> Очевидно, граф связен. Докажем по индукции, соотношение <tex>p = q + 1</tex>
  
 
* <tex> 3 \Rightarrow 4 </tex>
 
* <tex> 3 \Rightarrow 4 </tex>

Версия 20:48, 24 ноября 2011

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


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

Определения

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

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

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

  • [math] 1 \Rightarrow 2 [/math] Граф связен, значит любые две вершнины соединены путем, ацикличен, значит путь единственен, а так же прост, так как никакой путь не может зайти в одну вершину два раза, потому что это противоречит ацикличности.
  • [math] 2 \Rightarrow 3 [/math] Очевидно, граф связен. Докажем по индукции, соотношение [math]p = q + 1[/math]
  • [math] 3 \Rightarrow 4 [/math]

Литература

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