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

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

Версия 04:35, 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].
  • [math] 1 \Rightarrow 4 [/math] Связность аналогично первому пункту. Теперь рассмотрим [math] u [/math] и [math] v [/math] такие, что ребро [math] uv [/math] существует. Мы знаем, что это единственный путь из [math] u [/math] в [math] v [/math], значит после удаления ребра [math] v [/math] станет не достижимо из [math] u [/math] и наоборот, что означает утерю связности. Опять же повторив эти рассуждения в обратном порядке получим [math] 1 \Leftarrow 4 [/math].

Получив эквивалентность всех утверждений первому, по транзитивности автоматически получим эквивалентность остальных утверждений.

Литература

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