Лекции по дискретной математике. Ч.II. Комбинаторика, разостные уравнения, алгоритмы на графах. Гайдамака Ю.В - 29 стр.

UptoLike

ВУЗ: 

РУДН | Москва

Составители: 

Рубрика: 

Обратно, если такое разбиение существует, то произвольно вы-
бираем вершины v
1
∈
V
1
и v
2
∈
V
2
. Цепь, соединяющая v
1
и v
2
, обяза-
тельно должно содержать, по крайней мере, одно ребро, имеющее
граничные точки в обоих множествах V
1
и V
2
. А т.к. такого ребра
нет, то граф G несвязен.
Если в произвольном графе G вершина v
i
связана с вершиной v
j
,
а v
j
связана с v
l
, то v
i
связана с v
l
. Отношение связности является
отношением эквивалентности (рефлексивно, симметрично, транзи-
тивно). Следовательно, существует такое разложение множества
вершин
i
i
VV ∪=
на попарно непересекающиеся подмножества, что все вершины в
каждом V
i
связаны, а вершины из различных V
i
не связаны. Т.о.
имеем
)(
i
i
VGG ∪==
разложение графа на непересекающиеся связные подграфы G(V
i
),
которые называются компонентами связности графа G.
Деревья и леса
Граф называется деревом, если он связен и не имеет циклов.
Граф, не имеющий циклов и состоящий из k компонентов, называ-
ется лесом из k деревьев.
Граф является деревом тогда и только тогда, когда каждая пара
различных вершин соединяется одной и только одной цепью. Дей-
ствительно, связность означает существование, по крайней мере,
одной цепи, а из отсутствия циклов следует существование един-
ственной такой цепи.
Удаление любого ребра из дерева делает его несвязным, т.к.
удаляемое ребро составляет единственную цепь, соединяющую
его граничные точки. С другой стороны, из любого связного графа,
который не является деревом, можно удалить некоторые ребра не
нарушая связности (например, любое ребро, входящее в цикл). Ес-
ли дерево T является подграфом графа G, то ребра G, которые
принадлежат T, называются ветвями
дерева T, а ребра не принад-
лежавшие дереву T, - хордами относительно дерева T.
Если все вершины графа G принадлежат дереву T, то говорят,
что дерево покрывает
граф G (является его остовом или каркасом).
Теорема.
Каждое дерево с n вершинами имеет в точности n-1
29

Страницы