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

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


Определение:
Дерево - это связный ациклический граф.


Определение:
Граф, не содержащий циклов, называется лесом.
Теорема:
Для графа [math]G[/math] с [math]p[/math] вершинами и [math]q[/math] ребрами следующие утверждения эквивалентны:

1) [math]G[/math] - дерево;

2) любые две вершины в [math]G[/math] соединены единственной простой цепью;

3) [math]G[/math] связный граф и [math]p = q + 1[/math];

4) [math]G[/math] ациклический граф и [math]p = q + 1[/math];

5) [math]G[/math] - ациклический граф, и если любую праву несмежных вершин соединить ребром [math]x[/math], то в графе [math]G + x[/math] будет точно один простой цикл;

6) [math]G[/math] - связный граф, отличный от Kp для [math]p \ge 3[/math], и если любую пару несмежных вершин соединить ребром [math]x[/math], то в графе [math]G + x[/math] будет точно один простой цикл;

7) [math]G[/math] - Граф, отличный от K3 [math]\cup[/math] K1 и K3[math]\cup[/math] K2, [math]p = q + 1[/math], и если любую пару несмежных вершин соединить ребром [math]x[/math], то в графе [math]G + x[/math] будет точно один простой цикл.

Следствие

В любом нетривиальном дереве имеется по крайней мере две висячие вершины.