Дискретная математика: Основы теории графов и алгоритмизация задач. Прокушев Л.А. - 58 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

58
V→f
n
, êîòîðîå ïîçâîëÿåò âûïîëíèòü ñðàâíåíèå ïî êðèòåðèþ f
n
.
Îáîçíà÷èì ÷åðåç F
n
ìíîæåñòâî îöåíîê, êîòîðûå ìîæíî ïîëó÷èòü,
èññëåäóÿ ýëåìåíòû V ñ òî÷êè çðåíèÿ êðèòåðèÿ f
n
. Ïðè àíàëèçå ïî
âñåì êðèòåðèÿì êàæäîìó ýëåìåíòó v∈V ñòàâèòñÿ â ñîîòâåòñòâèå
ïîñëåäîâàòåëüíîñòü èç N îöåíîê, âçÿòûõ èç ìíîæåñòâ F
1
,  , F
N
, ò. å.
ñ êàæäûì ýëåìåíòîì ìíîæåñòâà V ñîïîñòàâëÿåòñÿ ýëåìåíò äåêàðòîâà
ïðîèçâåäåíèÿ F '= F
1
× F
2
×× F
N
..
Ñòàâèòñÿ çàäà÷à âûïîëíèòü ñðàâíåíèå îáúåêòîâ ìíîæåñòâà V ñ ïî-
ìîùüþ ìíîãîìåðíîãî ñîñòîÿíèÿ F' = F
1
× F
2
×× F
N
. ñ öåëüþ âûáîðà
îäíîãî èëè íåñêîëüêèõ îáúåêòîâ, ÿâëÿþùèõñÿ íàèëó÷øèìè ñ òî÷êè çðå-
íèÿ ìíîæåñòâà êðèòåðèåâ F. Ïðåäñòàâèì ðåøåíèå çàäà÷è ïîïàðíîãî ñðàâ-
íåíèÿ îáúåêòîâ íà ÿçûêå òåîðèè ãðàôîâ.
Ìíîæåñòâî âñåõ óïîðÿäî÷åííûõ ïàð v, v'∈V îáîçíà÷àåòñÿ V×V. Ï î ä -
ìíîæåñòâî B⊆V×V íàçûâàåòñÿ áèíàðíûì îòíîøåíèåì, ò. å. (v,v') ∈B.
Âûøå ìû ðàññìîòðåëè ñîîòâåòñòâèå ìåæäó áèíàðíûì îòíîøåíèåì è
îðãðàôîì, ïðè ýòîì âåðøèíû ãðàôà ñîîòâåòñòâóþò îáúåêòàì ñðàâíåíèÿ
v
i
∈V, à äóãè îòðàæàþò áèíàðíîå îòíîøåíèå ìåæäó îáúåêòàìè.
Íàïîìíèì, ÷òî åñëè (v,v') ∈B, òî â ãðàôå ïðîâîäèòñÿ äóãà èç v â v',
ïðè ýòîì v íà÷àëî, à v' êîíåö äóãè, ò. å. äóãà îïðåäåëÿåòñÿ ïàðîé
(v,v'). Ïîñëåäîâàòåëüíîñòü äóã (v
i
, v
i+1
), i=1,2, , k1, íàçûâàåòñÿ ïó-
òåì. Êîíå÷íûé ïóòü, ó êîòîðîãî v
1
=v
k
, îáðàçóåò êîíòóð. Äóãà (v, v) íà-
çûâàåòñÿ ïåòëåé.
Êàê èçâåñòíî, áèíàðíîå îòíîøåíèå íàçûâàåòñÿ ðåôëåêñèâíûì, åñëè
(v,v) ∈B (ò. å. ãðàô ñ ïåòëÿìè); àíòèðåôëåêñèâíûì, åñëè (v,v) ∉B (ò. å.
ãðàô áåç ïåòåëü); ñèììåòðè÷íûì, åñëè (v,v') ∈B ↔ (v',v) ∈B (ò. å. äëÿ
êàæäîé ïàðû ñìåæíûõ âåðøèí åñòü âñòðå÷íûå äóãè); àíòèñèììåò-
ðè÷íûì, åñëè (v,v') ∈B è (v',v) ∈B → v=v' (ò. å. âåðøèíû ñî âñòðå÷íû-
ìè äóãàìè ðàññìàòðèâàþòñÿ êàê îäíà âåðøèíà); àñèììåòðè÷íûì, åñëè
(v,v') ∈B → (v',v) ∉B (ò. å. ãðàô áåç âñòðå÷íûõ äóã ìåæäó ïàðàìè âåð-
øèí); òðàíçèòèâíûì, åñëè (v,v') ∈B è (v',v'') ∈B → (v,v'') ∈B (ò. å. åñëè
ëþáûå òðè ïîñëåäîâàòåëüíûå âåðøèíû ñâÿçàíû äâóìÿ ïîñëåäîâàòåëü-
íûìè äóãàìè, òî ñóùåñòâóåò äóãà ìåæäó ïåðâîé è òðåòüåé âåðøèíàìè);
ëèíåéíûì, åñëè (v,v') ∈B èëè (v',v) ∈B (ò. å. ëþáûå äâå âåðøèíû ñâÿçà-
íû õîòÿ áû îäíîé äóãîé).
Ðàññìîòðèì òåïåðü ìíîæåñòâî êðèòåðèåâ F. Êàæäûé ÷àñòíûé êðèòå-
ðèé f
n
∈F çàäàåò íàïðàâëåíèå âîçðàñòàíèÿ ïðåäïî÷òåíèÿ îáúåêòîâ, â ñî-
îòâåòñòâèè ñ óâåëè÷åíèåì èõ îöåíîê, îïðåäåëÿåìûõ â êîëè÷åñòâåííîé
èëè ðàíãîâîé øêàëå, ò. å. ìîæíî çàäàòü áèíàðíîå îòíîøåíèå ïðåäïî÷-

Страницы