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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

(n, m)
m−1
n.
O(mn).
O(m log
2
m)
m
G(V, E),
T (V T, ET ),
v
i
v
j
ET
k
:=ET
k−1
+{v
i
, v
j
}
V T
k
:=V T
k−1
+v
j
, v
i
∈V T
k−1
, v
j
6∈V T
k−1
, c
i,j
T n−1
T
0
, T
1
, . . . , T
n−1
, T
0
=h{v}, ∅i,
T
n−1
   Îöåíèì òðóäîåìêîñòü ïðèâåäåííîãî âàðèàíòà ðåàëèçàöèè
àëãîðèòìà Êðàñêàëà ïðèìåíèòåëüíî ê (n, m) -ãðàôó.
    õóäøåì ñëó÷àå (ñàìîå äëèííîå ðåáðî ïðèíàäëåæèò êðàò-
÷àéøåìó îñòîâó) âíåøíèé öèêë ïåðåáîðà ðåáåð ãðàôà äîë-
æåí ïîâòîðèòüñÿ m−1 ðàç. Êðîìå òîãî, â òåõ ñëó÷àÿõ, êîãäà
âêëþ÷åíèå ðåáðà ïðèâîäèò ê îáúåäèíåíèþ äâóõ ôðàãìåíòîâ
áóäóùåãî îñòîâà, äîëæíà áûòü âûïîëíåíà ïðîöåäóðà îáúåäè-
íåíèÿ ìíîæåñòâ èõ âåðøèí. ×èñëî ïîâòîðåíèé ñîîòâåòñòâóþ-
ùåãî öèêëà ðàâíî n. Ó÷èòûâàÿ âñå ýòî, ìîæíî óòâåðæäàòü,
÷òî òðóäîåìêîñòü àëãîðèòìà íå õóæå ÷åì O(mn). Ýòî âåñü-
ìà çàâûøåííàÿ îöåíêà, ïîñêîëüêó äàëåêî íå âñåãäà ðåáðî ñ
ìàêñèìàëüíûì âåñîì âõîäèò â îñòîâ, è ñîâñåì íå îáÿçàòåëüíî,
÷òî âêëþ÷åíèå î÷åðåäíîãî ðåáðà äîëæíî ïðèâîäèòü ê ñëèÿ-
íèþ íåêîòîðîé ïàðû ôðàãìåíòîâ.
    çàêëþ÷åíèå îòìåòèì, ÷òî àëãîðèòì ïðåäïîëàãàåò óïîðÿ-
äî÷åííîñòü ñïèñêà ðåáåð, à ýòî, â ñâîþ î÷åðåäü, òðåáóåò âû-
ïîëíåíèÿ åùå ïîðÿäêà O(m log2 m) îïåðàöèé. Ïðè äîñòàòî÷-
íî áîëüøîì m èìåííî ýòà ñîñòàâëÿþùàÿ ïðîöåññà ïîëó÷åíèÿ
êðàò÷àéøåãî îñòîâà ìîæåò îêàçàòüñÿ îñíîâíîé â îáùåì áà-
ëàíñå òðóäîåìêîñòè.

   3.4.2. Àëãîðèòì Ïðèìà
   Îïèñàíèå àëãîðèòìà.  îòëè÷èå îò àëãîðèòìà Êðàñ-
êàëà, àëãîðèòì Ïðèìà îáåñïå÷èâàåò ïîñòðîåíèå îñòîâà ãðàôà
G(V, E), çàäàííîãî ñïèñêîì ðåáåð, ïóòåì íàðàùèâàíèÿ åäèí-
ñòâåííîãî äðåâîâèäíîãî ôðàãìåíòà T (V T, ET ), êîòîðûé âíà-
÷àëå âîîáùå íå èìååò ðåáåð è ñîñòîèò èç îäíîé ïðîèçâîëüíî
âûáðàííîé âåðøèíû ãðàôà. Íà êàæäîé èòåðàöèè ê ôðàãìåí-
òó äîáàâëÿåòñÿ ñàìîå êîðîòêîå ðåáðî èç ÷èñëà ðåáåð, ó êî-
òîðûõ îäíà èç êîíöîâûõ âåðøèí vi óæå âêëþ÷åíà â ñòðîÿ-
ùèéñÿ îñòîâ, à äðóãàÿ vj åùå íåò, ò. å. ETk :=ETk−1 +{vi , vj } è
V Tk :=V Tk−1 +vj , ãäå vi ∈V Tk−1 , vj 6∈V Tk−1 , à ci,j ìèíèìàëüíî.
Ïðîöåññ çàêàí÷èâàåòñÿ ïîñëå ïðèñîåäèíåíèÿ ê T n−1 ðåáåð.
Òàêèì îáðàçîì, ïðè âûïîëíåíèè àëãîðèòìà ôîðìèðóåòñÿ ïî-
ñëåäîâàòåëüíîñòü äåðåâüåâ: T0 , T1 , . . . , Tn−1 , ãäå T0 =h{v}, ∅i,
à Tn−1  êðàò÷àéøèé îñòîâ. Åñëè ñïèñîê óïîðÿäî÷åí ïî âîç-


                                63

Страницы