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

Материал из Викиконспекты
Версия от 06:35, 11 октября 2010; Geork (обсуждение | вклад) (Новая страница: «{{Определение |definition = Ациклический граф - граф, в котором нет циклов. }} {{Определение |definition =…»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
Определение:
Ациклический граф - граф, в котором нет циклов.


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


Определение:
Граф, не содержащий циклов, называется лесом.
Теорема:
Для графа [math]G[/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] - ациклический граф, и если любую праву несмежных вершин соединить ребром x, то в графе [math]G + x[/math] будет точно один простой цикл;

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

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

Следствие

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