19. Леса и деревья, их основные свойства.
К списку вопросов
Лесом называется граф, не содержащий циклов. Связный лес называется деревом.
Деревья – простейшие графы, которые обладают рядом замечательных свойств:
1. дерево, имеющее n вершин, имеет ровно n-1 ребер.
2. каждое ребро дерева является мостом.
3. любые две вершины дерева соединены ровно одной простой цепью.
4. добавляя к дереву любое новое ребро, мы получаем ровно один цикл.
Следствие: Лес, состоящий из k компонентов и имеющий n вершин, содержит n-k ребер.
Наим. число ребер, кот. надо удалить из данного связного графа, чтобы в нем не осталось ни одного цикла, (т.е. чтобы превратить его в дерево) наз-ся циклическим рангом графа (y).
Гамма y = m-n+1 y - мера связности любого графа.
Дерево, оставшееся после удаления всех ребер, входящих в цикл, наз-ся остовым деревом.
Если граф несвязный и состоит из к-компонент, то y = m-n+к.
Для дерева y = 0.
Кn – полный граф:
Дерево строят по разному в соответствии с иерархическими признаками.
К списку вопросов
