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

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

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

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

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

Определения

Для графа 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 K_1 [/math] и [math] K_3 K_2 [/math], количество вершин [math]n[/math], а ребер [math]n - 1[/math], при добавлении любого ребра для несмежных вершин появляется цикл

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

Докажем эквивалентность 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
• Википедия — свободная энциклопедия