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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

(v
i
, v
j
).
(v
i
, v
j
),
c
i,j
∞.
(v
i
, v
j
)
v
i
v
j
.
v
i
(v
i
, v
j
),
v
j
(v
i
, v
j
).
(v
i
, v
j
).
i c
i,j
A
i
,
j c
i,j
B
j
. (v
i
, v
j
)
φ
i,j
=A
i
+B
j
.
Ðåäóêöèÿ ïðåîáðàçîâàííîé òàêèì îáðàçîì ìàòðèöû ïîçâîëÿ-
åò ïîëó÷èòü íèæíþþ ãðàíèöó ìíîæåñòâà öèêëîâ, ñîäåðæàùèõ
äóãó (vi , vj ).
     Íèæíÿÿ ãðàíèöà äëÿ ìíîæåñòâà ãàìèëüòîíîâûõ öèêëîâ,
íå ñîäåðæàùèõ (vi , vj ), ïîëó÷àåòñÿ ïóòåì ðåäóêöèè âåñîâîé
ìàòðèöû, â êîòîðîé ýëåìåíò ci,j ïîëàãàåì ðàâíûì ∞.
     Íàêîíåö, äóãó, ïî êîòîðîé ïðîèñõîäèò ðàçáèåíèå î÷åðåä-
íîãî ðàññìàòðèâàåìîãî ïîäìíîæåñòâà ãàìèëüòîíîâûõ öèêëîâ,
(ñì. áèíàðíîå äåðåâî íà ðèñ. 5.18) öåëåñîîáðàçíî âûáèðàòü
èç ÷èñëà òåõ, âåñà êîòîðûõ â ðåäóöèðîâàííîé ìàòðèöå îêà-
çàëèñü íóëåâûìè. Âî-ïåðâûõ, ýòî íàèáîëåå êîðîòêèå äóãè è,
âî-âòîðûõ, îíè ÿâëÿþòñÿ ýëåìåíòàìè åñòåñòâåííîé (âîçìîæíî
äàæå öèêëè÷åñêîé) ñòðóêòóðû â ãðàôå, èìåþùåé ìèíèìàëü-
íóþ äëèíó. Îäíàêî êîëè÷åñòâî òàêèõ äóã äîâîëüíî âåëèêî,
íå ìåíåå ÷èñëà âåðøèí â ãðàôå. Çàäà÷à âûáîðà ìîæåò áûòü
ðåøåíà ïóòåì îöåíêè äëÿ êàæäîé èç íèõ "øòðàôà" (ïîòåðü)
çà íåâêëþ÷åíèå äóãè â ãàìèëüòîíîâ öèêë. Ïóñòü, íàïðèìåð,
(vi , vj ) îäíà èç äóã ñ íóëåâûì âåñîì, íå âêëþ÷åííàÿ â öèêë.
Çíà÷èò, â öèêëå èìååòñÿ îðöåïü, ñâÿçûâàþùàÿ âåðøèíó vi ñ
vj . Íà÷àëüíîé äóãîé ýòîé öåïè äîëæíà áûòü îäíà èç äóã, âû-
õîäÿùèõ èç vi è îòëè÷íàÿ îò (vi , vj ), à êîíå÷íîé  îäíà èç äóã,
âõîäÿùèõ â vj è òàêæå îòëè÷íàÿ îò (vi , vj ). Íà ñóììó âåñîâ
ýòèõ äóã â ðåäóöèðîâàííîé ìàòðèöå è ïðîèçîéäåò óäëèíåíèå
öèêëà ïðè îòêàçå îò èñïîëüçîâàíèÿ äóãè (vi , vj ). Îáîçíà÷èì
ìèíèìàëüíûé ýëåìåíò i ñòðîêè (íå ñ÷èòàÿ ci,j ) êàê Ai , à
ìèíèìàëüíûé ýëåìåíò j ñòîëáöà (òàêæå íå ñ÷èòàÿ ci,j ) êàê
Bj . Íàçîâåì øòðàôîì çà íåèñïîëüçîâàíèå äóãè (vi , vj ) ñóììó
φi,j =Ai +Bj . Ìàêñèìàëüíûé èç øòðàôîâ ïî ìíîæåñòâó "íó-
ëåâûõ" äóã ðåäóöèðîâàííîé ìàòðèöû îïðåäåëÿåò òó èç íèõ,
ïî êîòîðîé öåëåñîîáðàçíî âûïîëíÿòü äàëüíåéøåå ðàçáèåíèå
î÷åðåäíîãî ïîäìíîæåñòâà öèêëîâ.
     Ïðèìåð. Ðàçáåðåì ïðèìåð íà ïðèìåíåíèå îïèñàííîãî âà-
ðèàíòà ðåàëèçàöèè ìåòîäà âåòâåé è ãðàíèö. Ïóñòü ãðàô çàäàí
ìàòðèöåé âåñîâ, íà ðèñ. 5.19,à.26 Çàìåòèì, ÷òî â ñèëó îñîáîé
 26 Íå îáÿçàòåëüíî, ÷òîáû ìàòðèöà áûëà ñèììåòðè÷íîé, õîòÿ ýòî ïðåä-
ñòàâëÿåòñÿ íàèáîëåå åñòåñòâåííûì ïðè òðàêòîâêå âåñîâ äóã êàê ðàññòîÿ-
íèé. Ðàññìàòðèâàåìûé àëãîðèòì äàåò ðåøåíèå â ñàìîì îáùåì ñëó÷àå.


                                131

Страницы