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

UptoLike

ВУЗ: 

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

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

Рубрика: 

28
åäèíåíû äâóìÿ âñòðå÷íûìè, ò. å. ïðîòèâîïîëîæíî íàïðàâëåííûìè äó-
ãàìè) (ðèñ. 1.17,à).
Àíòèñèììåòðè÷åñêèì íàçûâàåòñÿ ãðàô G=(V,U), â êîòîðîì (∀v
i
∈V,
∀v
j
∈V) (v
i
, v
j
)∈U ⇒ (v
j
, v
i
)∉U (ïàðà ñìåæíûõ âåðøèí ìîæåò áûòü ñîåäè-
íåíà ëèøü â îäíîì íàïðàâëåíèè, ïåòëè îòñóòñòâóþò) (ðèñ.1.17,á).
Ïîëíûì íàçûâàåòñÿ ãðàô G=(V, U), â êîòîðîì (∀v
i
∈V, ∀v
j
∈V)
(v
i
, v
j
)∉ U ⇒ (v
j
, v
i
)∈U (i ≠ j) (ëþáûå äâå âåðøèíû ñîåäèíåíû ïî êðàé-
íåé ìåðå îäíîé äóãîé, ò. å. ñìåæíû) (ðèñ. 1.17, â).
Ðåôëåêñèâíûì áóäåì íàçûâàòü ãðàô, èìåþùèé ïåòëþ â êàæäîé âåð-
øèíå.
Òðàíçèòèâíûì íàçûâàåòñÿ ãðàô, â êîòîðîì èç íàëè÷èÿ äóã u
1
=(v, v') è
u
2
=(v', v'') ñëåäóåò ñóùåñòâîâàíèå äóãè u
3
=(v, v''). Òàêèì îáðàçîì â òðàí-
çèòèâíîì ãðàôå ñóùåñòâîâàíèå ëþáîãî ïóòè èç âåðøèíû v â âåðøèíó
w îçíà÷àåò ñóùåñòâîâàíèå äóãè èç v â w.
Ïîëíûì ãðàôîì ñ ïåòëÿìè íàçûâàåòñÿ ãðàô G=(V, Ã), åñëè (∀v
i
∈V)
Ãv
i
=V (êàæäàÿ ïàðà âåðøèí, ðàçëè÷íûõ èëè íåò, ñîåäèíÿåòñÿ äóãîé, ò. å.
ýòî ñèììåòðè÷åñêèé, ðåôëåêñèâíûé è òðàíçèòèâíûé ãðàô). Î÷åâèäíî,
÷òî êàæäîìó ãðàôó ìîæíî ñîïîñòàâèòü ïîëíûé ãðàô ñ ïåòëÿìè.
1.4.4. Ïåðåìåùåíèÿ â îðãðàôå
Ïåðåìåùåíèÿ ïî äóãàì îðãðàôà îáóñëîâëåíû èõ îðèåíòàöèåé.
Ïóòåì äëèíû n ÿâëÿåòñÿ ïîñëåäîâàòåëüíîñòü (íå îáÿçàòåëüíî ðàç-
ëè÷íûõ) äóã (u
1
, u
2
, , u
n
) òàêèõ, ÷òî äëÿ ñîîòâåòñòâóþùåé ïîñëåäî-
âàòåëüíîñòè n+1 âåðøèí v
0
, v
1
, , v
n
ñïðàâåäëèâî u
i
=(v
i-1
, v
i
) äëÿ
i=1, 2, , n (ò. å. êîíåö ïðåäûäóùåé äóãè ñîâïàäàåò ñ íà÷àëîì ñëå-
äóþùåé). Ïóòü ìîæíî çàäàòü ïîñëåäîâàòåëüíîñòüþ äóã èëè âåðøèí,
Ðèñ. 1.17. Ðàçíîâèäíîñòè îðãðàôîâ:
à ñèììåòðè÷åñêèé; á àíòèñèììåòðè÷åñêèé; â ïîëíûé
v
v
v
"
v
!
à á â
v
!
v
v
v
"
v
v
v
"
v
!

Страницы