Составители:
Рубрика:
67
(ýêâèâàëåíòíîñòè) ýëåìåíòîâ êîíòóðà ((v,v')∈Nf è (v,v')∈N
f
→ v=v') îíè
ñâåäåíû (ñòÿíóòû) ê îäíîìó îáúåêòó (K), ïîñòîëüêó ãðàô êîíòóðîâ ÿâëÿåò-
ñÿ òàêæå àíòèñèììåòðè÷íûì, ò. å. îòðàæàåò ïîëíûé ïîðÿäîê, èëè ñåðèþ.
Ãðàô êëàññîâ ýêâèâàëåíòíîñòåé ÿâëÿåòñÿ àöèêëè÷åñêèì, à äëÿ âû-
ÿâëåíèÿ â íåì ïîðÿäêà, êîòîðûé íå âûãëÿäèò î÷åâèäíûì, ñóùåñòâó-
þò ðàçëè÷íûå ìåòîäû óïîðÿäî÷åíèÿ âåðøèí, êîòîðûå áóäóò ðàññìîò-
ðåíû íèæå.
4.6. Ðàçáèåíèå àöèêëè÷åñêîãî ãðàôà íà óðîâíè
Ïîñòàíîâêà çàäà÷è.  ýòîé çàäà÷å îñóùåñòâëÿåòñÿ óïîðÿäî÷åíèå âåð-
øèí ïî óðîâíÿì ïîñëåäîâàòåëüíîñòåé äóã â àöèêëè÷åñêîì ãðàôå.
4.6.1. Ïîðÿäêîâàÿ ôóíêöèÿ ãðàôà
Ðàññìîòðèì ãðàô áåç êîíòóðîâ G=(V,Ã) è îïðåäåëèì åãî ïîäìíîæå-
ñòâà N
0
, N
1
, ... , N
r
ñëåäóþùèì îáðàçîì:
N
0
={ v
i
v
i
∈V,
1
ˆ
Ã
i
v
−
=∅}, ãäå ñèìâîë ÷èòàåòñÿ êàê åñëè, ò. å. N
0
ýòî ïîäìíîæåñòâî âåðøèí V, åñëè èì íå ïðåäøåñòâóåò íè îäíà âåðøèíà
(íåò âõîäÿùèõ äóã) ;
N
1
={ v
i
v
i
∈V N
0
,
1
ˆ
Ã
i
v
−
⊂ N
0
}, ò. å. N
1
ïîäìíîæåñòâî èç îñòàâøèõ-
ñÿ âåðøèí-êîíöîâ äóã, ïðè÷åì âåðøèíû-íà÷àëà äóã, íàõîäÿòñÿ â ïðåä-
øåñòâóþùåì ìíîæåñòâå N
0
;
áà
v
"
v
v
v
v
%
v
#
v
v
'
v
!
v
$
v
&
K
$
K
#
K
K
K
!
K
"
K
$
K
#
K
K
K
!
K
"
Ðèñ. 4.4. Ãðàô, ðàçëîæåííûé íà ìàêñèìàëüíî ñèëüíî ñâÿçíûå
ïîäãðàôû (êîíòóðû): à ãðàô êëàññîâ ýêâèâàëåíòíûõ îáúåêòîâ;
á ãðàô êîíòóðîâ
Страницы
- « первая
- ‹ предыдущая
- …
- 65
- 66
- 67
- 68
- 69
- …
- следующая ›
- последняя »
