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

Определения

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

Ациклический граф - граф, в котором нет циклов.

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

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

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

Граф, не содержащий циклов, называется лесом.

Теорема

Теорема:

Для графа [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] будет точно один простой цикл.

Следствие:

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

Литература

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