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

UptoLike

ВУЗ: 

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

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

Рубрика: 

15
Äëèíîé ìàðøðóòà (n) íàçûâàåòñÿ ÷èñëî ðåáåð, êîòîðûå îí ñîäåðæèò.
Ãîâîðÿò, ÷òî ìàðøðóò çàìêíóò, åñëè v
0
=v
n
, è íå çàìêíóò, åñëè v
0
≠v
n
.
 ïîñëåäíåì ñëó÷àå ìîæíî ñêàçàòü, ÷òî ìàðøðóò ñîåäèíÿåò âåðøè-
íû v
0
è
v
n
. Çàìåòèì, ÷òî îäíî ðåáðî ìîæíî ðàññìàòðèâàòü êàê ìàðø-
ðóò äëèíû 1.
Äëÿ ãðàôà íà ðèñ. 1.6 ïîñëåäîâà-
òåëüíîñòü ðåáåð
u
1
,
u
5
,
u
2
,
u
3
,
u
4
,
u
6
îáðàçóåò íåçàìêíóòûé ìàðøðóò
äëèíû 6, ñîåäèíÿþùèé âåðøèíû v
1
è v
5
. Åìó ñîîòâåòñòâóåò ïîñëåäîâà-
òåëüíîñòü âåðøèí v
1
, v
2
, v
2
, v
3
, v
4
,
v
2
, v
5
. Åñëè çàìåíèòü â ìàðøðóòå
ðåáðî
u
6
íà
u
1,
òî ïîëó÷èì ïðèìåð
çàìêíóòîãî ìàðøðóòà ñ âåðøèíàìè
v
1
, v
2
, v
2
, v
3
, v
4
, v
2
, v
1
.
Öåïüþ íàçûâàåòñÿ íåçàìêíóòûé ìàðøðóò, åñëè âñå åãî ðåáðà ðàçëè÷-
íû. Íàïðèìåð, äëÿ ãðàôà íà ðèñ.1.6 ìîæíî âûäåëèòü ìíîæåñòâî ðåáåð
u
1
,
u
5
,
u
4
,
u
3
,
u
2
, îáðàçóþùèõ öåïü ñ ïîñëåäîâàòåëüíîñòüþ âåðøèí
v
1
, v
2
, v
2
, v
4
, v
3
, v
2
.
Öèêëîì íàçûâàåòñÿ öåïü, êîòîðàÿ íà÷èíàåòñÿ è çàêàí÷èâàåòñÿ â îä-
íîé è òîé æå âåðøèíå (v
0
=v
n
). Íàïðèìåð, äëÿ ãðàôà ðèñ.1.6 öèêë îáðà-
çóåò ïîñëåäîâàòåëüíîñòü ðåáåð
u
2
,
u
3
,
u
4
,
u
5
ñ ïîñëåäîâàòåëüíîñòüþ
âåðøèí v
2
, v
3
, v
4
, v
2
, v
2
.
Ïðîñòîé öåïüþ íàçûâàåòñÿ öåïü, â êîòîðîé âñå n+1 âåðøèí v
0
, v
1
, ... , v
n
ðàçëè÷íû (î÷åâèäíî, ÷òî â ýòîì ñëó÷àå ðåáðà îáÿçàòåëüíî ðàçëè÷íû).
Íàïðèìåð, äëÿ ãðàôà íà ðèñ.1.6 ïðîñòóþ öåïü ñîñòàâëÿþò ðåáðà
u
6
,
u
2
,
u
3
ñ âåðøèíàìè v
5
, v
2
, v
3
, v
4
.
Ïðîñòûì öèêëîì íàçûâàåòñÿ öèêë, åñëè v
0
= v
n
, íî âñå îñòàëüíûå
âåðøèíû ðàçëè÷íû. Íàïðèìåð, äëÿ ãðàôà ïðîñòîé öèêë îáðàçóþò ðåáðà
u
2
,
u
3
,
u
4
ñ ïîñëåäîâàòåëüíîñòüþ âåðøèí v
2
, v
3
, v
4
, v
2
.
1.3.6. Ñâÿçíîñòü íåîðèåíòèðîâàííîãî ãðàôà
Ãðàô G=(V,
U
) íàçûâàåòñÿ ñâÿçíûì, åñëè äëÿ âñåõ v
i
è v
j
∈V (v
i
≠v
j
)
âñåãäà ñóùåñòâóåò öåïü èç v
i
â v
j
, ò. å. åñëè êàæäàÿ ïàðà ðàçëè÷íûõ âåð-
øèí ìîæåò áûòü ñîåäèíåíà, ïî êðàéíåé ìåðå, îäíîé öåïüþ. Â ïðîòèâ-
íîì ñëó÷àå ãðàô íàçûâàåòñÿ íåñâÿçíûì. Íàïðèìåð, ãðàô ðèñ.1.6 ÿâëÿåò-
ñÿ ñâÿçíûì, à ãðàôû ðèñ. 1.4 è 1.7 íåñâÿçíûìè.
v
v
"
5
u
2
u
6
u
4
u
1
u
3
u
v
!
v
#
v
Ðèñ. 1. 6. Ïðèìåð ãðàôà

Страницы