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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

v
2
v
1
c
1,2
∞,
(v
1
, v
2
).
c
2,1
∞,
(v
2
, v
1
).
S(v
2
, v
1
) S(v
2
, v
1
)
v
2
v
4
v
5
v
1
0
∞
2 30
v
3
1 ∞ 0
v
5
21 0 ∞
L
5
=L
3
+∆=84
v
2
v
4
v
5
α
i
A
i
v
1
∞ 28 2 28
v
3
0 ∞ 0 0 0
v
5
20 0 ∞ 0 20
β
j
1 0 0 3
B
j
20 0 28 28
v
1
v
2
v
4
v
5
v
1
∞ 0 2 30
v
2
∞ ∞ 30 17
v
3
29 1 ∞ 0
v
5
3 21 0 ∞
L
6
=L
3
+φ
2,1
=101
L
6
S(v
2
, v
1
)
L
3
S(v
4
, v
6
) φ
2,1
(v
2
, v
1
) L
6
=81+20=101.
L
5
S(v
2
, v
1
),
∆=
P
α
i
+
P
β
j
S(v
2
, v
1
)
L
5
=L
3
+∆=81+3=84.
L
5
L
6
, L
4
L
2
S(v
2
, v
1
) S(v
4
, v
6
) S(v
6
, v
3
)
S(v
2
, v
1
).
φ
1,4
=A
1
+B
4
=28+0=28 (v
1
, v
4
).
S(v
2
, v
1
)
S(v
1
, v
4
) S(v
1
, v
4
).
v
1
v
4
.
óäàëèòü ñòðîêó v2 è ñòîëáåö v1 èç ìàòðèöû íà ðèñ. 5.21,á, à
ýëåìåíò c1,2 ïîëîæèòü ðàâíûì ∞, ÷òîáû èñêëþ÷èòü îáðàò-
íóþ äóãó (v1 , v2 ). Ìàòðèöà â ïîëó÷àåòñÿ, åñëè â ìàòðèöå íà
ðèñ. 5.21,á ýëåìåíò c2,1 ïîëîæèòü ðàâíûì ∞, çàïðåùàÿ òåì
ñàìûì èñïîëüçîâàíèå äóãè (v2 , v1 ).
         S(v2 , v1 )                                   S(v2 , v1 )
         v2 v4   v5         v2 v4 v5 αi Ai             v1   v2   v4   v5
          0
    v1   ∞ 2     30    v1   ∞    0   28    2 28   v1   ∞     0    2   30
    v3    1 ∞     0    v3   0    ∞   0     0 0    v2   ∞    ∞    30   17
    v5   21 0    ∞     v5   20   0   ∞     0 20   v3   29    1   ∞    0
                       βj   1    0   0     3      v5    3   21    0   ∞
    L5 =L3 +∆=84
                       Bj   20   0   28      28
                                                  L6 =L3 +φ2,1 =101
           à                     á                           â
                            Ðèñ. 5.22
    Íèæíÿÿ ãðàíèöà L6 ïîäìíîæåñòâà S(v2 , v1 ) íàõîäèòñÿ êàê
ñóììà íèæíåé ãðàíèöû L3 äëÿ S(v4 , v6 ) è øòðàôà φ2,1 çà
íåèñïîëüçîâàíèå äóãè (v2 , v1 ) : L6 =81+20=101.
    ×òîáû íàéòè íèæíþþ ãðàíèöó L5 ïîäìíîæåñòâà S(v2 , v1 ),
ñëåäóåò âûïîëíèòü ðåäóêöèþ ìàòðèöû à. Ðåçóëüòàò          P ýòîé P îïå-
ðàöèè ïðåäñòàâëåí íà ðèñ. 5.22,á. Ïàðàìåòð ∆= αi + βj â
äàííîì ñëó÷àå ðàâåí 3. Ïîýòîìó íèæíÿÿ ãðàíèöà äëÿ S(v2 , v1 )
èìååò çíà÷åíèå L5 =L3 +∆=81+3=84.
    Òàê êàê L5 ìåíüøå, ÷åì íèæíèå ãðàíèöû L6 , L4 è L2 ïîä-
ìíîæåñòâ S(v2 , v1 ) , S(v4 , v6 ) è S(v6 , v3 ) ñîîòâåòñòâåííî, òî î÷å-
ðåäíîìó ðàçáèåíèþ ïîäëåæèò S(v2 , v1 ).
    Èñïîëüçóÿ ðåäóöèðîâàííóþ ìàòðèöó, ïðåäñòàâëåííóþ íà
ðèñ. 5.22,á, íàõîäèì, ÷òî ìàêñèìàëüíûé ñóììàðíûé øòðàô
φ1,4 =A1 +B4 =28+0=28 ñîîòâåòñòâóåò äóãå (v1 , v4 ). Ðàçáèåíèå
ìíîæåñòâà S(v2 , v1 ) ïî ýòîé äóãå ïîðîæäàåò åùå äâà ïîäìíî-
æåñòâà S(v1 , v4 ) è S(v1 , v4 ). Ñîîòâåòñòâóþùèå ìàòðèöû ïðåä-
ñòàâëåíû íà ðèñ. 5.23,à,â.
    Ïåðâàÿ ìàòðèöà (à) ïîëó÷åíà èç ìàòðèöû íà ðèñ. 5.22,á ïó-
òåì óäàëåíèÿ ñòðîêè v1 è ñòîëáöà v4 . Êðîìå òîãî, ïîñêîëüêó


                                     135

Страницы