Дискретная математика: графы и автоматы. Альпин Ю.А - 16 стр.

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

16 Глава 1. Неориентированные графы
Наконец, единственность получающегося простого цикла следует из
того, что в противном случае вершины, инцидентные добавленному
ребру, соединены в исходном графе двумя простыми цепями, что про-
тиворечит условию 4).
5) ⇒ 1). Если добавление нового ребра дает простой цикл, зна-
чит, вершины, соединенные этим ребром, были соединены в исходном
графе простой цепью. Следовательно, граф связный. ¤
2. Остовы наименьшего веса. Алгоритм Краскала. Од-
на из причин популярности деревьев заключается в том, что любой
связный граф содержит в качестве подграфа дерево с тем же мно-
жеством вершин, что и сам граф. Это дерево называется остовом
графа. В существовании остова можно убедиться, последовательно
удаляя рёбра, принадлежащие циклам. Ясно, что граф, не являю-
щийся деревом, имеет несколько остовов.
Рассмотрим следующую задачу. Имеется несколько городов, ко-
торые нужно соединить между собой сетью дорог. Для каждой пары
городов известна стоимость строительства соединяющей их дороги.
Требуется построить сеть дорог, имеющую минимальную суммарную
стоимость. Эта и подобные ей практические задачи допускают следу-
ющую математическую формулировку в терминах графов.
Дан граф, каждому ребру которого приписано положительное
число — вес. Весом остова назовём сумму весов его рёбер. Требу-
ется найти остов графа, имеющий наименьший вес. Наиболее изве-
стен следующий алгоритм решения этой задачи, обычно именуемый
алгоритмом Краскала.
Построим графы T
0
, T
1
, . . . , T
n−1
следующим образом. Возьмём
в качестве T
0
пустой граф с множеством вершин V . Добавив ребро
наименьшего веса, получим граф T
1
. Ясно, что у него нет циклов.
Пусть уже построен лес T
i
с i рёбрами (i < n − 1). Он несвязный по
предложению 2.1. Выберем ребро наименьшего веса из тех, которые
не образуют циклов с рёбрами T
i
(таковым является любое ребро,
соединяющее различные компоненты графа T
i
). Добавив выбранное
ребро к T
i
, получим T
i+1
. Продолжаем, пока не получим граф T
n−1
.
У этого графа по построению n − 1 ребер и нет циклов. По теореме 1
граф T
n−1
— дерево (остов исходного графа).
Теорема 2. Остов T
n−1
имеет минимально возможный вес.
Д о к а з а т е л ь с т в о. Пусть D — любой другой остов графа. До-
кажем, что вес T
n−1
не больше веса D. Запишем последовательность
рёбер e
1
, e
2
, . . . , e
n−1
остова T
n−1
, выбранных алгоритмом Краскала.
Пусть e
k
— ребро с наименьшим номером, не принадлежащее D. До-
16                                      Глава 1. Неориентированные графы


Наконец, единственность получающегося простого цикла следует из
того, что в противном случае вершины, инцидентные добавленному
ребру, соединены в исходном графе двумя простыми цепями, что про-
тиворечит условию 4).
    5) ⇒ 1). Если добавление нового ребра дает простой цикл, зна-
чит, вершины, соединенные этим ребром, были соединены в исходном
графе простой цепью. Следовательно, граф связный. ¤
    2. Остовы наименьшего веса. Алгоритм Краскала. Од-
на из причин популярности деревьев заключается в том, что любой
связный граф содержит в качестве подграфа дерево с тем же мно-
жеством вершин, что и сам граф. Это дерево называется остовом
графа. В существовании остова можно убедиться, последовательно
удаляя рёбра, принадлежащие циклам. Ясно, что граф, не являю-
щийся деревом, имеет несколько остовов.
    Рассмотрим следующую задачу. Имеется несколько городов, ко-
торые нужно соединить между собой сетью дорог. Для каждой пары
городов известна стоимость строительства соединяющей их дороги.
Требуется построить сеть дорог, имеющую минимальную суммарную
стоимость. Эта и подобные ей практические задачи допускают следу-
ющую математическую формулировку в терминах графов.
    Дан граф, каждому ребру которого приписано положительное
число — вес. Весом остова назовём сумму весов его рёбер. Требу-
ется найти остов графа, имеющий наименьший вес. Наиболее изве-
стен следующий алгоритм решения этой задачи, обычно именуемый
алгоритмом Краскала.
    Построим графы T0 , T1 , . . . , Tn−1 следующим образом. Возьмём
в качестве T0 пустой граф с множеством вершин V . Добавив ребро
наименьшего веса, получим граф T1 . Ясно, что у него нет циклов.
Пусть уже построен лес Ti с i рёбрами (i < n − 1). Он несвязный по
предложению 2.1. Выберем ребро наименьшего веса из тех, которые
не образуют циклов с рёбрами Ti (таковым является любое ребро,
соединяющее различные компоненты графа Ti ). Добавив выбранное
ребро к Ti , получим Ti+1 . Продолжаем, пока не получим граф Tn−1 .
У этого графа по построению n − 1 ребер и нет циклов. По теореме 1
граф Tn−1 — дерево (остов исходного графа).
     Теорема 2. Остов Tn−1 имеет минимально возможный вес.
   Д о к а з а т е л ь с т в о. Пусть D — любой другой остов графа. До-
кажем, что вес Tn−1 не больше веса D. Запишем последовательность
рёбер e1 , e2 , . . . , en−1 остова Tn−1 , выбранных алгоритмом Краскала.
Пусть ek — ребро с наименьшим номером, не принадлежащее D. До-

Страницы