2014-02-12
1611
Связность
Говорят, что граф связен, если каждая пара различных вершин может быть соединена, по крайней мере, одной цепью. В противном случае граф называется несвязным. Другое определение связности графа дается следующей теоремой.
Теорема. Граф G=(V, E) связен тогда и только тогда, когда множество его вершин нельзя разбить на два непустых подмножества V 1 и V 2 так, что обе граничные точки каждого ребра находятся в одном и том же подмножестве.
Пусть G=(V, E) - произвольный граф. Рассмотрим бинарное отношение r, определенное между некоторыми упорядоченными парами вершин следующим образом: v r w тогда и только тогда, когда v = w или когда существует цепь, соединяющая v и w. Очевидно, что отношение r рефлексивно (v r v для любого v), симметрично (из v r w следует, что w r v) и транзитивно (из u r v и v r w следует u r w ). Таким образом, r есть отношение эквивалентности. Оно разбивает множество V единственным образом на классы эквивалентности взаимно связных вершин. Для графа, изображенного на рис. 1.1, такими классами являются{ v 2, v 3, v 6},{ v 1, v 4} и { v 5}. Каждый класс эквивалентности вершин вместе с ребрами из E, инцидентными этим вершинам, образует связный подграф,называемыйпросто компонентой G. Легко видеть, что компонента G 1 графа G является максимальным связным подграфом в том смысле, что граф G 1 не имеет связного собственного надграфа.
|
|
|
Граф называется деревом, если он связен и не имеет циклов. Граф, не имеющий циклов и состоящий из k компонент, называется лесом из k деревьев. Понятие дерева играет важную роль во многих разделах теории графов. Граф является деревом тогда и только тогда, когда каждая пара различных вершин соединяется одной и только одной цепью. (Связность означает существование, по крайней мере, одной цепи, а из отсутствия циклов следует существование единственной цепи.)
Удаление любого ребра из дерева делает его несвязным, т. к. удаляемое ребро составляет единственную цепь, соединяющую его граничные точки. С другой стороны, из любого несвязного графа, который не является деревом, можно удалить некоторые ребра, не нарушая связности (например, любое ребро, входящее в цикл). Следовательно, дерево можно также определить как минимальный связный граф, где минимальность понимается в том смысле, что он не содержит подграфа, который состоит из всех его вершин и является связным.
Если дерево T является подграфом графа G, ребра G, которые принадлежат дереву T, называются ветвями дерева T, а ребра, не принадлежащие дереву T, - хордами относительно дерева T. Если все вершины G принадлежат дереву T, то говорят, что дерево покрывает граф G. Очевидно, что только связные графы имеют покрывающие деревья, и только деревья имеют единственные покрывающие деревья.
|
|
|
| На рис. 6.7 жирными линиями выделены два различных покрывающих дерева для одного и того же графа. Тот факт, что каждое из этих деревьев имеет четыре ребра, является следствием общего свойства деревьев, которое устанавливается следующей теоремой. | а) б) Рис.6.7 – Покрывающие деревья |
Теорема. Каждое дерево с n вершинами имеет в точности n -1 ребро.
Применив предыдущий результат к каждому дереву леса, получим следующее «обобщение».
Теорема. Лес из k деревьев, содержащий n вершин имеет в точности n - k ребер.
Любые два дерева, покрывающие один и тот же граф, можно преобразовать одно в другое, строя последовательность покрывающих деревьев, каждое из которых отличается от предыдущего только одним ребром. Рассмотрим, например, последовательность деревьев T 1, T 2, T 3, T 4, где дерево T 1 изображено на рис. 6.7, а, а остальные деревья на рис. 6.8. Заметим, что дерево T 4 на рис. 6.8 совпадает с деревом, изображенным на рис. 6.7, б.
Рис. 6.8 – Трансформация покрывающего дерева
Указанные четыре дерева образуют «монотонный» переход от T 1 к T 4 в том смысле, что каждое последующее дерево имеет на единицу большее число общих ребер с конечным деревом. В общем случае переход от одного покрывающего дерева T к другому T¢ всегда можно осуществить с помощью следующей процедуры.
Пусть e 1 - любое ребро, принадлежащее T ¢, но не принадлежащее T. Тогда (единственная) цепь в T, которая соединяет граничные точки ребра,должна содержать, по крайней мере, одно ребро, не содержащееся в T ¢, т. к. T ¢ не имеет циклов. Построим дерево T 1, которое отличается от T только тем, что в нем удалено ребро и введено новое ребро. Тогда T 1 также будет покрывающим деревом. Если граф G имеет k вершин, тогда каждое покрывающее дерево имеет k -1 ребро и процесс перехода к дереву T ¢ обязательно закончится не более чем за k -1 промежуточных шагов.
