Составители:
Рубрика:
63
åñëè Ê(v
i
) êëàññ, ñîäåðæàùèé âåðøèíó v
i
, òî
Ê(v
i
) =
ˆ
Ã
i
v
∩
1
ˆ
Ã
i
v
−
,
ò. å. êîíòóð äëÿ íåêîòîðîé âåðøèíû v
i
åñòü ïîäìíîæåñòâî âåðøèí, îá-
ðàçóåìîå ïåðåñå÷åíèåì ìíîæåñòâ òðàíçèòèâíîãî è îáðàòíîãî òðàíçè-
òèâíîãî çàìûêàíèé äëÿ âåðøèíû v
i.
 ÷àñòíîñòè, êëàññ Ê(v
i
) ìîæåò ñî-
ñòîÿòü è èç îäíîé âåðøèíû v
i.
Àëãîðèòì ìåòîäà âêëþ÷àåò ñëåäóþùèå îñíîâíûå øàãè.
1. Äëÿ îáðàáàòûâàåìûõ âåðøèí âûáèðàåì íà÷àëüíóþ âåðøèíó v
i
è
îïðåäåëÿåì
ˆ
Ã
i
v
,
1
ˆ
Ã
i
v
−
, Ê(v
i
).
2. Óäàëÿåì èç äàëüíåéøåãî àíàëèçà âåðøèíû èç Ê(v
i
) ïóòåì ïîäàâ-
ëåíèÿ èõ ñâÿçåé, äëÿ ÷åãî â ìàòðèöå ñìåæíîñòè íåîáõîäèìî îáíóëèòü
ñòðîêè è ñòîëáöû äëÿ âåðøèí èç êëàññà Ê(v
i
).
3. Åñëè åñòü åùå íåîáðàáîòàííûå âåðøèíû, òî ïåðåéòè íà øàã 1.
Ïðèìåð
Äëÿ ãðàôà G=(V,U), ãäå V=11 (ðèñ. 4.3) íèæå ïðåäñòàâëåí ïðîöåññ
ïîëó÷åíèÿ êîíòóðîâ îò íà÷àëüíûõ âåðøèí. Ðåçóëüòèðóþùèé âåêòîð V
äîëæåí ñîäåðæàòü íîìåðà êîíòóðîâ, ïðè âåðøèíàõ èõ îáðàçóþùèõ.
Ýòàï 1. Îáðàáîòêà èñõîäíîé ìàòðèöû ñìåæíîñòè S. Íà÷àëüíàÿ âåð-
øèíà v
1
îòìå÷åíà çíà÷åíèåì 0 â âåêòîðàõ çàìûêàíèé.
Ðèñ. 4.3. Îðãðàô G
v
"
v
v
!
v
v
v
v
'
v
&
v
%
v
$
v
#
Страницы
- « первая
- ‹ предыдущая
- …
- 61
- 62
- 63
- 64
- 65
- …
- следующая ›
- последняя »
