1.8. Деревья и леса

Граф называется деревом, если он связен и не имеет циклов. Граф, не имеющий циклов и состоящий из компонент, называется лесом из деревьев. Понятие дерева играет важную роль во многих разделах теории графов. Граф является деревом тогда и только тогда, когда каждая пара различных вершин соединяется одной и только одной цепью. (Связность означает существование, по крайней мере, одной цепи, а из отсутствия циклов следует существование единственной такой цепи.)

Удаление любого ребра из дерева делает его несвязным, так как удаляемое ребро составляет единственную цепь, соединяющую его граничные точки. С другой стороны, из любого связного графа, который не является деревом, можно удалить некоторые ребра, не нарушая связности (например, любое ребро, входящее в цикл). Следовательно, дерево можно также определить как минимальный связный граф, где минимальность понимается в том смысле, что он не содержит подграфа, который состоит из всех его вершин и является связным.

Если дерево является подграфом графа ребра которые принадлежат дереву называются ветвями дерева а ребра, не принадлежащие дереву хордами относительно дерева Если все вершины принадлежат дереву то говорят, что дерево покрывает граф Очевидно, что только связные графы имеют покрывающие деревья и только деревья имеют единственные покрывающие деревья.

На рис. 1.7 жирными линиями выделены два различных покрывающих дерева для одного и того же графа.

Рис. 1.7.

Тот факт, что каждое из этих деревьев имеет по четыре ребра, является следствием общего свойства деревьев, которое устанавливается следующей теоремой.

Теорема 1.5. Каждое дерево с вершинами имеет в точности ребро.

Доказательство. Удаление одного произвольно, ребра разбивает дерево на две компоненты, т. е.

превращает его в лес из двух деревьев (оставляем читателю показать, что при этом не может получиться более двух компонент). Аналогично, удаление второго ребра превращает дерево в лес из трех деревьев. Вообще, после удаления любых ребер получим лес из деревьев. С другой стороны, после удаления всех ребер, очевидно, получим лес, состоящий из деревьев (каждое из которых является изолированной вершиной). Отсюда и следует, что максимальное число ребер, которое мы можем удалить из дерева, равно Теорема доказана.

Применив предыдущий результат к каждому дереву леса, получим следующее «обобщение».

Теорема 1.6. Лес из деревьев, содержащий вершин имеет в точности ребер.

Любые два дерева, покрывающие один и тот же граф, можно преобразовать одно в другое, строя последовательность покрывающих деревьев, каждое из которых отличается от предыдущего только одним ребром. Рассмотрим, например, последовательность деревьев где дерево изображено на рис. 1.7, а, а остальные деревья на рис. 1.8. Заметим, что дерево на рис. 1.8 совпадает с деревом, изображенным на рис. 1.7, Ь).

Рис. 1.8.

Указанные четыре дерева образуют «монотонный» переход от к в том смысле, что каждое последующее дерево имеет на единицу большее число общих ребер с конечным деревом. В общем случае переход от одного покрывающего дерева к другому V всегда можно осуществить с помощью следующей процедуры.

Пусть любое "ребро, принадлежащее но не принадлежащее Тогда (единственная) цепь в которая соединяет граничные точки ребра должна

содержать, по крайней мере, одно ребро не содержащееся в так как V не имеет циклов. Построим дерево которое отличается от только тем, что в нем удалено ребро и введено новое ребро Тогда также будет покрывающим деревом (почему?). Если и V не совпадают, то повторяем рассмотренный процесс. Если граф имеет вершин, тогда каждое покрывающее дерево имеет ребро и процесс перехода к дереву V обязательно закончится не более чем за промежуточных шагов.