Составители:
Рубрика:
62
4.5. Ìåòîäû è àëãîðèòìû âûáîðà
ïðåäïî÷òèòåëüíûõ îáúåêòîâ
4.5.1. Ìåòîä è àëãîðèòì ïîèñêà êîíòóðîâ â ãðàôå
Ðàññìîòðèì ãðàô G êàê ïàðó G= (V, Ã), ãäå Ã ïðåäñòàâëÿåò ìíîãî-
çíà÷íîå îòîáðàæåíèå ìíîæåñòâà âåðøèí V â ñåáÿ, íàïðèìåð, êàê áûëî
ïîêàçàíî âûøå Ã
v
, îáîçíà÷àåò ìíîæåñòâî âåðøèí-êîíöîâ äóã, èìåþùèõ
íà÷àëîì âåðøèíó v;
ˆ
Ã
v
è
ˆ
Ã
v
−
ïðåäñòàâëÿþò òðàíçèòèâíîå è îáðàòíîå
òðàíçèòèâíîå çàìûêàíèå äëÿ âåðøèíû v.
Îòñóòñòâèå òðàíçèòèâíîñòè â ãðàôå ïðåâîñõîäñòâà îáúåêòîâ ñðàâ-
íåíèÿ G ñâèäåòåëüñòâóþò î íàëè÷èè êîíòóðîâ, îáúåäèíÿþùèõ ïîäìíî-
æåñòâà îáúåêòîâ, íåðàçëè÷èìûõ ïî èíôîðìàöèè, ñîäåðæàùåéñÿ â ãðà-
ôå, â ñîîòâåòñòâèè ñ îòíîøåíèåì íåðàçëè÷èìîñòè N
f
äëÿ îáúåêòîâ ñ
îäèíàêîâûìè îöåíêàìè p(v)=p(v') : (v,v')∈N
f
. Ýòî îòíîøåíèå N
f
ÿâëÿåòñÿ
òàêæå îòíîøåíèåì ýêâèâàëåíòíîñòè (òðàíçèòèâíûì, ðåôëåêñèâíûì è
ñèììåòðè÷íûì).
Ïóñòü Ê ÿâëÿåòñÿ êîíòóðîì â ãðàôå G, òîãäà îáúåêòû v∈Ê ìîæíî
ðàññìàòðèâàòü êàê ýêâèâàëåíòíûå, ò. å. êîíòóðû îáðàçóþò êëàññû ýê-
âèâàëåíòíîñòåé (Ê
1
,, Ê
m
) è ïðåäñòàâëÿþòñÿ â ãðàôå êàê òðàíçèòèâíûå,
ðåôëåêñèâíûå, ñèììåòðè÷íûå ïîäãðàôû, îïðåäåëåííûå âûøå (ñì. ï. 1.4.8)
êàê ñèëüíî ñâÿçíûå ãðàôû. Òàêèì îáðàçîì ìíîæåñòâî îáúåêòîâ V (âåð-
øèí ãðàôà G) ìîæíî ðàçëîæèòü íà êëàññû Ê
1
,, Ê
m
, êàæäûé èç êîòî-
ðûõ åñòü êîíòóð, ò. å. ñèëüíî ñâÿçíûé ãðàô.
Ìàêñèìàëüíûì ñèëüíî ñâÿçíûì ïîäãðàôîì G' ãðàôà G=(V,Ã) íàçûâà-
åòñÿ òàêîé ïîäãðàô, äëÿ êîòîðîãî íå ñóùåñòâóåò ñèëüíî ñâÿçíîãî ãðàôà
G'', ñòðîãî ñîäåðæàùåãî G'.
Ëåãêî ïîêàçàòü, ÷òî ïîäìíîæåñòâî êëàññîâ {Ê
i
}, i=
1, m
, óïîðÿäî÷è-
âàþòñÿ îòíîøåíèåì R': ñóùåñòâóåò ïóòü èç êëàññà Ê
r
â Ê
s
. Îòíîøå-
íèå R' ðåôëåêñèâíî è òðàíçèòèâíî. Îíî òàêæå àñèììåòðè÷íî (ò. å. â
ãðàôå íåò âñòðå÷íûõ äóã), òàê êàê åñëè áû ñóùåñòâîâàëè ïóòè êàê èç Ê
r
â Ê
s
, òàê è èç Ê
s
â Ê
r
, òî Ê
r
è Ê
s
ñëåäîâàëî áû îáúåäèíèòü â îäèí êëàññ,
÷òî ïðîòèâîðå÷èò èõ ìàêñèìàëüíîñòè.
Ïåðâûé øàã óïîðÿäî÷åíèÿ ãðàôà ïðåâîñõîäñòâà G = (V,Ã) ñîñòîèò â
íàõîæäåíèè êîíòóðîâ ãðàôà è ðàññìîòðåíèè èõ êàê îòäåëüíûõ îáúåê-
òîâ.
Ìåòîä ïîèñêà êîíòóðîâ ñîñòîèò â ðàçëîæåíèè ãðàôà íà êëàññû ýêâè-
âàëåíòíîñòåé:
Страницы
- « первая
- ‹ предыдущая
- …
- 60
- 61
- 62
- 63
- 64
- …
- следующая ›
- последняя »
