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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

(v
4
, v
6
, v
3
, v
4
),
(v
3
, v
4
). c
3,4
∞
c
4,6
∞,
(v
4
, v
6
).
S(v
4
, v
6
) S(v
4
, v
6
)
v
1
v
2
v
4
v
5
v
1
∞ 0 2 30
v
2
0 ∞ 30 17
v
3
29 1
12
∞
0
v
5
3 21 0 ∞
L
3
=L
1
+∆=81
v
1
v
2
v
4
v
5
α
i
A
i
v
1
∞ 0 2 30 0 2
v
2
∞ 30 17 0 17
v
3
29 1 ∞ 0 0 1
v
5
3 21 0 ∞ 0 3
β
j
0 0 0 0 0
B
j
3 1 2 17 20
v
1
v
2
v
4
v
5
v
6
v
1
∞ 0 2 30 6
v
2
0 ∞ 30 17 12
v
3
29 1 12 0 ∞
v
4
32 83 ∞ 49 ∞
v
5
3 21 0 ∞ 0
L
4
=L
1
+φ
4,6
=113
S(v
4
, v
6
),
(v
6
, v
3
) (v
4
, v
6
),
S(v
6
, v
3
)
φ
4,6
(v
4
, v
6
) L
4
=L
1
+φ
4,6
=81+32=113.
S(v
4
, v
6
),
(v
4
, v
6
) (v
6
, v
3
),
L
3
S(v
4
, v
6
)
S(v
6
, v
3
)
L
4
S(v
4
, v
6
)
L
2
S(v
6
, v
3
).
S(v
4
, v
6
).
φ
2,1
=20 (v
2
, v
1
).
S(v
4
, v
6
) S(v
2
, v
1
) S(v
2
, v
1
).
(v
2
, v
1
),
òðåõâåðøèííîãî öèêëà (v4 , v6 , v3 , v4 ), ñëåäóåò çàáëîêèðîâàòü
èñïîëüçîâàíèå îáðàòíîé äóãè (v3 , v4 ). Ïîýòîìó c3,4 ïîëàãàåì
ðàâíûì ∞ . Âòîðàÿ ìàòðèöà (â) ïîëó÷àåòñÿ, åñëè â ìàòðèöå
íà ðèñ. 5.20,á çíà÷åíèå ýëåìåíòà c4,6 ïîëîæèòü ðàâíûì ∞,
çàïðåùàÿ òåì ñàìûì èñïîëüçîâàíèå äóãè (v4 , v6 ).
      S(v4 , v6 )                                              S(v4 , v6 )
     v1   v2   v4 v5        v1   v2   v4   v5   αi   Ai        v1   v2   v4   v5   v6
v1   ∞     0    2 30   v1   ∞     0    2   30   0     2   v1   ∞     0    2   30    6
v2    0   ∞    30 17   v2    0   ∞    30   17   0    17   v2    0   ∞    30   17   12
               12                                         v3   29    1   12    0   ∞
v3   29    1   ∞ 0     v3   29    1   ∞     0   0     1
v5    3   21    0 ∞    v5    3   21    0   ∞    0     3   v4   32   83   ∞    49   ∞
                       βj    0    0    0    0   0         v5    3   21    0   ∞     0
 L3 =L1 +∆=81
                       Bj    3    1    2   17        20
                                                           L4 =L1 +φ4,6 =113
           à                          á                              â
                                 Ðèñ. 5.21
    Íèæíÿÿ ãðàíèöà äëèíû öèêëîâ ïîäìíîæåñòâà S(v4 , v6 ),
ò. å. öèêëîâ, ñîäåðæàùèõ (v6 , v3 ) è íå ñîäåðæàùèõ (v4 , v6 ),
ðàâíà ñóììå íèæíåé ãðàíèöû ïîäìíîæåñòâà S(v6 , v3 ) è øòðà-
ôà φ4,6 çà íåèñïîëüçîâàíèå (v4 , v6 ) : L4 =L1 +φ4,6 =81+32=113.
    Äëÿ îïðåäåëåíèÿ íèæíåé ãðàíèöû ïîäìíîæåñòâà S(v4 , v6 ),
â êîòîðîì âñå öèêëû ñîäåðæàò (v4 , v6 ) è (v6 , v3 ), ðåäóöèðóåì
ìàòðèöó, ïðåäñòàâëåííóþ íà ðèñ. 5.21,à. È çäåñü ðåäóöèðî-
âàííàÿ ìàòðèöà èäåíòè÷íà èñõîäíîé (ñì. ðèñ. 5.21,á). Ïîýòî-
ìó íèæíÿÿ ãðàíèöà L3 ïîäìíîæåñòâà S(v4 , v6 ) ñîâïàäàåò ñ
ðàíåå íàéäåííîé íèæíåé ãðàíèöåé äëÿ S(v6 , v3 ) è ðàâíà 81.
Ýòî ìåíüøå, ÷åì íèæíÿÿ ãðàíèöà L4 äëÿ S(v4 , v6 ) è íèæ-
íÿÿ ãðàíèöà L2 äëÿ S(v6 , v3 ). Çíà÷èò, ðàçáèåíèþ ïîäëåæèò
S(v4 , v6 ). Ðåçóëüòàòû ïîèñêà äóãè, ïî êîòîðîé ñëåäóåò ïðîèç-
âîäèòü ðàçáèåíèå, ïðåäñòàâëåíû íà ðèñ. 5.21,á. Ìàêñèìàëüíîå
çíà÷åíèå øòðàôà φ2,1 =20 óêàçûâàåò íà äóãó (v2 , v1 ). Ðàçáèâà-
åì S(v4 , v6 ) íà äâà ïîäìíîæåñòâà S(v2 , v1 ) è S(v2 , v1 ). Ïåðâîå
ñîñòîèò èç öèêëîâ, ñîäåðæàùèõ äóãó (v2 , v1 ), öèêëû âòîðîãî
ýòîé äóãè íå ñîäåðæàò. Óêàçàííûì ïîäìíîæåñòâàì ñîîòâåò-
ñòâóþò ìàòðèöû íà ðèñ. 5.22,à,â. Ìàòðèöà à ïîëó÷àåòñÿ, åñëè


                                           134

Страницы