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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

s
t
(s, t) (t, s)
(s, t)
V
0
s
V
0
s
n−1 C
2
n
2C
2
n
k−1
L
1
≤L
2
≤ . . . ≤L
k
k
C
c
i,j
c
i,j
≤c
i,k
+c
k,j
,
âåñîâ ñîñòàâëÿþùèõ åãî äóã (ðåáåð) ìèíèìàëüíà. Çäåñü s è
t ÿâëþòñÿ ñîîòâåòñòâåííî íà÷àëüíîé è êîíå÷íîé âåðøèíàìè.
Òàêîå ðàçëè÷èå â îáîçíà÷åíèÿõ êîíöåâûõ âåðøèí ïóòè íåîá-
õîäèìî äëÿ îðãðàôîâ, òàê êàê â ýòîì ñëó÷àå, â îòëè÷èå îò
ïðîñòûõ ãðàôîâ, êðàò÷àéøèå (s, t)- è (t, s)-ïóòè ðàçëè÷íû.
     Ïîíÿòíî, ÷òî ëþáîé ó÷àñòîê êðàò÷àéøåãî ïóòè ñàì ÿâëÿ-
åòñÿ êðàò÷àéøèì ïóòåì ìåæäó ïàðîé åãî êîíöåâûõ âåðøèí.
Çíà÷èò, åñëè íàéäåí êðàò÷àéøèé (s, t) -ïóòü, ïðîìåæóòî÷íûå
âåðøèíû êîòîðîãî îáðàçóþò ìíîæåñòâî V 0 , òî ôàêòè÷åñêè
ðåøåíà çàäà÷à îòûñêàíèÿ êðàò÷àéøèõ ïóòåé èç s âî âñå âåð-
øèíû V 0 . Ïîýòîìó ïðåäñòàâëÿåòñÿ åñòåñòâåííûì ñëåäóþùåå
îáîáùåíèå ñôîðìóëèðîâàííîé âûøå çàäà÷è.
     Íàéòè êðàò÷àéøèå ïóòè ìåæäó çàäàííîé íà÷àëüíîé âåð-
øèíîé s è âñåìè îñòàëüíûìè âåðøèíàìè ãðàôà.
Íàêîíåö, â ñàìîé øèðîêîé ïîñòàíîâêå çàäà÷à âûãëÿäèò òàê:
íàéòè êðàò÷àéøèå ïóòè ìåæäó âñåìè âåðøèíàìè ãðàôà.
     Íåòðóäíî âèäåòü, ÷òî îïðåäåëÿþùèì â ïðèâåäåííûõ ôîð-
ìóëèðîâêàõ ÿâëÿåòñÿ êîëè÷åñòâî ïàð êîíöåâûõ âåðøèí, äëÿ
êîòîðûõ ñëåäóåò íàéòè êðàò÷àéøèé ïóòü: â ïåðâîé çàäà÷å ýòî
îäíà ïàðà, âî âòîðîé n−1 ïàð, à â òðåòüåé  Cn2 ïàð (äëÿ
ïðîñòîãî ãðàôà) èëè 2Cn2 (äëÿ îðèåíòèðîâàííîãî).
     Åùå îäíà ðàçíîâèäíîñòü çàäà÷è âîçíèêàåò, êîãäà äëÿ íåêî-
òîðîé ïàðû âåðøèí êðîìå êðàò÷àéøåãî òðåáóåòñÿ íàéòè åùå
k−1 ïóòåé, äëèíû êîòîðûõ ñîñòàâëÿþò íåóáûâàþùóþ ÷èñëî-
âóþ ïîñëåäîâàòåëüíîñòü Lêð1 ≤Lêð2 ≤ . . . ≤Lêðk . Ýòà çàäà÷à èç-
âåñòíà êàê çàäà÷à ïîèñêà k êðàò÷àéøèõ ïóòåé ìåæäó äâóìÿ
çàäàííûìè âåðøèíàìè.
      îáùåì ñëó÷àå ýëåìåíòû ìàòðèöû C ìîãóò áûòü ðàç-
íûõ çíàêîâ. Íàëè÷èå îòðèöàòåëüíûõ çíà÷åíèé ñðåäè ýëåìåí-
òîâ ci,j óñëîæíÿåò ðåøåíèå çàäà÷è ïîèñêà êðàò÷àéøèõ ïóòåé.
Çàäà÷à ñòàíîâèòñÿ åùå áîëåå ñëîæíîé, åñëè â ãðàôå ïðèñóò-
ñòâóþò öèêëû ñ îòðèöàòåëüíûì ñóììàðíûì âåñîì. Íàîáîðîò,
åñëè âûïîëíÿåòñÿ òàê íàçûâàåìîå "ïðàâèëî òðåóãîëüíèêà":
ci,j ≤ci,k +ck,j , òî çàäà÷à ñòàíîâèòñÿ ñóùåñòâåííî ïðîùå è ôàê-
òè÷åñêè ìîæåò ðàññìàòðèâàòüñÿ êàê çàäà÷à ïîèñêà êðàò÷àé-
øåãî ïóòè â ãðàôå ñ ðåáðàìè (äóãàìè) åäèíè÷íîé äëèíû.



                              76

Страницы