Элементы теории графов. Сюсюкалов А.И - 19 стр.

UptoLike

ВУЗ: 

РГРТУ | Рязань

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

Рубрика: 

14
принадлежащую второму пути, тогда участки первого и второго
путей между
0
v и
1
v образуют цикл. Противоречие.
Таким образом, можно дать другое определение дерева.
Определение 3.3. Дерево – граф, в котором любые две вер-
шины соединены ровно одной цепью.
Лемма. В любом дереве есть висячая вершина.
Д о к а з а т е л ь с т в о. Рассмотрим произвольную верши-
ну
0
v и пойдём по любому ребру из неё в другую вершину
1
v .
Если выходящих рёбер из новой вершины
1
v нет, то остаёмся в
ней, а в противном случае идём по любому другому ребру даль-
ше. Так как граф конечен и в нём нет циклов, то процесс закон-
чится только в висячей вершине.
Теорема 3.3. При удалении любого ребра из дерева оно пре-
вращается в несвязный граф.
Д о к а з а т е л ь с т в о. Пусть концы удалённого ребра в
новом графе соединены цепью. Тогда эта цепь и удалённое реб-
ро образуют цикл.
Теорема 3.4. В дереве число вершин на одну больше числа
рёбер.
Д о к а з а т е л ь с т в о. Пусть в графе
G
n
вершин. Пред-
положим
1
v – висячая вершина, удалим её и выходящее из неё
ребро. После этого опять останется дерево, так как циклов нет.
Пусть
2
v – висячая вершина, которую также удалим и т.д. Про-
делав эту операцию
1n раз, получим граф, состоящий из
одной вершины.
Теорема 3.5. Связный граф
G
, у которого число рёбер на
единицу меньше числа вершин, является деревом.
Д о к а з а т е л ь с т в о. От противного. Пусть
G
не явля-
ется деревом, т.е. имеет циклы. Удалив несколько рёбер, можно
получить дерево. Тогда число рёбер
E
и число вершин
V
удов-
летворяют неравенству
1
EV
. Получили противоречие с
теоремой 3.4.
З а д а ч а. Какое наименьшее число рёбер надо удалить из
связного графа
G
, чтобы он оставался связным и в нём не было

Страницы