Деревья и циклы
Граф 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.
Дата добавления: 2015-09-27 | Просмотры: 529 | Нарушение авторских прав
|