1.10. Деревья и циклы
Граф 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.
Достарыңызбен бөлісу: |
