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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

l(v
9
),
v
8
,
{v
8
, v
5
}.
l(v
6
)=20,
l(v
3
) l(v
9
) l(v
9
)=14
{v
2
, v
3
}, {v
3
, v
6
}, {v
4
, v
5
}, {v
5
, v
1
},{v
6
, v
5
},{v
7
, v
3
},{v
8
, v
5
},
{v
9
, v
6
},{v
10
, v
9
}.
pred
pred
i
p
O(n
2
).
n−1
C.
    Íà òðåòüåé èòåðàöèè ïîñëå ïåðåñ÷åòà âðåìåííûõ ïîìåòîê,
ïðè÷åì èçìåíÿåòñÿ òîëüêî ïîìåòêà l(v9 ), ìèíèìàëüíîé îêà-
çûâàåòñÿ ïîìåòêà âåðøèíû v8 , è â îñòîâ âêëþ÷àåòñÿ ðåáðî
{v8 , v5 }. Âòîðàÿ âåðøèíà ðåáåðíîé ïàðû áåðåòñÿ èç ïîñëåäíåé
ñòðîêè âîñüìîãî ñòîëáöà.
    Íà ÷åòâåðòîé èòåðàöèè (çíà÷åíèÿ âñåõ ïîìåòîê ñîõðàíÿ-
þòñÿ) ìèíèìàëüíîé îêàçûâàåòñÿ ïîìåòêà l(v6 )=20, íà ïÿòîé
(èçìåíÿþòñÿ l(v3 ) è l(v9 ) ) ìèíèìàëüíà l(v9 )=14 è ò. ä. Ïðî-
öåññ çàâåðøàåòñÿ íà äåâÿòîé èòåðàöèè ïîñëå òîãî, êàê âñå âåð-
øèíû ïîëó÷àþò ïîñòîÿííûå ïîìåòêè (ñì. òàáë. 3.6).
     èòîãå ïîëó÷àåì ñïèñîê ðåáåð, îáðàçóþùèõ êðàò÷àéøèé
îñòîâ: {v2 , v3 }, {v3 , v6 }, {v4 , v5 }, {v5 , v1 },{v6 , v5 },{v7 , v3 },{v8 , v5 },
{v9 , v6 },{v10 , v9 }. Ïåðâàÿ âåðøèíà ïàðû áåðåòñÿ èç çàãîëîâêà
ñòîëáöà, à âòîðàÿ èç ïîñëåäíåé ñòðîêè òîãî æå ñòîëáöà. Ðå-
çóëüòàò ïîëíîñòüþ ñîîòâåòñòâóåò îñòîâó íà ðèñ. 3.13(9). Äëèíà
íàéäåííîãî îñòîâà ðàâíà ñóììå âñåõ ïîñòîÿííûõ ïîìåòîê, êî-
òîðûå, êàê ëåãêî ïðîâåðèòü, ðàâíû âåñàì ðåáåð, âîøåäøèõ â
îñòîâ.
    Ñòðîêà âåðøèí-ïðåäøåñòâåííèö pred ìîæåò áûòü ñôîð-
ìèðîâàíà è ïîñëå òîãî, êàê âñå âåðøèíû ïîëó÷àò ïîñòîÿííûå
ïîìåòêè. Äëÿ ýòîãî äîñòàòî÷íî â êàæäîì ñòîëáöå òàáëèöû
íàéòè ñàìóþ âåðõíþþ ñòðî÷êó ñ ìèíèìàëüíîé ïîìåòêîé. Çíà-
÷åíèå predi ñîäåðæèòñÿ â ñòîëáöå p ýòîé ñòðîêè.
     çàêëþ÷åíèå îòìåòèì, ÷òî òðóäîåìêîñòü ðàññìîòðåííîãî
âàðèàíòà ðåàëèçàöèè àëãîðèòìà Ïðèìà èìååò ïîðÿäîê O(n2 ).
Äåéñòâèòåëüíî, ÷èñëî èòåðàöèé âíåøíåãî öèêëà ðàâíî n−1
ïðè÷åì íà êàæäîé èòåðàöèè ñëåäóåò îáðàáîòàòü ñòðîêó ìàò-
ðèöû C.




                                         69

Страницы