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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство эквивалентности)
Строка 15: Строка 15:
  
 
==Доказательство эквивалентности==
 
==Доказательство эквивалентности==
 +
Докажем эквивалентность 1 определения с остальными:
 +
 +
* <tex> 1 \Rightarrow 2 </tex>  Связность, очевидно, вытекает из существования пути между любыми двумя вершинами, а ацикличность из единственности. Повторив эти рассуждения в обратном порядке получим <tex> 1 \Leftarrow 2 </tex>.
 +
 +
* <tex> 1 \Rightarrow 3 </tex> Ацикличность получаем аналогично первому пункту. Теперь рассмотрим <tex> u </tex> и <tex> v </tex> такие, что ребра <tex> uv </tex> не существует. Между ними, как мы знаем, уже существует путь, и при добавлении нового ребра мы получим второй путь. Из существования двух различных путей вытекает существование цикла. Опять же повторив эти рассуждения в обратном порядке получим <tex> 1 \Leftarrow 3 </tex>.
  
 
==Литература==
 
==Литература==

Версия 04:30, 13 ноября 2011

Определение:
Дерево — неориентированный граф, в котором две любых вершины соединены единственным простым путем. Другими словами, любой связный граф без циклов дерево.


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

Определения

Дерево - неориентированный простой граф G, который удовлетворяет любому из эквивалентных утверждений:

  1. Любые две вершины графа G соединены единственным простым путем
  2. G - связен и ацикличен
  3. G - ацикличен, и простой цикл формируется при добавлении любого ребра
  4. G - связен, и удаление любого ребра приводит к потере связности

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

Докажем эквивалентность 1 определения с остальными:

  • [math] 1 \Rightarrow 2 [/math] Связность, очевидно, вытекает из существования пути между любыми двумя вершинами, а ацикличность из единственности. Повторив эти рассуждения в обратном порядке получим [math] 1 \Leftarrow 2 [/math].
  • [math] 1 \Rightarrow 3 [/math] Ацикличность получаем аналогично первому пункту. Теперь рассмотрим [math] u [/math] и [math] v [/math] такие, что ребра [math] uv [/math] не существует. Между ними, как мы знаем, уже существует путь, и при добавлении нового ребра мы получим второй путь. Из существования двух различных путей вытекает существование цикла. Опять же повторив эти рассуждения в обратном порядке получим [math] 1 \Leftarrow 3 [/math].

Литература

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