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

UptoLike

ВУЗ: 

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

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

Рубрика: 

29
÷åðåç êîòîðûå îí ïðîõîäèò. Íàïðè-
ìåð, íà ðèñ.1.18 ïîñëåäîâàòåëüíîñòü
äóã (u
1
, u
5
, u
5
, u
3
) îáðàçóåò ïóòü ñ ñî-
îòâåòñòâóþùåé ïîñëåäîâàòåëüíîñòüþ
âåðøèí (v
3
, v
2
, v
2
, v
2
, v
1
).
Ïóòü íàçûâàåòñÿ çàìêíóòûì, åñëè
v
0
=v
n
, è íåçàìêíóòûì, åñëè v
0
≠v
n
. Â
ïîñëåäíåì ñëó÷àå ãîâîðÿò, ÷òî ïóòü
ñîåäèíÿåò v
0
è v
n
èëè, òî÷íåå, ÷òî îí
èäåò èç v
0
â v
n
.
Ïðîñòûì ïóòåì íàçûâàåòñÿ ïóòü, â êîòîðîì íåò ïîâòîðÿþùèõñÿ äóã,
íàïðèìåð ïóòü (u
1
, u
5
, u
3
, u
6
) íà ðèñ.1.18. ñ ïîñëåäîâàòåëüíîñòüþ âåð-
øèí (v
3
, v
2
, v
2
, v
1
, v
4
).
Ýëåìåíòàðíûì ïóòåì íàçûâàåòñÿ ïóòü, åñëè âñå åãî âåðøèíû ðàç-
ëè÷íû, íàïðèìåð ýëåìåíòàðíûé ïóòü (u
1
, u
3
, u
6
) ñ âåðøèíàìè (v
3
, v
2
, v
1
, v
4
)
íà ðèñ. 1.18.
Êîíòóðîì íàçûâàåòñÿ çàìêíóòûé ïóòü, êîãäà v
0
=v
n
, íàïðèìåð êîíòóð
(u
7
, u
2
, u
4
, u
2
, u
6)
ñ âåðøèíàìè (v
4
, v
3
,v
1
, v
3
, v
1
, v
4
) íà ðèñ.1.18. Ïðîñòûì
êîíòóðîì íàçûâàåòñÿ êîíòóð, â êîòîðîì âñå äóãè ðàçëè÷íû, íàïðèìåð
êîíòóð (u
1
, u
5
, u
3
, u
4
) ñ âåðøèíàìè (v
3
, v
2
, v
2
, v
1
, v
3
). Ýëåìåíòàðíûì êîí-
òóðîì íàçûâàåòñÿ êîíòóð ñ ðàçëè÷íûìè âåðøèíàìè (êðîìå íà÷àëüíîé è
êîíå÷íîé, êîòîðûå ñîâïàäàþò), íàïðèìåð, êîíòóð (u
1
, u
3
, u
4
) ñ âåðøèíà-
ìè (v
3
, v
2
, v
1
, v
3
) íà ðèñ.1.18.
Äëèíîé ïóòè µ = (u
1
, u
2
, , u
n
) íàçûâàþò ÷èñëî åãî äóã è îáîçíà÷à-
þò ÷åðåç L(µ), íàïðèìåð íà ðèñ.1.18
µ=(u
1
, u
5
, u
3
,u
6
); L(µ)=4;
µ=(u
1
, u
3
, u
4
); L(µ)=3.
Äëÿ óäîáñòâà ââîäÿò ïîíÿòèå ïóòè íóëåâîé äëèíû (èçîëèðîâàííàÿ
âåðøèíà).
Îðãðàô íàçûâàåòñÿ öèêëè÷åñêèì (êîíòóðíûì), åñëè îí ñîäåðæèò,
ïî êðàéíåé ìåðå, îäèí êîíòóð, è àöèêëè÷åñêèì (áåñêîíòóðíûì) â ïðî-
òèâíîì ñëó÷àå. Çàìåòèì, ÷òî ïåòëÿ ÿâëÿåòñÿ ñïåöèàëüíûì âèäîì êîí-
òóðà.
Ãàìèëüòîíîâ ïóòü  ýòî ýëåìåíòàðíûé ïóòü, â êîòîðîì ÷èñëî äóã íà
åäèíèöó ìåíüøå ÷èñëà âåðøèí ãðàôà V. Èíà÷å ãîâîðÿ, òàêîé ïóòü
ïðîõîäèò ÷åðåç âñå âåðøèíû â òî÷íîñòè ïî îäíîìó ðàçó. Ïðè çàïèñè ñ
ïîìîùüþ âåðøèí ãàìèëüòîíîâ ïóòü ýòî ïåðåñòàíîâêà âåðøèí ãðàôà.
Íàïðèìåð, â ãðàôå ðèñ 1.18 åñòü äâà ãàìèëüòîíîâûõ ïóòè:
Ðèñ.1.18. Îðãðàô
v
v
"
v
!
u
u
"
u
v
u
!
u
$
u
%
u
#

Страницы