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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

V
0
, V
1
, . . . , V
5
,
V
V
i
V
i
,
i.
G(V, Γ
−1
)
V
V
0
= {v | v ∈ V & Γ
−1
(v) = ∅ };
V
1
= {v | v ∈ V −V
0
& Γ
−1
(v) ⊂ V
0
};
V
2
= {v | v ∈ V −(V
0
∪V
1
) & Γ
−1
(v) ⊂ (V
0
∪V
1
) };
. . . . . .
V
r
= {v | v ∈ V −
r−1
S
j=0
V
j
& Γ
−1
(v) ⊂
r−1
S
j=0
V
j
},
V
r
Γ(v)=∅ v∈V
r
.
O(v),
V
k
,
v
i
∈V
k
, O(v
i
)=k.
V
V
0
, V
1
, . . . , V
r
Γ
−1
(v)=∅,
îò÷åòëèâî âûðàæåíîå ðàçáèåíèå åãî âåðøèí íà ïîäìíîæåñòâà
V0 , V1 , . . . , V5 , òàêîå, ÷òî íà÷àëüíàÿ âåðøèíà ëþáîé äóãè ïðè-
íàäëåæèò ïîäìíîæåñòâó ñ ìåíüøèì èíäåêñîì ïî ñðàâíåíèþ
ñ êîíå÷íîé âåðøèíîé. Äîñòàòî÷íî ïðîíóìåðîâàòü ñïåðâà âåð-
øèíû ïåðâîãî ïîäìíîæåñòâà, ïîòîì âòîðîãî, òðåòüåãî è ò. ä.
Ïðè ýòîì âíóòðè ïîäìíîæåñòâà ïîðÿäîê ïðîèçâîëüíûé, à ýòî
çíà÷èò, ÷òî ñóùåñòâóåò íåñêîëüêî âàðèàíòîâ òàêîé ðàçìåòêè.
     Ñëåäîâàòåëüíî, çàäà÷à òîïîëîãè÷åñêîé ñîðòèðîâêè ñâîäèò-
ñÿ ê îòûñêàíèþ ðàçáèåíèÿ ìíîæåñòâà âåðøèí ãðàôà V íà
ïîäìíîæåñòâà Vi (íàçûâàåìûå óðîâíÿìè, ñëîÿìè, ÿðóñàìè),
òàêèå, ÷òî åñëè âåðøèíà ïðèíàäëåæèò ïîäìíîæåñòâó Vi , òî
ëþáàÿ ñëåäóþùàÿ çà íåé âõîäèò â ïîäìíîæåñòâî, èíäåêñ êîòî-
ðîãî áîëüøå i. Èíûìè ñëîâàìè, íà ìíîæåñòâå âåðøèí íåîáõî-
äèìî íàéòè ÷èñëîâóþ ôóíêöèþ, íàçûâàåìóþ ïîðÿäêîâîé ôóíê-
öèåé ãðàôà, êîòîðàÿ îïðåäåëÿåòñÿ ñëåäóþùèì îáðàçîì.
     Ïóñòü G(V, Γ−1 )  àöèêëè÷åñêèé îðãðàô, è íàéäåíû ñëå-
äóþùèå íåïåðåñåêàþùèåñÿ ïîäìíîæåñòâà ìíîæåñòâà V :
    V0 = {v |   v∈V                & Γ−1 (v) = ∅ };
    V1 = {v |   v ∈ V −V0          & Γ−1 (v) ⊂ V0 };
    V2 = {v |   v ∈ V −(V0 ∪V1 )   & Γ−1 (v) ⊂ (V0 ∪V1 ) };
    ...                              ...
                        S
                       r−1                      S
                                               r−1
    Vr = {v |   v ∈V−      Vj      & Γ−1 (v) ⊂      Vj },
                        j=0                     j=0

ãäå Vr òàêîâî, ÷òî Γ(v)=∅ äëÿ âñåõ v∈Vr . Ïîðÿäêîâàÿ ôóíê-
öèÿ ãðàôà O(v), îïðåäåëåííàÿ íà ìíîæåñòâå âåðøèí, ñîïî-
ñòàâëÿåò êàæäîé èç íèõ ÷èñëî, ðàâíîå çíà÷åíèþ èíäåêñà ïîä-
ìíîæåñòâà Vk , ýëåìåíòîì êîòîðîãî ýòà âåðøèíà ÿâëÿåòñÿ, ò. å.
åñëè vi ∈Vk , òî O(vi )=k.
   Â ñîîòâåòñòâèè ñ ïðèâåäåííûìè ñîîòíîøåíèÿìè äëÿ ïî-
ëó÷åíèÿ íåîáõîäèìîãî ðàçáèåíèÿ ìíîæåñòâà V íà ïîäìíîæå-
ñòâà V0 , V1 , . . . , Vr ñëåäóåò ïîâòîðíî âûïîëíÿòü ïðîöåäóðó ïî-
èñêà âåðøèí, ó êîòîðûõ Γ−1 (v)=∅, ñíà÷àëà â çàäàííîì ãðà-
ôå, ïîòîì â ãðàôå, ïîëó÷åííîì èç çàäàííîãî ïóòåì óäàëåíèÿ
âåðøèí, íàéäåííûõ íà ïåðâîé èòåðàöèè, çàòåì â ãðàôå, ïîëó-
÷åííîì ïóòåì óäàëåíèÿ âåðøèí, íàéäåííûõ íà ïåðâûõ äâóõ
èòåðàöèÿõ, è ò. ä., ïîêà íå áóäóò îáðàáîòàíû âñå âåðøèíû.


                                     28

Страницы