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

                     Îñíîâíûå ïîíÿòèÿ

                          Î ãðàôàõ
      ðÿäå ñëó÷àåâ íóæíóþ èíôîðìàöèþ ìîæíî ïðåäñòàâèòü â
âèäå ãðàôà.
     Ãðàô ñîñòîèò èç äâóõ ìíîæåñòâ: ìíîæåñòâà âåðøèí è ìíî-
æåñòâà ðåáåð (äóã), ñîåäèíÿþùèõ ýòè âåðøèíû.  îáùåì ñëó÷àå
âåðøèíû ãðàôà ñîîòâåòñòâóþò êàêèì-òî îáúåêòàì è èçîáðàæà-
þòñÿ íà ñõåìå â âèäå òî÷åê, êðóãîâ, ïðÿìîóãîëüíèêîâ, à ðåáðà
ñîåäèíÿþò ýòè îáúåêòû è èçîáðàæàþòñÿ â âèäå îòðåçêîâ, äóã,
ëèíèé, ñòðåëîê. Íàïðèìåð, ñõåìà æåëåçíûõ èëè àâòîìîáèëüíûõ
äîðîã ìîæåò áûòü ïðåäñòàâëåíà â âèäå ãðàôà. Çäåñü âåðøèíû
ãðàôà — ýòî ãîðîäà, à ðåáðà — ñîåäèíÿþùèå èõ äîðîãè. Àëãîðèò-
ìû ðåøåíèÿ ðàçëè÷íûõ çàäà÷ ÷àñòî ïðåäñòàâëÿþò â âèäå áëîê-
ñõåì. Îòäåëüíûå áëîêè ñîîòâåòñòâóþò øàãàì àëãîðèòìà è ÿâëÿ-
þòñÿ âåðøèíàìè ãðàôà. Ñòðåëêè óêàçûâàþò ïîðÿäîê âûïîëíå-
íèÿ ýòèõ áëîêîâ è ÿâëÿþòñÿ ðåáðàìè ãðàôà. Ãðàôû ìîæíî èñ-
ïîëüçîâàòü, ÷òîáû îáúÿñíèòü ñòðóêòóðó êàêîé-ëèáî îðãàíèçà-
öèè, âëèÿíèå ðàçëè÷íûõ ôàêòîðîâ â ñëîæíîé ñèñòåìå è ò. ä.
      ðÿäå ñëó÷àåâ âåðøèíàì è (èëè) ðåáðàì ãðàôà ïðèïèñàíû
÷èñëà. Èíîãäà èõ íàçûâàþò âåñàìè, à ñàìè ãðàôû âçâåøåííûìè.
Íàïðèìåð, ïðè ïëàíèðîâàíèè ïóòåøåñòâèÿ ìîæíî ïîñòðîèòü ãðàô,
âåðøèíàì êîòîðîãî ñîîòâåòñòâóþò ãîðîäà, êîòîðûå ïëàíèðóåòñÿ
ïîñåòèòü, ðåáðàì ñîîòâåòñòâóþò âîçìîæíîñòè ïåðååçäà èç ãîðîäà
â ãîðîä, à âåñ ðåáðà ðàâåí ñòîèìîñòè ïðîåçäà ïî ýòîìó ðåáðó.
     Ñóùåñòâóþò îðèåíòèðîâàííûå è íåîðèåíòèðîâàííûå ãðàôû.
 îðèåíòèðîâàííîì ãðàôå ìû ðàçëè÷àåì ðåáðî (a,b) è ðåáðî (b,a).
Çäåñü îðèåíòèðîâàííîå ðåáðî (a,b) èäåò èç âåðøèíû a â âåðøèíó
b: a→b, à îðèåíòèðîâàííîå ðåáðî (b,a) èäåò èç âåðøèíû b â
âåðøèíó a: b→a. Â íåîðèåíòèðîâàííîì ãðàôå ýòè ðåáðà íå ðàçëè-
÷àþòñÿ è ðåáðî (a,b) â ðàâíîé ñòåïåíè ñîåäèíÿåò îáå âåðøèíû:
a↔b. Îðèåíòèðîâàííûå ðåáðà ÷àñòî íàçûâàþò äóãàìè. Åñëè ðàñ-
ñìàòðèâàòü ñõåìó àâòîìîáèëüíûõ äîðîã, òî åå, êàê ïðàâèëî, íàäî
ñ÷èòàòü íåîðèåíòèðîâàííûì ãðàôîì. À åñëè ðàññìàòðèâàòü ñõåìó
âîäíîãî òðàíñïîðòà, òî (ñ ó÷åòîì òå÷åíèÿ) ëó÷øå ïðèìåíèòü
îðèåíòèðîâàííûé ãðàô. Ïóòåøåñòâîâàòü íà ëîäêàõ èëè ïëîòàõ
ìîæíî òîëüêî ïî òå÷åíèþ. Äàæå åñëè ìû ìîæåì ïëûòü ïðîòèâ
òå÷åíèÿ, òî ñêîðîñòü, çàòðà÷åííûå óñèëèÿ è âðåìÿ ìîãóò ñóùå-

                              8