Элементы теории графов. Домнин Л.Н. - 58 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

G C,
c
i,j
=∞, v
i
v
j
G
s
v
1
s
v
2
s
v
3
s
v
4
s
v
5
s
v
6
s
v
7
s
v
8
s
v
9
s
v
10
@
@
@
@
@
@
@
@
@
v
1
v
2
v
3
v
4
v
5
v
6
v
7
v
8
v
9
v
10
C=
v
1
v
2
v
3
v
4
v
5
v
6
v
7
v
8
v
9
v
10
∞ 34 ∞ 7 2 38 ∞ ∞ ∞ ∞
34 ∞ 5 ∞ 30 ∞ 22 ∞ ∞ ∞
∞ 5 ∞ ∞ ∞ 25 17 ∞ ∞ ∞
7 ∞ ∞ ∞ 3 ∞ ∞ 13 23 ∞
2 30 ∞ 3 ∞ 20 ∞ 10 ∞ ∞
38 ∞ 25 ∞ 20 ∞ ∞ ∞ 14 14
∞ 22 17 ∞ ∞ ∞ ∞ ∞ ∞ 35
∞ ∞ ∞ 13 10 ∞ ∞ ∞ 23 ∞
∞ ∞ ∞ 23 ∞ 14 ∞ 23 ∞ 8
∞ ∞ ∞ ∞ ∞ 14 35 ∞ 8 ∞
e a b l
ab
T
i
V T
i
T
1
e
1
={v
1
, v
5
} T
i
T
1
,
V T
i
e
2
={v
4
, v
5
}
V T
1
. T
1
,
V T
1
, v
1
, v
4
, v
5
.
V T
1
T
2
V T
2
= {v
2
, v
3
}.
V T
1
,
   Ðàññìîòðèì ïðèìåð. Ïóñòü òðåáóåòñÿ íàéòè êðàò÷àéøèé
îñòîâ ãðàôà G ñ ìàòðèöåé âåñîâ C, ïîêàçàííûõ íà ðèñ. 3.10.
Ýëåìåíò ci,j =∞, åñëè âåðøèíû vi è vj íå ñâÿçàíû ðåáðîì.
                                     v1   v2   v3   v4   v5   v6   v7   v8   v9   v10
               G                                                                    
                             v1      ∞    34   ∞    7     2   38   ∞    ∞    ∞    ∞
         vs1  vs2   vs3      v2     34   ∞     5   ∞    30   ∞    22   ∞    ∞    ∞
                             v3    ∞      5   ∞    ∞    ∞    25   17   ∞    ∞    ∞
          @    @                                                                    
                             v4     7    ∞    ∞    ∞    3    ∞    ∞    13   23   ∞
            @     @                                                                 
         s @ s v6 @ sv7      v      2    30   ∞    3    ∞    20   ∞    10   ∞    ∞
 v4 s                     C= v5     38
    @    v5                    6         ∞    25   ∞    20   ∞    ∞    ∞    14   14 
                                                                                     
                             v7    ∞     22   17   ∞    ∞    ∞    ∞    ∞    ∞    35 
       @                                                                            
    s @s       s             v8    ∞     ∞    ∞    13   10   ∞    ∞    ∞    23   ∞
    v8   v9    v10                                                                  
                             v9      ∞    ∞    ∞    23   ∞    14   ∞    23   ∞     8
                             v10     ∞    ∞    ∞    ∞    ∞    14   35   ∞     8   ∞
                     Ðèñ. 3.10
   Ñîçäàåì óïîðÿäî÷åííûé ñïèñîê ðåáåð â âèäå òàáë. 3.3, ãäå
ñòîëáöû e , a , b , lab ñîäåðæàò ñîîòâåòñòâåííî íîìåðà, ìåòêè
êîíöîâ è äëèíû ðåáåð. Äâà ïîñëåäíèõ ñòîëáöà çàïîëíÿþòñÿ â
ïðîöåññå ïîñòðîåíèÿ êðàò÷àéøåãî îñòîâà.  ñòîëáöå Ti îòðà-
æàåòñÿ ïðîöåññ ñîçäàíèÿ, èçìåíåíèÿ è îáúåäèíåíèÿ ôðàãìåí-
òîâ îñòîâà, à â ñòîëáöå V Ti ôèêñèðóþòñÿ ìíîæåñòâà âåðøèí,
ïðèíàäëåæàùèõ ðàçëè÷íûì ôðàãìåíòàì îñòîâà.
   Â ñîîòâåòñòâèè ñ àëãîðèòìîì ôîðìèðóåì ïåðâûé ôðàã-
ìåíò T1 èç ðåáðà e1 ={v1 , v5 } (ñì. ñòîëáåö Ti ). Ìíîæåñòâî âåð-
øèí, îòíîñÿùèõñÿ ê T1 , ôèêñèðóåì â ïåðâîé ñòðîêå ñòîëáöà
V Ti . Ðåáðî e2 ={v4 , v5 } èìååò îáùèé ýëåìåíò ñ ìíîæåñòâîì
V T1 . Ïîýòîìó ïðèñîåäèíèì åãî ê ôðàãìåíòó T1 , êîððåêòè-
ðóÿ ìíîæåñòâî V T1 , êîòîðîå òåïåðü ñîäåðæèò v1 , v4 , v5 . Êîí-
öû òðåòüåãî ðåáðà íå ïðèíàäëåæàò ìíîæåñòâó V T1 , ïîýòîìó
ñîçäàåì âòîðîé ôðàãìåíò T2 íà îñíîâå òðåòüåãî ðåáðà. Äëÿ
íåãî V T2 = {v2 , v3 }. ×åòâåðòîå ðåáðî ïðîïóñêàåì, òàê êàê
îáå åãî âåðøèíû ÿâëÿþòñÿ ýëåìåíòàìè V T1 , à ïÿòîå ðåáðî
äàåò íà÷àëî òðåòüåìó ôðàãìåíòó, è ò. ä. Ïðîöåññ ïîñòðîåíèÿ
îñòîâà çàâåðøàåòñÿ íà ïÿòíàäöàòîì ðåáðå, êîòîðîå îáúåäè-
íÿåò äâà îñòàâøèåñÿ ôðàãìåíòà. Íà ðèñ. 3.11 ïðåäñòàâëåíû
øåñòü èç ïÿòíàäöàòè ýòàïîâ ïîñòðîåíèÿ îñòîâà. ×èñëî â âåðõ-
íåì ëåâîì óãëó êàæäîé "êàðòèíêè" ñîîòâåòñòâóåò òàáëè÷íîìó
íîìåðó àíàëèçèðóåìîãî ðåáðà (íîìåðó èòåðàöèè).


                                 58

Страницы