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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

α
i
.
j
v
j
.
α
i
= min{c
i,j
}, j=1, n
i C.
c
i,j
=c
i,j
−α
i
, j=1, n.
β
j
= min{c
i,j
}, i=1, n,
c
i,j
=c
i,j
−β
j
, i=1, n
∆=
P
n
i=1
α
i
+
P
n
j=1
β
j
.
(v
i
, v
j
).
(v
i
, v
j
)
v
i
v
j
.
i j.
(v
j
, v
i
),
(v
i
, v
j
). c
j,i
=∞.
ñêîëüêó ëþáîé ãàìèëüòîíîâ öèêë îáÿçàòåëüíî ñîäåðæèò îäíó
(è òîëüêî îäíó) èç ýòèõ äóã, åãî äëèíà èçìåíèòñÿ íà âåëè÷èíó
αi . ßñíî, ÷òî ïðè ýòîì ñîîòíîøåíèÿ ìåæäó öèêëàìè ïî äëèíå
ñîõðàíÿòñÿ, ò. å. ñàìûé êîðîòêèé òàêîâûì è îñòàíåòñÿ. Òî÷íî
òàêèå æå ðàññóæäåíèÿ ñïðàâåäëèâû è äëÿ ñòîëáöà j ìàòðè-
öû âåñîâ, ñ òîé ëèøü ðàçíèöåé, ÷òî ðå÷ü èäåò îáî âñåõ äóãàõ,
âõîäÿùèõ â âåðøèíó vj .
   Ïóñòü αi = min{ci,j }, j=1, n  ìèíèìàëüíûé ýëåìåíò ñòðî-
êè i ìàòðèöû C. Ïðåîáðàçóåì ìàòðèöó ïóòåì âû÷èòàíèÿ
èç ýëåìåíòîâ êàæäîé ñòðîêè ñîîòâåòñòâóþùåãî ìèíèìàëüíî-
ãî ýëåìåíòà ýòîé ñòðîêè, ïîëîæèâ ci,j =ci,j −αi , j=1, n. Òàêàÿ
îïåðàöèÿ íîñèò íàçâàíèå ðåäóêöèè ìàòðèöû ïî ñòðîêàì. Î÷å-
âèäíî, ÷òî ïîñëå åå âûïîëíåíèÿ êàæäàÿ ñòðîêà äîëæíà ñîäåð-
æàòü õîòÿ áû ïî îäíîìó íóëåâîìó ýëåìåíòó.
   Ñîâåðøåííî àíàëîãè÷íî îïðåäåëÿåòñÿ îïåðàöèÿ ðåäóêöèè
ìàòðèöû ïî ñòîëáöàì. Íàõîäÿòñÿ ìèíèìàëüíûå ýëåìåíòû ïî
ñòîëáöàì βj = min{ci,j }, i=1, n, ïîñëå ÷åãî âûïîëíÿåòñÿ ïðå-
îáðàçîâàíèå ci,j =ci,j −βj , i=1, n ïî âñåì ñòîëáöàì ìàòðèöû. Â
ðåçóëüòàòå â êàæäîì ñòîëáöå ïîÿâèòñÿ õîòÿ áû îäèí íóëåâîé
ýëåìåíò.
   Ïîíÿòíî, ÷òî â ðåçóëüòàòå ïîëíîé ðåäóêöèè âåñîâîé ìàò-
ðèöû êàê ïî ñòðîêàì, òàê è ïî ñòîëáöàì, äëèíû âñåõ ãàìèëü-
òîíîâûõ
    Pn öèêëîâ  Pn â ãðàôå äîëæíû óìåíüøèòüñÿ íà âåëè÷èíó
∆= i=1 αi + j=1 βj . Ýòà âåëè÷èíà ìîæåò ðàññìàòðèâàòüñÿ
êàê áåçóñëîâíàÿ íèæíÿÿ ãðàíèöà äëèíû êðàò÷àéøåãî ãàìèëü-
òîíîâà öèêëà â ïîëíîì îðãðàôå.
   Ïîêàæåì, êàê îïðåäåëÿåòñÿ íèæíÿÿ ãðàíèöà ìíîæåñòâà
ãàìèëüòîíîâûõ öèêëîâ ïðè óñëîâèè, ÷òî âñå îíè ñîäåðæàò
íåêîòîðóþ äóãó, íàïðèìåð (vi , vj ). Òàê êàê ëþáàÿ âåðøèíà â
öèêëå ìîæåò èìåòü òîëüêî îäíó âõîäÿùóþ è îäíó âûõîäÿùóþ
äóãó, èñïîëüçîâàíèå (vi , vj ) ôàêòè÷åñêè íàêëàäûâàåò çàïðåò
íà âêëþ÷åíèå îñòàëüíûõ äóã, âûõîäÿùèõ èç vi è âõîäÿùèõ
â vj . Çàïðåòèòü èñïîëüçîâàíèå ýòèõ äóã ìîæíî, èñêëþ÷èâ èç
âåñîâîé ìàòðèöû ñòðîêó i è ñòîëáåö j. Êðîìå òîãî, íåîáõî-
äèìî çàïðåòèòü èñïîëüçîâàíèå äóãè (vj , vi ), êîòîðàÿ îáðàçóåò
öèêë ñ (vi , vj ). Ñ ýòîé öåëüþ äîñòàòî÷íî ïîëîæèòü cj,i =∞.


                             130

Страницы