Составители:
Рубрика:
68
N
2
={ v
i
v
i
∈V( N
0
∪N
1
),
1
ˆ
Ã
i
v
−
⊂ N
0
∪N
1
}, ò. å. N
2
ïîäìíîæåñòâî èç
îñòàâøèõñÿ âåðøèí-êîíöîâ äóã, ïðè÷åì âåðøèíû-íà÷àëà äóã ìîãóò íà-
õîäèòüñÿ â ëþáûõ ïðåäûäóùèõ ìíîæåñòâàõ; íàêîíåö,
N
r
={ v
i
v
i
∈ V
1
0
r
k
k
N
−
=
U
,
1
ˆ
Ã
i
v
−
⊂
1
0
r
k
k
N
−
=
U
}, ãäå r òàêîå íàèìåíüøåå
÷èñëî, ÷òî ÃN
r
=∅, ò. å. èç âåðøèí ýòîãî ïîäìíîæåñòâà íå èñõîäèò íè
îäíà äóãà (ýòî âèñÿ÷èå âåðøèíû).
Ïîäìíîæåñòâà N
k
, k=0, 1, 2, , r îáðàçóþò ðàçáèåíèå V è óïîðÿäî-
÷åíû îòíîøåíèåì ñëåäîâàíèÿ (→) :
N
k
→N
k'
⇔ k<k'.
Ïîðÿäêîâàÿ ôóíêöèÿ ãðàôà áåç êîíòóðîâ (Î(v)) îïðåäåëÿåòñÿ ðàâåí-
ñòâîì
v
i
∈ N
k
⇒ O (v
i
)=k.
Äðóãèìè ñëîâàìè, ïðåäëàãàåòñÿ ðàçáèòü ìíîæåñòâî âåðøèí ãðàôà
áåç êîíòóðîâ íà íåïåðåñåêàþùèåñÿ ïîäìíîæåñòâà, óïîðÿäî÷åííûå òàê,
÷òî åñëè âåðøèíà ïðèíàäëåæèò ïîäìíîæåñòâó ñ íîìåðîì k, òî ñëåäóþ-
ùàÿ çà íåé âåðøèíà âõîäèò â ïîäìíîæåñòâî ñ íîìåðîì, áîëüøèì k.
Ïîäìíîæåñòâà ýòîãî ðàçáèåíèÿ íàçûâàþòñÿ óðîâíÿìè. Îíè óïîðÿ-
äî÷èâàþò ïîñëåäîâàòåëüíîñòü ïóòåé â ãðàôå.
Ïðèìåð
Àëãîðèòì íàõîæäåíèÿ óðîâíåé àöèêëè÷åñêîãî ãðàôà è åãî ïîðÿäêî-
âîé ôóíêöèè ðàññìîòðèì íà ïðèìåðå ãðàôà íà ðèñ 4.5,à.
Ïðåäñòàâèì ãðàô åãî ìàòðèöåé ñìåæíîñòè S è ðàññìîòðèì îñíîâíûå
øàãè àëãîðèòìà íàõîæäåíèÿ óðîâíåé ãðàôà (ñì.ðèñ. 4.5,á).
á) ||S||:
Ðèñ. 4.5. Âûäåëåíèå óðîâíåé àöèêëè÷åñêîãî ãðàôà:
à èñõîäíûé ãðàô G; á ìàòðèöà ñìåæíîñòè è óðîâíè ãðàôà
A
à
)
B
F
C
E
D
A000011 ABCDE F
B101010 C
0
204031 N
0
=
{
B,D
}
C000000 C
1
01211 1 N
1
=
{
A
}
D101010 C
2
1 1 2 1 0 0 N
2
=
{
E,F
}
E001000 C
3
1 1 0 1 1 1 N
3
=
{
C
}
F001000
ABCDEF
Страницы
- « первая
- ‹ предыдущая
- …
- 66
- 67
- 68
- 69
- 70
- …
- следующая ›
- последняя »
