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

Связность

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

Теорема. Граф G=(V, E) связен тогда и только тогда, когда множество его вершин нельзя разбить на два непустых подмножества V₁ и V₂ так, что обе граничные точки каждого ребра находятся в одном и том же подмножестве.

Пусть G=(V, E) - произвольный граф. Рассмотрим бинарное отношение r, определенное между некоторыми упорядоченными парами вершин следующим образом: vrw тогда и только тогда, когда v=w или когда существует цепь, соединяющая v и w. Очевидно, что отношение r рефлексивно (vrv для любого v), симметрично (из vrw следует, что wrv) и транзитивно (из urv и vrw следует urw).Таким образом, r есть отношение эквивалентности. Оно разбивает множество V единственным образом на классы эквивалентности взаимно связных вершин. Для графа, изображенного на рис. 1.1, такими классами являются{v₂, v_3, v₆},{v₁, v₄} и {v₅}. Каждый класс эквивалентности вершин вместе с ребрами из E, инцидентными этим вершинам, образует связный подграф,называемыйпросто компонентой G. Легко видеть, что компонента G₁ графа G является максимальным связным подграфом в том смысле, что граф G₁ не имеет связного собственного надграфа.

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

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

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

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

а) б) Рис.6.7 – Покрывающие деревья

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

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

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

Любые два дерева, покрывающие один и тот же граф, можно преобразовать одно в другое, строя последовательность покрывающих деревьев, каждое из которых отличается от предыдущего только одним ребром. Рассмотрим, например, последовательность деревьев T₁, T₂, T₃, T₄, где дерево T₁ изображено на рис. 6.7, а, а остальные деревья на рис. 6.8. Заметим, что дерево T₄ на рис. 6.8 совпадает с деревом, изображенным на рис. 6.7, б.

 

Рис. 6.8 – Трансформация покрывающего дерева

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

 

Пусть e₁ - любое ребро, принадлежащее T¢, но не принадлежащее T. Тогда (единственная) цепь в T, которая соединяет граничные точки ребра,должна содержать, по крайней мере, одно ребро , не содержащееся в T¢, т. к. T¢ не имеет циклов. Построим дерево T₁, которое отличается от T только тем, что в нем удалено ребро и введено новое ребро. Тогда T₁ также будет покрывающим деревом. Если граф G имеет k вершин, тогда каждое покрывающее дерево имеет k-1 ребро и процесс перехода к дереву T¢ обязательно закончится не более чем за k-1 промежуточных шагов.