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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

∞.
v
1
v
2
v
3
v
4
v
5
v
6
v
1
∞ 3 93 13 33 9
v
2
4 ∞ 77 42 21 16
v
3
45 17 ∞ 36 16 28
v
4
39 90 80 ∞ 56 7
v
5
28 46 88 33 ∞ 25
v
6
3 88 18 46 92 ∞
v
1
v
2
v
3
v
4
v
5
v
6
α
i
A
i
v
1
∞ 0 75 2 30 6 3 2
v
2
0 ∞ 58 30 17 12 4 12
v
3
29 1 ∞ 12 0 12 16 1
v
4
32 83 58 ∞ 49 0 7 32
v
5
3 21 48 0 ∞ 0 25 3
v
6
0 85 35 89 ∞ 3 0
β
j
0 0 15 8 0 0 ∆=81
B
j
0 1 48 2 17 0 φ
6,3
=48
α
i
β
j
,
L
0
=∆=81.
φ
i,j
=A
i
+B
j
A
i
B
j
. φ
6,3
=A
6
+B
3
=48
(v
6
, v
3
).
S(v
6
, v
3
) S(v
6
, v
3
),
c
3,6
∞,
(v
3
, v
6
), (v
6
, v
3
).
c
6,3
∞,
(v
6
, v
3
).
S(v
6
, v
3
),
L
2
=L
0
+φ
6,3
=81+48=129,
ðîëè "íóëåâûõ" äóã â êà÷åñòâå çíà÷åíèÿ äëÿ äèàãîíàëüíûõ
ýëåìåíòîâ ìàòðèöû âìåñòî íóëÿ èñïîëüçóåòñÿ ∞.
         v1   v2   v3   v4   v5   v6            v1   v2   v3   v4   v5   v6  αi     Ai
    v1   ∞     3   93   13   33    9       v1   ∞     0   75   2    30    6   3      2
    v2    4   ∞    77   42   21   16       v2    0   ∞    58   30   17   12   4     12
    v3   45   17   ∞    36   16   28       v3   29    1   ∞    12    0   12 16       1
    v4   39   90   80   ∞    56    7       v4   32   83   58   ∞    49    0   7     32
    v5   28   46   88   33   ∞    25       v5    3   21   48   0    ∞     0  25      3
    v6    3   88   18   46   92   ∞        v6    0   85    0   35   89   ∞    3      0
                                           βj    0    0   15   8     0    0 ∆=81
                                           Bj    0    1   48   2    17    0      φ6,3 =48
                    à                                               á
                                       Ðèñ. 5.19
    Âûïîëíèâ ðåäóêöèþ ïî ñòðîêàì è ïî ñòîëáöàì, ïîëó÷à-
åì ìàòðèöó, ïîêàçàííóþ íà ðèñ. 5.19,á. Òàì æå ïðåäñòàâëå-
íû ñòîëáåö αi è ñòðîêà βj , èñïîëüçîâàííûå ïðè ðåäóêöèè.
Ñóììèðóÿ èõ ñîäåðæèìîå, íàõîäèì íà÷àëüíóþ îöåíêó íèæíåé
ãðàíèöû äëèíû ãàìèëüòîíîâûõ öèêëîâ L0 =∆=81. Äëÿ êàæ-
äîé "íóëåâîé" äóãè ïîëó÷åííîé ìàòðèöû îòûñêèâàåì ñîñòàâ-
ëÿþùèå øòðàôà φi,j =Ai +Bj è çàïèñûâàåì èõ â ñòîëáåö Ai è
ñòðîêó Bj . Ìàêñèìàëüíûé øòðàô φ6,3 =A6 +B3 =48 ñîîòâåò-
ñòâóåò äóãå (v6 , v3 ). Ïîýòîìó èìåííî åå öåëåñîîáðàçíî âçÿòü
â êà÷åñòâå îñíîâû ïðè ðàçáèåíèè ìíîæåñòâà ãàìèëüòîíîâûõ
öèêëîâ íà äâà ïîäìíîæåñòâà S(v6 , v3 ) è S(v6 , v3 ), òàêèõ, ÷òî
âñå öèêëû ïåðâîãî ñîäåðæàò óêàçàííóþ äóãó, âñå öèêëû âòîðî-
ãî åå íå ñîäåðæàò. Ýòèì ïîäìíîæåñòâàì ñîîòâåòñòâóþò ìàòðè-
öû íà ðèñ. 5.20,à,â. Ïåðâàÿ ïîëó÷åíà ïóòåì âû÷åðêèâàíèÿ øå-
ñòîé ñòðîêè è òðåòüåãî ñòîëáöà â ìàòðèöå íà ðèñ. 5.19,á. Êðî-
ìå òîãî, ýëåìåíò c3,6 ïðèíÿò ðàâíûì ∞, ÷òîáû çàáëîêèðî-
âàòü èñïîëüçîâàíèå äóãè (v3 , v6 ), îáðàçóþùåé öèêë ñ (v6 , v3 ).
Âòîðàÿ ìàòðèöà (â) ïîëó÷àåòñÿ, åñëè â ìàòðèöå íà ðèñ. 5.19,á
çíà÷åíèå ýëåìåíòà c6,3 ïîëîæèòü ðàâíûì ∞, çàïðåùàÿ òåì
ñàìûì èñïîëüçîâàíèå äóãè (v6 , v3 ).
    Íèæíÿÿ ãðàíèöà äëèíû öèêëîâ ïîäìíîæåñòâà S(v6 , v3 ),
î÷åâèäíî, ðàâíà L2 =L0 +φ6,3 =81+48=129, ò. å. ïî ñðàâíåíèþ


                                                132

Страницы