Математические методы в экономике. Копылов Г.Н - 35 стр.

    §3. ÇÀÄÀ×À Î ÊÐÀÒ×ÀÉØÅÌ ÏÓÒÈ Â ÃÐÀÔÅ

     Ïðè ïåðåâîçêå ãðóçà èç ïóíêòà À â ïóíêò Â ìû õîòèì âûá-
ðàòü îïòèìàëüíûé ìàðøðóò. Ýòà çàäà÷à ìîæåò ðàññìàòðèâàòüñÿ
êàê çàäà÷à ïîèñêà ïóòè â ãðàôå. Çäåñü âåðøèíàìè ãðàôà ìîãóò
áûòü ãîðîäà, æåëåçíîäîðîæíûå ñòàíöèè, ïåðåêðåñòêè è ò. ä., à
ðåáðàìè ãðàôà ÿâëÿþòñÿ äîðîãè.
     Ðàññìîòðèì ïðèìåð. Çàäàí íåîðèåíòèðîâàííûé ãðàô, èìåþ-
ùèé 16 âåðøèí.
                      13    14        15   16



                      9     10        11   12



                      5     6         7    8



                      1     2         3    4


     Êàê ìîæíî ïîïàñòü èç âåðøèíû 1 â âåðøèíó 16? Çäåñü
ìîæíî âîñïîëüçîâàòüñÿ ïóòåì1→2→3→4→8→12→16, à ìîæíî
1→2→6→10→11→15→16. Åñëè íà êàæäîì øàãå ìû èäåì òîëüêî
ââåðõ èëè âïðàâî, òî âñåãî â ýòîì ïðèìåðå èìåþòñÿ 20 âîçìîæ-
íûõ ïóòåé èç âåðøèíû 1 â âåðøèíó 16. Èíîãäà ìîæåò áûòü âû-
ãîäíî ðàçðåøèòü äâèãàòüñÿ íå òîëüêî ââåðõ èëè âïðàâî. Â ýòîì
ñëó÷àå ÷èñëî ïóòåé óâåëè÷èòñÿ. Òàê, âîçìîæåí âàðèàíò
1→2→6→5→9→10→11→12→16.
     Êàê ñðàâíèâàòü âîçìîæíûå âàðèàíòû? Ýòî çàâèñèò îò ïî-
ñòàâëåííîé öåëè. Íàïðèìåð, ïðè âûáîðå ìàðøðóòà ïîåçäêè ñ
ðàáîòû äîìîé ìû ó÷èòûâàåì ìíîãî ôàêòîðîâ: íàëè÷èå ñâîáîä-
íîãî âðåìåíè, äåíåã, ñîñòîÿíèå ïîãîäû, âðåìÿ ñóòîê è ò. ä. Çäåñü
âûáîð ïðîèñõîäèò ïî ìíîãèì êðèòåðèÿì. Â ôîðìàëèçîâàííîé ìî-
äåëè áóäåì ñ÷èòàòü, ÷òî êàæäîìó ðåáðó ãðàôà ïðèïèñàíî îïðåäå-
ëåííîå ÷èñëî. Íàçîâåì ýòî ÷èñëî äëèíîé ðåáðà. Äëèíà ïóòè îïðå-
äåëÿåòñÿ êàê ñóììà äëèí âõîäÿùèõ â íåãî ðåáåð. Íàøåé çàäà÷åé
ÿâëÿåòñÿ íàõîæäåíèå êðàò÷àéøåãî ïóòè, âåäóùåãî èç îäíîé âåð-
øèíû â äðóãóþ.
     Ïîëó÷èëè ñëåäóþùóþ ìàòåìàòè÷åñêóþ çàäà÷ó.
     Äàí îðèåíòèðîâàííûé ãðàô, êàæäîìó ðåáðó ïðèïèñàíà íå-
êîòîðàÿ äëèíà. Äëèíà ïóòè èç îäíîé âåðøèíû â äðóãóþ ðàâíà

                                 35