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

Определение:

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

Определение:

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

Определения

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