Составители:
Рубрика:
61
êîëè÷åñòâî ïàðàëëåëüíûõ äóã, âàæíîñòü êðèòåðèåâ è âåëè÷èíû îöå-
íîê ïî ðàçíûì êðèòåðèÿì. Äëÿ ó÷åòà ïîñëåäíèõ ïàðàìåòðîâ èñïîëü-
çóþòñÿ áîëåå ñëîæíûå ïðàâèëà è àëãîðèòìû ïðåîáðàçîâàíèÿ
G
V
→G=(V,U).
Èñïîëüçóÿ ïðèíöèï ãîëîñîâàíèÿ (áîëüøèíñòâà) êàê îòíîøåíèå ïðå-
âîñõîäñòâà, èç ãðàôà G
V
(ðèñ. 4.2,à) ìîæíî ëåãêî ïîëó÷èòü ãðàô G=(V,U)
(ðèñ. 4.2,á), êîòîðûé ìîæåò áûòü íå òðàíçèòèâíûì, íåñìîòðÿ íà òî, ÷òî
âñå èñõîäíûå ãðàôû G
V
òðàíçèòèâíû.
Ãðàô G îòðàæàåòñÿ áóëåâîé ìàòðèöåé ñìåæíîñòè Â
Ì×Ì
(ðèñ. 4.2,â),
â êîòîðîé ýëåìåíò b
ij
=1, åñëè äóãà (v,v')∈U (ñòðåëêà èäåò îò v ê v'), ò. å.
âåðøèíà v' ïðåâîñõîäèò (áîëåå ïðåäïî÷òèòåëüíà) v, â ïðîòèâíîì ñëó÷àå
b
ij
=0.
Òàêèì îáðàçîì, â ðåçóëüòàòå äâóõ øàãîâ îáðàáîòêè èñõîäíîé ìàòðè-
öû îöåíîê P
Ì×N
ïîëó÷åíà áóëåâà ìàòðèöà Â
Ì×Ì
, îòðàæàþùàÿ ãðàô G
ïðåâîñõîäñòâà (ïðåäïî÷òåíèÿ) âåðøèí (îáúåêòîâ ñðàâíåíèÿ).
Ðèñ. 4.2. Ïðåîáðàçîâàíèå ìóëüòèãðàôà G
V
→ →
→ →
→ G: à ìóëüòèãðàô G
V
; á ãðàô
G=(V, U); â ìàòðèöà ñìåæíîñòè ãðàôà G
v
"
v
v
!
v
G
8
:
1 2 3 4
1
2
3
4
0 1 1 1
0 0 1 1
1 1 0 1
0 0 0 0
à
á
G:
B
"
×
"
â
3
4
3
v
"
v
v
!
v
2
3
2
1
5
5
6
3
1
Страницы
- « первая
- ‹ предыдущая
- …
- 59
- 60
- 61
- 62
- 63
- …
- следующая ›
- последняя »
