Дерево, эквивалентные определения

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


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

Определения

Дерево - неориентированный простой граф 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
  • Википедия — свободная энциклопедия