1.9. Деревья и циклы

Граф G называется Деревом если он является связным и не имеет циклов.

Граф G называется Лесом если все его компоненты связности - деревья.

Свойства деревьев:

Следующие утверждения эквивалентны:

1) Граф G есть дерево.

2) Граф G является связным и число его ребер ровно на 1 меньше числа вершин.

3) " две различные вершины графа G можно соединить единственной (и при этом простой) цепью.

4) Граф G не содержит циклов, но, добавляя к нему любое новое ребро, получаем ровно один и притом простой цикл

Утверждение 4. Если у дерева G имеется, по крайней мере, 1 ребро, то у него найдется висячая вершина.

Утверждение 5.Пусть G связный граф, а − висячая вершина в G, граф получается из G в результате удаления вершины и инцидентного ей ребра. Тогда тоже является связным.

Остовным деревом Связного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом.

Пусть G – связный граф. Тогда остовное дерево графа G должно содержать N(G)-1 ребер. Значит, для получения остовного дерева из графа G нужно удалить ребер.

Число называется Цикломатическим Числом графа G.

< Предыдущая		Следующая >