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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

(v
1
, v
4
)
(v
2
, v
1
, v
4
, v
6
, v
3
),
(v
3
, v
2
), c
3,2
=∞.
c
1,4
=∞,
(v
1
, v
4
).
S(v
1
, v
4
) S(v
1
, v
4
)
L
7
=104 L
8
=112,
L
7
S(v
1
, v
4
) S(v
1
, v
4
)
v
2
v
5
v
3
0
∞
0
v
5
20 ∞
L
7
=L
5
+∆=104
v
2
v
5
α
i
A
v
3
∞ 0 ∞
v
5
0 ∞ 20 ∞
β
j
0 0 20
B ∞ ∞ ∞
v
2
v
4
v
5
v
1
∞ ∞ 28
v
3
0 ∞ 0
v
5
20 0 ∞
L
8
=L
5
+φ
1,4
=112
(v
2
, v
1
, v
4
, v
6
, v
3
).
(v
3
, v
5
) (v
5
, v
2
).
(v
2
, v
1
, v
4
, v
6
, v
3
, v
5
, v
2
),
L
7
,
L
6
, S(v
2
, v
1
)
L
7
,
(v
4
, v
6
)
(v
6
, v
3
), (v
2
, v
1
).
äóãà (v1 , v4 ) ñîâìåñòíî ñ ðàíåå âûáðàííûìè äóãàìè îáðàçóåò
îðöåïü (v2 , v1 , v4 , v6 , v3 ), íåîáõîäèìî çàïðåòèòü èñïîëüçîâàíèå
äóãè (v3 , v2 ), çàìûêàþùåé ýòó öåïü. Ïîëàãàåì c3,2 =∞.
   Âòîðàÿ ìàòðèöà (â) ïîëó÷àåòñÿ, åñëè â ìàòðèöå, ïðåäñòàâ-
ëåííîé íà ðèñ. 5.22,á, ïðèíÿòü c1,4 =∞, ÷òîáû çàáëîêèðîâàòü
èñïîëüçîâàíèå äóãè (v1 , v4 ).
   Íèæíèå ãðàíèöû äëÿ ïîäìíîæåñòâ S(v1 , v4 ) è S(v1 , v4 )
ñîîòâåòñòâåííî ðàâíû L7 =104 è L8 =112, ïðè÷åì äëÿ îòûñ-
êàíèÿ L7 âûïîëíåíà ðåäóêöèÿ (ñì. ðèñ. 5.23,á) ìàòðèöû íà
ðèñ. 5.23,à.
         S(v1 , v4 )                                  S(v1 , v4 )
         v2 v5                v2 v5 αi A              v2   v4   v5
          0
    v3   ∞ 0            v3    ∞   0 0 ∞          v1   ∞    ∞    28
    v5   20 ∞           v5    0   ∞ 20 ∞         v3    0   ∞     0
                        βj    0   0 20           v5   20   0    ∞
    L7 =L5 +∆=104
                        B     ∞   ∞    ∞
                                                 L8 =L5 +φ1,4 =112
          à                       á                        â
                             Ðèñ. 5.23
    Ñîäåðæèìîå ìàòðèöû íà ðèñ. 5.23,á óêàçûâàåò íà åäèí-
ñòâåííóþ âîçìîæíîñòü ïîëó÷åíèÿ ãàìèëüòîíîâà öèêëà íà îñíî-
âå ñôîðìèðîâàííîé ê äàííîìó ìîìåíòó öåïè (v2 , v1 , v4 , v6 , v3 ).
Ýòî èñïîëüçîâàíèå "íóëåâûõ" äóã (v3 , v5 ) è (v5 , v2 ). Â ðåçóëü-
òàòå èìååì ãàìèëüòîíîâ öèêë (v2 , v1 , v4 , v6 , v3 , v5 , v2 ), äëèíà
êîòîðîãî ðàâíà L7 , ò. å. 104. Íà ôîíå çíà÷åíèé âåñîâ äóã, ñî-
äåðæàùèõñÿ â èñõîäíîé ìàòðèöå (ñì. ðèñ. 5.19,à), ïîëó÷åííûé
ðåçóëüòàò ïðåäñòàâëÿåòñÿ î÷åíü õîðîøèì, îäíàêî óòâåðæäàòü,
÷òî ýòî êðàò÷àéøèé öèêë, ïîêà íåëüçÿ. Äåéñòâèòåëüíî, íèæ-
íÿÿ ãðàíèöà L6 , äëÿ ìíîæåñòâà S(v2 , v1 ) 27 èìååò çíà÷åíèå 101
(ñì. ðèñ. 5.22,â), à ýòî ìåíüøå, ÷åì äëèíà íàéäåííîãî ãàìèëü-
òîíîâà öèêëà. Ïîýòîìó âïîëíå âîçìîæíî, ÷òî ñðåäè öèêëîâ
ýòîãî ìíîæåñòâà åñòü öèêë ìåíüøåé, ÷åì L7 , èëè ðàâíîé äëè-
íû. Ñëåäîâàòåëüíî, íåîáõîäèìî ïðîäîëæèòü ïðîöåññ ðàçáèå-
  27 Ìíîæåñòâî      ãàìèëüòîíîâûõ öèêëîâ, ñîäåðæàùèõ äóãè (v4 , v6 ) è
(v6 , v3 ), íî íå ñîäåðæàùèõ äóãó (v2 , v1 ).


                                      136

Страницы