Составители:
Рубрика:
71
} (åñëè íåò íóëåâûõ ñòîëáöîâ)
15. èíà÷å { âûâîä ñîîáùåíèÿ ( ãðàôå åñòü êîíòóðû) ;
ïåðåõîä íà êîíåö àëãîðèòìà ï.18 ;
}
16. } ïîêà (v<=n) ; (óñëîâèå ïðîäîëæåíèÿ öèêëà ïî v ï. 4)
17. Âûâîä N ; (âåêòîð íîìåðîâ óðîâíåé âåðøèí)
18. Êîíåö àëãîðèòìà.
4.6.3. Ïîðÿäêîâàÿ ôóíêöèÿ êëàññîâ ýêâèâàëåíòíîñòåé ãðàôà.
Âûäåëåíèå ïðåäïî÷òèòåëüíûõ îáúåêòîâ ñðàâíåíèÿ
Êàê ïîêàçàíî â ï. 4.6.1, ãðàô áåç êîíòóðîâ ìîæíî óïîðÿäî÷èòü
ïî óðîâíÿì â ñîîòâåòñòâèè ñ ïîðÿäêîâîé ôóíêöèåé. Ðàññìîòðèì
êëàññû ýêâèâàëåíòíîñòåé ãðàôà ( êîíòóðû, ìàêñèìàëüíî ñèëüíî
ñâÿçíûå ïîäìíîæåñòâà âåðøèí). Êàê ìû âèäåëè â ï. 4.5.3, ýòè
êëàññû óïîðÿäî÷åíû è ãðàô êëàññîâ ýêâèâàëåíòíîñòåé (ðèñ. 4.4,á)
íå èìååò êîíòóðîâ, ïîýòîìó ìîæíî îïðåäåëèòü åãî óðîâíè. Íà-
ïðèìåð, ïîñëå ïðèìåíåíèÿ àëãîðèòìà ðàçáèåíèÿ ãðàôà íà óðîâíè
íà ðèñ. 4.7 ïîêàçàíû óðîâíè äëÿ ãðàôà êëàññîâ ýêâèâàëåíòíîñ-
òåé (ðèñ. 4.4,á).
Èñõîäíûé ãðàô íà ðèñ. 4.3 áûë ïîñòðîåí íà îñíîâå îòíîøåíèÿ
ïðåäïî÷òåíèÿ ( ïðåâîñõîäñòâà ñì. ï. 4.4) P
f
: (v,v')∈P
f
, ò. å. v'
ïðåâîñõîäèò v, à ãðàô êîíòóðîâ (ðèñ. 4.4,á) áûë ïîñòðîåí íà îñíî-
âå îòíîøåíèÿ R': åñòü ïóòü èç K
r
â K
s
, çíà÷èò, âèñÿ÷èå âåðøè-
íû (íå èìåþùèå ïðåâîñõîäÿùèõ
âåðøèí) ãðàôà íà ðèñ. 4.7 (ò. å.
êëàññû K
4
={v
4
, v
5
} è K
6
={v
8
}) ñî-
äåðæàò âåðøèíû-îáúåêòû ñðàâíå-
íèÿ, êîòîðûå ÿâëÿþòñÿ ïðåäïî÷òè-
òåëüíûìè â äàííîì àíàëèçå è íå-
ñðàâíèìû ìåæäó ñîáîé ïî èíôîð-
ìàöèè, ñîäåðæàùåéñÿ â ãðàôå. Òà-
êèì îáðàçîì, çàäà÷à âûáîðà ïðåä-
ïî÷òèòåëüíûõ îáúåêòîâ èç ìíîæå-
ñòâà ñðàâíèâàåìûõ ìåæäó ñîáîé ïî
íåñêîëüêèì êðèòåðèÿì ðåøåíà, íî
ýòî íå åäèíñòâåííûé ìåòîä.
Ðèñ. 4.7. Óðîâíè ãðàôà
êëàññîâ ýêâèâàëåíòíîñòåé
K
$
K
#
K
K
K
!
K
"
N
N
N
!
N
Страницы
- « первая
- ‹ предыдущая
- …
- 69
- 70
- 71
- 72
- 73
- …
- следующая ›
- последняя »
