Элементы теории графов. Домнин Л.Н. - 30 стр.

äàåò èñêîìîå ðàçáèåíèå ìíîæåñòâà âåðøèí ãðàôà G íà ïîä-
ìíîæåñòâà V0 , V1 , . . . , V5 , à ïîñëåäíÿÿ ñòðîêà  ïîðÿäêîâóþ
ôóíêöèþ. Èçîáðàæåíèå ðàññìàòðèâàåìîãî ãðàôà, îòðàæàþ-
ùåå ïîëó÷åííîå ðàçáèåíèå, äàíî íà ðèñ 1.18 (ñì. ãðàô G1 ).


   1.7. Ìàðøðóòû, öåïè è ïðîñòûå öåïè
     ðàçä. 1.3 äàíû ïîíÿòèÿ öåïè è ïðîñòîé öåïè, êàê ÷åðå-
äóþùåéñÿ ïîñëåäîâàòåëüíîñòè âåðøèí è ðåáåð, ïðè÷åì â öåïè
ïîïàðíî ðàçëè÷íû âñå ðåáðà, à â ïðîñòîé öåïè  âñå âåðøèíû.
Ìàðøðóò îïðåäåëÿåòñÿ òàê æå, çà èñêëþ÷åíèåì îãðàíè÷åíèé
íà ïîâòîðåíèå âåðøèí è ðåáåð: äîïóñêàåòñÿ ïîâòîðåíèå êàê
âåðøèí, òàê è ðåáåð. Òàêèì îáðàçîì, èìååì òðèàäó, îòíîøå-
íèÿ ìåæäó ýëåìåíòàìè êîòîðîé ìîæíî ïðåäñòàâèòü ñõåìîé:

                 Ìàðøðóò Öåïü Ïðîñòàÿ öåïü         .

   Ïðèìåíèòåëüíî ê îðèåíòèðîâàííûì ãðàôàì ñóùåñòâóþò
àíàëîãè÷íûå ïîíÿòèÿ: îðèåíòèðîâàííûé ìàðøðóò (îðìàðø-
ðóò), îðèåíòèðîâàííàÿ öåïü (îðöåïü) è îðèåíòèðîâàííàÿ ïðî-
ñòàÿ öåïü (ïðîñòàÿ îðöåïü). Äëÿ ïîñëåäíåé ÷àñòî èñïîëü-
çóåòñÿ äðóãîé áîëåå êîðîòêèé òåðìèí ïóòü.
   Ïðè ðàññìîòðåíèè îðãðàôîâ èñïîëüçóþò òàêæå ïîíÿòèÿ:
ïîëóìàðøðóò, ïîëóöåïü è ïîëóïóòü, êîòîðûå îòëè÷àþòñÿ îò
ñîòâåòñòâóþùèõ èì îðìàðøðóòà, îðöåïè è ïóòè òåì, ÷òî äî-
ïóñêàþòñÿ ðàçíîíàïðàâëåííûå äóãè. Íàïðèìåð, ïîñëåäîâàòåëü-
íîñòü äóã (v1 , v2 ), (v3 , v2 ), (v3 , v4 ) îïðåäåëÿåò ïîëóïóòü ñ íà-
÷àëüíîé âåðøèíîé v1 è êîíå÷íîé âåðøèíîé v4 .
   Ïðèâåäåííàÿ òåðìèíîëîãèÿ â îñíîâíîì ñîîòâåòñòâóåò ïðè-
íÿòîé, íàïðèìåð â [1]. Âîîáùå æå äëÿ ðàññìàòðèâàåìûõ ïîíÿ-
òèé èñïîëüçóþò è äðóãèå òåðìèíû.
   Â äàëüíåéøåì ñëîâî îðèåíòèðîâàííûé ïðèìåíèòåëüíî ê
ìàðøðóòó èëè öåïè áóäåì îïóñêàòü, åñëè èç êîíòåêñòà ÿñíî, î
êàêîì ãðàôå èäåò ðå÷ü.




                                30