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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

§ 4. Листы и деревья 17
бавив его к D, получим граф с единственным простым циклом (см.
теорему 1). В этом цикле найдется ребро e
0
, не принадлежащее T
n−1
.
Докажем, что вес e
0
не меньше, чем вес e
k
. Действительно, допустим,
что вес e
0
строго меньше, чем вес e
k
. Но тогда на k-м шаге алгоритм
Краскала не должен был выбрать e
k
, поскольку есть более лёгкое
ребро e
0
, не образующее циклов с рёбрами e
1
, e
2
, . . . , e
k−1
. Итак, вес
e
0
не меньше, чем вес e
k
. Поэтому, удалив ребро e
0
, мы получим новый
остов D
0
, который имеет с остовом T
n−1
больше общих рёбер, чем D,
а его вес не больше, чем вес D. Если D
0
6= T
n−1
, то повторим выше-
описанную процедуру замены ребра и получим дерево D
00
, которое
имеет ещё больше общих рёбер с D и вес его не больше, чем вес D
0
.
Продолжая таким образом, получим последовательность остовов
D, D
0
, D
00
, . . . , D
(m)
= T
n−1
,
веса которых образуют невозрастающую последовательность. Сле-
довательно, вес T
n−1
не больше, чем вес D, что и завершает
доказательство. ¤
Пример 1. Требуется найти остов наименьшего веса в графе,
изображенном на рис. 7:
Рис. 7
Следуя алгоритму Краскала, выбираем ребро BE наименьшего веса 1.
Среди оставшихся рёбер наименьший вес 2 имеет ребро CE. Следу-
ющее по весу ребро BC образует цикл с ранее выбранными рёбрами,
поэтому пропускаем его и берём ребро AB веса 4. Ребро AE веса 5
образует цикл с уже выбранными рёбрами AB и BE, следовательно,
его брать нельзя. Легко видеть, что любое из рёбер BD и CD веса 6
подходит для последнего шага. Получившиеся остовы наименьшего
веса 1 + 2 + 4 + 6 = 13 изображены на рисунке 8.
§ 4. Листы и деревья
Как следует из предложения 1 §3, дерево — это связный граф,
каждое ребро которого является мостом. Противоположным свой-
ством обладает лист. Связный граф называется листом, если у него
§ 4. Листы и деревья                                                     17


бавив его к D, получим граф с единственным простым циклом (см.
теорему 1). В этом цикле найдется ребро e0 , не принадлежащее Tn−1 .
Докажем, что вес e0 не меньше, чем вес ek . Действительно, допустим,
что вес e0 строго меньше, чем вес ek . Но тогда на k-м шаге алгоритм
Краскала не должен был выбрать ek , поскольку есть более лёгкое
ребро e0 , не образующее циклов с рёбрами e1 , e2 , . . . , ek−1 . Итак, вес
e0 не меньше, чем вес ek . Поэтому, удалив ребро e0 , мы получим новый
остов D0 , который имеет с остовом Tn−1 больше общих рёбер, чем D,
а его вес не больше, чем вес D. Если D0 6= Tn−1 , то повторим выше-
описанную процедуру замены ребра и получим дерево D00 , которое
имеет ещё больше общих рёбер с D и вес его не больше, чем вес D0 .
Продолжая таким образом, получим последовательность остовов
                       D, D0 , D00 , . . . , D(m) = Tn−1 ,
веса которых образуют невозрастающую последовательность. Сле-
довательно, вес Tn−1 не больше, чем вес D, что и завершает
доказательство. ¤
    Пример 1. Требуется найти остов наименьшего веса в графе,
изображенном на рис. 7:




                                     Рис. 7

Следуя алгоритму Краскала, выбираем ребро BE наименьшего веса 1.
Среди оставшихся рёбер наименьший вес 2 имеет ребро CE. Следу-
ющее по весу ребро BC образует цикл с ранее выбранными рёбрами,
поэтому пропускаем его и берём ребро AB веса 4. Ребро AE веса 5
образует цикл с уже выбранными рёбрами AB и BE, следовательно,
его брать нельзя. Легко видеть, что любое из рёбер BD и CD веса 6
подходит для последнего шага. Получившиеся остовы наименьшего
веса 1 + 2 + 4 + 6 = 13 изображены на рисунке 8.


                        § 4. Листы и деревья

    Как следует из предложения 1 §3, дерево — это связный граф,
каждое ребро которого является мостом. Противоположным свой-
ством обладает лист. Связный граф называется листом, если у него

Страницы