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

UptoLike

ВУЗ: 

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

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

Рубрика: 

31
Äâîè÷íûì äåðåâîì íàçûâàåòñÿ ïðàäåðåâî, åñëè (∀v
i
∈V)|Ã{v
i
}|= 2 èëè
0, ò. å. èç êàæäîé âåðøèíû èñõîäèò äâå äóãè, åñëè ýòî íå âèñÿ÷àÿ âåð-
øèíà (ðèñ. 1.19,á).
Âåòâÿùèìñÿ íàçûâàåòñÿ ãðàô, âñå ñâÿçíûå êîìïîíåíòû êîòîðîãî ÿâ-
ëÿþòñÿ ïðàäåðåâüÿìè (ðèñ 1.19,â).
1.4.6. Îðãðàôû è áèíàðíûå îòíîøåíèÿ
Ïóñòü V  ìíîæåñòâî îáúåêòîâ, ïîäëåæàùèõ èññëåäîâàíèþ ïóòåì èõ
ïîïàðíîãî (áèíàðíîãî) ñðàâíåíèÿ. Ìíîæåñòâî âñåõ óïîðÿäî÷åííûõ ïàð
v,v'∈V îáîçíà÷àåòñÿ 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 → v=v'; àñèììåòðè÷íûì, åñëè
(v,v')∈B → (v',v)∉B; òðàíçèòèâíûì, åñëè (v,v')∈B è (v',v'')∈B → (v,v'')∈B;
ëèíåéíûì, åñëè (v,v')∈B èëè (v',v)∈B.
Áèíàðíûå îòíîøåíèÿ ëåãêî ïðåäñòàâëÿþòñÿ â âèäå îðãðàôà, ïðè ýòîì
âåðøèíû ãðàôà ñîîòâåòñòâóþò îáúåêòàì ñðàâíåíèÿ v
i
∈V, à äóãè îòîáðà-
æàþò áèíàðíîå îòíîøåíèå ìåæäó îáúåêòàìè. Åñëè (v, v')∈B, òî ïðîâî-
äèòñÿ äóãà èç v â v', ïðè ýòîì v íà÷àëî, à v' êîíåö äóãè, ò. å. äóãà
îïðåäåëÿåòñÿ ïàðîé (v,v'). Êàê ïîêàçàíî âûøå, ïîñëåäîâàòåëüíîñòü äóã
(v
i-1
, v
i
), i=1, 2, , n, ñîñòàâëÿåò ïóòü
â ãðàôå. Êîíå÷íûé ïóòü, ó êîòîðî-
ãî v
0
=v
n
, îáðàçóåò êîíòóð. Äóãà (v, v) íàçûâàåòñÿ ïåòëåé (îòðàæàåò ðåô-
ëåêñèâíîå îòíîøåíèå).
 äåéñòâèòåëüíîñòè, ëþáîå áèíàðíîå îòíîøåíèå Â, îïðåäåëåííîå
íà ìíîæåñòâå V, ìîæåò áûòü ïðåäñòàâëåíî îðèåíòèðîâàííûì ãðàôîì,
âåðøèíû êîòîðîãî ñîîòâåòñòâóþò ýëåìåíòàì V. Ãðàô ïîëíîñòüþ îïèñû-
âàåò îòíîøåíèå ïåðå÷èñëåíèåì âñåõ ñâÿçíûõ ýëåìåíòîâ. Òàêèì îáðà-
çîì, îðãðàô, â íåêîòîðîì ñìûñëå, ÿâëÿåòñÿ èñ÷åðïûâàþùåé ôîðìîé ïðåä-
ñòàâëåíèÿ îòíîøåíèÿ, ò. å. îí ïîëíîñòüþ ïåðå÷èñëÿåò âñå ïàðû, äëÿ
êîòîðûõ ðàññìàòðèâàåìîå îòíîøåíèå èìååò ìåñòî.
Ðàññìîòðåííûå âûøå îïèñàíèÿ ñïåöèàëüíûõ êëàññîâ îðãðàôîâ, íå
èìåþùèõ ïàðàëëåëüíûõ ðåáåð, àíàëîãè÷íû òåðìèíîëîãèè áèíàðíûõ îò-
íîøåíèé. Äåéñòâèòåëüíî, ðåôëåêñèâíûì íàçûâàåòñÿ ãðàô, èìåþùèé
ïåòëþ (v, v) â êàæäîé âåðøèíå, ñèììåòðè÷åñêèì ÿâëÿåòñÿ ãðàô, â êîòî-
ðîì êàæäîé äóãå u=(v, w), ñîîòâåòñòâóåò âñòðå÷íàÿ äóãà u'=(w, v), òðàí-
çèòèâíûì íàçûâàåòñÿ ãðàô, â êîòîðîì èç ñóùåñòâîâàíèÿ äóã u
1
=(v, v') è
u
2
=(v', v'') ñëåäóåò ñóùåñòâîâàíèå äóãè u
3
=(v, v'').

Страницы