Дискретная математика: Основы теории графов и алгоритмизация задач: Учебное пособие
Рассмотрены основные определения и понятия теории графов, необходимые для решения некоторых прикладных задач дискретной математики (определение оптимальных расстояний между множеством объектов, поиск критического пути в задаче сетевого планирования и управления, выбор предпочтительных вариантов системы по множеству критериев). Обсуждаются подходы к разработке компьютерных алгоритмов задач па основе моделей теории графов.
X(0) X(1) X(m) X(m+1) X(n2) X(n1) X(n) x (1) ... ... v(0) x(1) w(n) xin xin−1 xi2 xi1 Ðèñ. 2.4. Ïðîöåññ ïîèñêà ïóòè ìåæäó âåðøèíàìè v è w Ðàññìîòðåííûé àëãîðèòì îïèñûâàåò ïðîöåññ íàõîæäåíèÿ òðàíçè- òèâíîãî çàìûêàíèÿ à v, îòîáðàæàþùåãî äåðåâî êðàò÷àéøèõ ïóòåé, èñ- ˆ õîäÿùèõ îò ëþáîé âåðøèíû v êàê îò êîðíÿ äåðåâà. Àíàëîãè÷íî ìîæåò áûòü îïèñàí ïðîöåññ íàõîæäåíèÿ îáðàòíîãî òðàí- çèòèâíîãî çàìûêàíèÿ à v, ò. å. ìíîæåñòâà âåðøèí, èç êîòîðûõ ìîæíî ˆ ïîïàñòü â v ïî êðàò÷àéøåìó ïóòè. Ïðèìåð Äëÿ ãðàôà G íà ðèñ. 2.5,à ïîêàçàíû ìåòêè âåðøèí, íà÷èíàÿ ñ âåðøè- íû B, ïîëîæèòåëüíûå äëÿ òðàíçèòèâíîãî çàìûêàíèÿ à B è îòðèöàòåëü- ˆ íûå äëÿ îáðàòíîãî òðàíçèòèâíîãî çàìûêàíèÿ à B. ˆ à C(2,1) á) || S ||: ) ! * + D(1,1) B(0) , - ) * + , - ÃB ˆ A(3,2) E(2) à B ˆ â ÃÂ: ˆ Ö Â: ˆ E(2) D(1) A(2) D(1) B(0) B(0) C(2) A(3) C(1) Ðèñ. 2.5. Ïóòè â ãðàôå ñ íàèìåíüøèì ÷èñëîì äóã äëÿ âåðøèíû Â: à ãðàô ñ ìåòêàìè à B è à B; á ìàòðèöà ñìåæíîñòè ãðàôà S ˆ ˆ è çàìûêàíèé à ˆ B è à B; â ãðàôû çàìûêàíèé âåðøèíû  ˆ 41 Ïðèíöèïû ïîñòðîåíèÿ ìàøèííîãî àëãîðèòìà ïîèñêà òðàíçèòèâíîãî è îáðàòíîãî òðàíçèòèâíîãî çàìûêàíèé ðàññìîòðèì íà ïðèìåðå ïîëó÷å- íèÿ à B è à B íà îñíîâå àíàëèçà ìàòðèöû ñìåæíîñòè ãðàôà (ðèñ. 2.5,á). ˆ ˆ Ñïðàâà îò ìàòðèöû ñìåæíîñòè S íàõîäèòñÿ âåêòîð-ñòîëáåö äëÿ à, ˆ à âíèçó âåêòîð-ñòðîêà äëÿ È −  . Ðàññìîòðèì ïîðÿäîê çàïîëíåíèÿ ñòîë- áöà à. ˆ 1.  ïîçèöèþ  ñòîëáöà àçàïèñûâàåì íîëü (íà÷àëüíàÿ âåðøèíà). ˆ 2.  ñòðîêå  ìàòðèöû S åäèíèöà íàõîäèòñÿ â ïîçèöèÿõ, ñîîòâåò- ñòâóþùèõ âåðøèíàì, â êîòîðûå åñòü ïóòü äëèíû 1, ïîýòîìó â ïîçèöèþ D ñòîëáöà àçàïèñûâàåì 1. ˆ 3. Ñòðîêà D ìàòðèöû ñîäåðæèò 1 â ñòîëáöàõ, ñîîòâåòñòâóþùèõ âåð- øèíàì, êîòîðûå îòñòîÿò â ãðàôå îò âåðøèíû D íà îäíó äóãó, à çíà÷èò, êðàò÷àéøèé ïóòü äî íèõ îò âåðøèíû  ðàâåí 2 äóãàì. Åñëè â êëåòêàõ ñòîëáöà à, ñîîòâåòñòâóþùèõ åäèíè÷íûì ïîçèöèÿì ˆ ñòîëáöîâ â ñòðîêå D ìàòðèöû, óæå íàõîäÿòñÿ ÷èñëà, òî îíè íå ìåíÿþòñÿ (Â, D), à â ïóñòûå êëåòêè Ñ è Å çàïèñûâàåì 2. Òåì ñàìûì èñêëþ÷àþòñÿ ïåòëè (íàïðèìåð, â âåðøèíå D) è êîíòóðû (íàïðèìåð, äóãà (D,B)), è ïðîäîëæàåòñÿ ðîñò äåðåâà êðàò÷àéøèõ ïóòåé îò âåðøèíû Â. 4. Ïîâòîðÿåì ï. 3 äëÿ âåðøèí Ñ, Å è äðóãèõ, óâåëè÷èâàÿ äëèíó ïóòè íà 1, äî òåõ ïîð, ïîêà ýòî âîçìîæíî. Àíàëîãè÷íî äåéñòâóåì äëÿ ïîëó÷åíèÿ Ã−  , íî ïðè ýòîì íåîáõîäèìî ˆ òðàíñïîíèðîâàòü ìàòðèöó ñìåæíîñòè (ïîìåíÿòü ñòðîêè è ñòîëáöû ìåñ- òàìè) è èñïîëüçîâàòü ðàññìîòðåííûé àëãîðèòì èëè âûïîëíÿòü àíàëèç èñõîäíîé ìàòðèöû ïî ñòîëáöàì. ×èñëà, ïîëó÷åííûå â ñòðîêå Ã−  , äàþò ˆ ìèíèìàëüíûå äëèíû ïóòåé (÷èñëà äóã) èç òåõ âåðøèí, èç êîòîðûõ ìîæ- íî ïîïàñòü â âåðøèíó B, íàïðèìåð èç âåðøèíû Å íåëüçÿ ïîïàñòü â  íèêàêèì ïóòåì. 2.3.2. Îïèñàíèå àëãîðèòìà ïîèñêà òðàíçèòèâíîãî çàìûêàíèÿ Ìàøèííûé àëãîðèòì äîëæåí îáåñïå÷èâàòü ïîèñê òðàíçèòèâíîãî çà- ìûêàíèÿ (âåêòîð Z) äëÿ ëþáîé íà÷àëüíîé âåðøèíû (Ê) ãðàôà. Âîçìîæ- íûé âàðèàíò àëãîðèòìà ìîæåò âêëþ÷àòü ñëåäóþùèå îñíîâíûå øàãè. 1. Ââîä ìàòðèöû ñìåæíîñòè S, åå ðàçìåðà (n) è íîìåðà íà÷àëüíîé âåðøèíû (k). 2. Óñòàíîâêà íà÷àëüíîãî çíà÷åíèÿ âåêòîðà Z â öèêëå (i=1(l)n, Zi= 1). 3. Óñòàíîâêà Zk=0 (íà÷àëüíàÿ âåðøèíà), L=0 (ñ÷åò÷èê äëèíû ïóòè). 4. Öèêë àíàëèçà íåîáðàáîòàííûõ âåðøèí: 42 5. { Ñ=0 ; (ñ÷åò÷èê îáðàáîòàííûõ âåðøèí) 6. öèêë i=1(1)n (çàïîëíåíèå âåêòîðà Z) { åñëè (Zi≠L ) (âåðøèíà íå óäàëåíà íà äëèíó L, òî) { C=C+1; ( ïîäñ÷åò òàêèõ âåðøèí ) ïðîäîëæåíèå öèêëà i; } èíà÷å 7. öèêë j=1(1)n (ïî ïîçèöèÿì ñòðîêè i ìàòðèöû S) {åñëè (Sij = 1 è Zj < 0 ) (âåðøèíà j âõîäèò â çàìû- êàíèå è åùå íå âêëþ÷åíà,òî) Zj = L+1; (çàíåñåíèå äëèíû ïóòè äî âåðøèíû j â Zj) 8. } êîíåö öèêëà j) 9. } (êîíåö öèêëà i) 10. L=L+1; (èçìåíåíèå ñ÷åò÷èêà äëèíû ïóòè ) 11.} ïîêà (Ñ < n); (íå âñå âåðøèíû îáðàáîòàíû, ïðîäîëæàòü öèêë àíàëèçà) 12. Âûâîä ðåçóëüòàòà: Z (âåêòîð òðàíçèòèâíîãî çàìûêàíèÿ). 43 3. ÇÀÄÀ×È ÎÁ ÎÏÒÈÌÀËÜÍÛÕ ÐÀÑÑÒÎßÍÈßÕ Â ïðåäûäóùåé çàäà÷å ìû ñ÷èòàëè, ÷òî äëèíû âñåõ äóã ãðàôà G(V,U) áûëè ðàâíû, íàïðèìåð L(u)=1. Ðàññìîòðèì òåïåðü ñëó÷àé, êîãäà êàæäîé äóãå u ïîñòàâëåíî â ñîîòâåòñòâèå ÷èñëî L(u)>0, íàçûâàåìîå äëèíîé äóãè.  çàâèñèìîñòè îò êîíêðåòíîãî ïðèëîæåíèÿ, ýòî ÷èñëî ìîæåò áûòü ìå- ðîé ôèçè÷åñêîãî ðàññòîÿíèÿ, âðåìåíè, ñòîèìîñòè èëè äðóãîãî âàæíîãî ïàðàìåòðà. Ðàññìîòðèì îáùóþ ïîñòàíîâêó çàäà÷è îá îïòèìàëüíûõ ðàññòîÿíè- ÿõ íà ïðèìåðå çàäà÷è ñåòåâîãî ïëàíèðîâàíèÿ è óïðàâëåíèÿ (ÑÏÓ) îïå- ðàöèÿìè, íàçûâàåìûõ òàêæå çàäà÷àìè òèïà ÏÅÐÒ ( PERT). Îðãðàô ÿâëÿåòñÿ åñòåñòâåííûì ñðåäñòâîì äëÿ îïèñàíèÿ è àíàëèçà ñëîæíûõ ïðîåêòîâ, òðåáóþùèõ âûïîëíåíèÿ áîëüøîãî ÷èñëà âçàèìîñâÿ- çàííûõ îïåðàöèé (ðàáîò). Ïðîåêòîì ìîæåò áûòü, íàïðèìåð, ïðîöåññ ðàçðàáîòêè, ïîñòðîåíèÿ è ïðîâåðêè íåêîòîðîãî èçäåëèÿ, â òîì ÷èñëå è ñ èñïîëüçîâàíèåì ÑÀÏÐ (ñèñòåìû àâòîìàòèçèðîâàííîãî ïðîåêòèðîâàíèÿ) èëè ïðîöåññ ïðîåêòèðîâàíèÿ è ñòðîèòåëüñòâà çäàíèÿ, âêëþ÷àÿ ýòàïû ïîëó÷åíèÿ è ïîäãîòîâêè ìåñòà ñòðîèòåëüñòâà.  îáùåì ñëó÷àå ïðåäïî- ëîæèì, ÷òî ðàññìàòðèâàåòñÿ íåêîòîðûé ïðîåêò P è ìíîæåñòâî âñåõ îïå- ðàöèé, ñâÿçàííûõ ñ âûïîëíåíèåì ïðîåêòà, ìîæíî ðàçäåëèòü íà îòäåëü- íûå íåïåðåñåêàþùèåñÿ îïåðàöèè P{a1,a2, ... ,an}. Õîòÿ íåêîòîðûå îïåðàöèè ìîãóò áûòü íåçàâèñèìû äðóã îò äðóãà, â îáùåì ñëó÷àå ìåæäó íèìè ñóùåñòâóåò çàâèñèìîñòü ïî âðåìåíè, íàïðè- ìåð îïåðàöèÿ ai äîëæíà çàêîí÷èòüñÿ, ÷òîáû ìîãëà íà÷àòüñÿ îïåðàöèÿ aj. Åñëè çàäàíû âñå òàêèå çàâèñèìîñòè, òî èõ óäîáíî ïðåäñòàâèòü â âèäå îðãðàôà, êàê ïîêàçàíî íà ðèñ. 2.6. Êàæäàÿ äóãà ãðàôà ñîîòâåòñòâóåò îäíîé îïåðàöèè, à êàæäàÿ âåðøèíà, íàçûâàåìàÿ ñîáûòèåì, ñîîòâåòñòâóåò íåêîòîðîìó ìîìåíòó âðåìåíè. Äëÿ âûïîëíåíèÿ îïåðàöèè ài âûäåëÿåòñÿ íåêîòîðîå âðåìÿ t(ai), ÷òî îòðàæåíî ÷èñëàìè íà äóãàõ ãðàôà. Äëèíà (ò. å. ñóììà âðåìåííûõ èí- òåðâàëîâ) ëþáîãî ïóòè èç v1 â vi ñîîòâåòñòâóåò íèæíåé ãðàíèöå âðåìå- íè, èçìåðÿåìîãî îò íà÷àëà ïðîåêòà äî íàñòóïëåíèÿ ñîáûòèÿ vi, ïîñëå 44 êîòîðîãî ìîãóò áûòü íà÷àòû îïåðàöèè, èìåþùèå vi â êà÷åñòâå íà÷àëü- íîé âåðøèíû. v"(5) 5 v$(10) 4 3 3 2 2 v(0) v&(13) 3 v (3) 2 v#(8) 4 1 2 3 v!(4) 4 v%(8) Ðèñ. 3.1. Ãðàô âûïîëíåíèÿ îïåðàöèé ïðîåêòà Ïðè ðàñ÷åòàõ êàæäîé âåðøèíå óäîáíî ïîñòàâèòü â ñîîòâåòñòâèå ÷èñ- ëî (âðåìÿ) ñëåäóþùèì îáðàçîì: Ò(v1)=0, T(vi)=max{t(µ)} (i≠1), ãäå t(µ) îçíà÷àåò äëèíó ïóòè è ìàêñèìóì îïðåäåëÿåòñÿ ïî âñåì ïóòÿì èç v1 â vi. Äëèíîé ïóòè µ íàçûâàåòñÿ ñóììà äëèí äóã, âõîäÿùèõ â µ: L(µ) = ∑ L(u ) . u∈µ Äëèííåéøèé ïî âðåìåíè ïóòü îò íà÷àëüíîãî ñîáûòèÿ v1 äî êîíå÷- íîãî ñîáûòèÿ vn íàçûâàåòñÿ êðèòè÷åñêèì ïóòåì, êîòîðûé ìîæåò áûòü íå åäèíñòâåííûì, íàïðèìåð äëÿ ãðàôà íà ðèñ. 3.1 åñòü äâà êðèòè÷åñêèõ ïóòè (ïî âåðøèíàì ãðàôà): µ1 = (v1 , v2 , v4 , v5 , v6 , v8 ), L (µ1 ) = 13, µ 2 = (v1 , v2 , v4 , v6 , v8 ), L (µ 2 ) = 13. Äëèíà êðèòè÷åñêîãî ïóòè ñîîòâåòñòâóåò êðàò÷àéøåìó âðåìåíè, çà êîòîðîå ìîãóò áûòü âûïîëíåíû âñå îïåðàöèè ïðîåêòà, à çíà÷èò, è âåñü ïðîåêò â öåëîì. Çàìåòèì, ÷òî ïî ñâîåé ïðèðîäå ãðàô, ïðåäñòàâëÿþùèé ïðîöåññ âû- ïîëíåíèÿ îïåðàöèé, ÿâëÿåòñÿ àöèêëè÷åñêèì. Íàëè÷èå öèêëà ñîçäàëî áû íåâîçìîæíóþ ñèòóàöèþ, êîãäà íè îäíà èç îïåðàöèé öèêëà íå ìîãëà áû íà÷àòüñÿ ïåðâîé, ïîñêîëüêó ëþáàÿ èç íèõ çàâèñèò îò äðóãîé îïåðàöèè. 45  äàëüíåéøåì ìû áóäåì ïîëüçîâàòüñÿ òåðìèíîëîãèåé, ñîîòâåòñòâó- þùåé ðàññòîÿíèÿì, õîòÿ âñåãäà íóæíî ïîìíèòü è î äðóãèõ èíòåðïðåòà- öèÿõ. Îòìåòèì äâå âàæíåéøèå õàðàêòåðèñòèêè äëèíû, ñóùåñòâåííûå äëÿ äàëüíåéøåãî ðàññìîòðåíèÿ. 1. Äëèíà äîëæíà áûòü àääèòèâíà (äëèíà ñîâîêóïíîñòè äóã ðàâíà ñóììå äëèí îòäåëüíûõ äóã). 2. Äëèíà äîëæíà èñïîëüçîâàòüñÿ â êà÷åñòâå öåëåâîé ôóíêöèè, êîòî- ðóþ íåîáõîäèìî îïòèìèçèðîâàòü (ìèíèìèçèðîâàòü èëè ìàêñèìèçèðî- âàòü) ïðè îãðàíè÷åíèÿõ íà äîïóñòèìûå ìíîæåñòâà äóã. Äëÿ ãðàôà ñ êîíòóðàìè (öèêëè÷åñêîãî) ìîæíî ãîâîðèòü òîëüêî î çà- äà÷å îòûñêàíèÿ ìèíèìàëüíûõ ïóòåé ãðàôà, à â àöèêëè÷åñêîì ãðàôå ìîæíî èñêàòü êàê ìèíèìàëüíûé, òàê è ìàêñèìàëüíûé ïóòü ìåæäó âåðøèíàìè ãðàôà. 3.1. Ïîèñê ìèíèìàëüíûõ ïóòåé â ãðàôå Ïîñòàíîâêà çàäà÷è. Äëÿ ïðîèçâîëüíîãî îðãðàôà G(V, U), ãäå äëÿ ∀u ∈U ñîïîñòàâëåíî ÷èñëî L(u) > 0 (äëèíà äóãè), íåîáõîäèìî íàéòè ïóòü µ ìèíèìàëüíîé äëèíû, ñîåäèíÿþùèé âåðøèíó v0 c âåðøèíîé vn. 3.1.1. Ìåòîä ðåøåíèÿ çàäà÷è ïîèñêà ìèíèìàëüíîãî ïóòè Ñóùåñòâóåò íåñêîëüêî ìåòîäîâ ðåøåíèÿ ýòîé çàäà÷è, ñðåäè êîòîðûõ ðàññìîòðèì àëãîðèòì Ôîðäà, îïèñûâàåìûé ñëåäóþùèìè ïðàâèëàìè, êîòîðûå ìîæíî ðàçäåëèòü íà äâà ýòàïà: ïðÿìîé õîä âû÷èñëåíèå è íà- çíà÷åíèå ìåòîê âåðøèíàì ãðàôà; îáðàòíûé õîä îïðåäåëåíèå ìèíè- ìàëüíîãî ïóòè. Ïðÿìîé õîä. 1. Íàçíà÷åíèå íîìåðîâ âåðøèíàì. Ïåðåèìåíîâàòü âåðøèíû ãðà- ôà G òàê, ÷òîáû èñõîäíàÿ âåðøèíà ïîëó÷èëà íîìåð 0, åñëè ýòî íåîá- õîäèìî. 2. Ïðèñâîåíèå íà÷àëüíûõ ìåòîê. Ïðèñâîèòü êàæäîé âåðøèíå vi ìåò- êó λi òàê, ÷òîáû λ0 = 0, λi = ∞ ïðè i > 0 (ïîä ñèìâîëîì ∞ çäåñü ñëåäóåò ïîíèìàòü äîñòàòî÷íî áîëüøîå ïîëîæèòåëüíîå çíà÷åíèå). 3. Óìåíüøåíèå ìåòîê. Íàéòè òàêóþ äóãó (vi , v j ) , äëÿ êîòîðîé λ j λ i > L (vi , v j ) . Ó âåðøèíû v j çàìåíèòü ìåòêó λ j íà íîâóþ ìåòêó λ ' j = λi + L (vi , v j ) , åñëè λ'j < λj. 4. Ïåðåñ÷åò ìåòîê. Ïðèìåíÿòü ïðàâèëî 3 äî òåõ ïîð, ïîêà äëÿ êàæäîé äóãè (vi , v j ) íå ñòàíåò ñïðàâåäëèâûì íåðàâåíñòâî λj λi ≥ L (vi , v j ) . 46 Îáðàòíûé õîä. 5.  ìíîæåñòâå Ã1vn íàéòè òàêóþ âåðøèíó v p1 , ÷òî λn = λp + L(vp , vn) èëè λn λp = L(vp , vn). 1 1 1 1 Àíàëîãè÷íî, â ìíîæåñòâå Ã1vp íàéòè òàêóþ âåðøèíó vp , ÷òîáû áûëî 1 2 ñïðàâåäëèâî ðàâåíñòâî λp = λp + L(vp ,vp ) èëè λp λp = L(vp ,vp ) è ò. ä. 1 2 2 1 1 2 2 1 Ïîñëå íåêîòîðîãî ÷èñëà øàãîâ âåðøèíà vp ñîâïàäåò ñ âåðøèíîé v0. k Ïóòü µ = ( v0=vp ,vp , ... ,vp , vp , vn ) ìèíèìàëüíûé è åãî äëèíà k k1 2 1 L(µ) = λn. Ïðèìåð Ïðîèëëþñòðèðóåì ðàáîòó àëãîðèòìà ïîèñêà ìèíèìàëüíîãî ïóòè äëÿ ãðàôà íà ðèñ. 3.2. v[∞,7] 4 v"[∞,15,11] 7 15 2 8 9 v![∞,9] 16 v$[∞,25,19] v[0] 5 6 8 7 2 4 3 4 6 v [∞,8] v#[∞,14,13] Ðèñ. 3.2. Îðãðàô ñ äëèíàìè äóã è ìåòêàìè âåðøèí Ýòàï 1 (ïðÿìîé õîä) âû÷èñëåíèå íîâûõ ìåòîê ïðè âåðøèíàõ. Ïðèïèñûâàåì âåðøèíå v0 ìåòêó 0, à îñòàëüíûì âåðøèíàì ìåòêó ∞. Íàõîäèì íîâûå ìåòêè, êîòîðûå ïîêàçàíû â êâàäðàòíûõ ñêîáêàõ ïðè âåð- øèíàõ ãðàôà: 1. L(v0, v1)=7, λ'1=0+7< λ1=∞, îñòàåòñÿ λ1=7; 2. L(v0, v2)=8, λ'2=0+8< λ2=∞, îñòàåòñÿ λ2=8; 3. L(v0, v3)=9, λ'3=0+9< λ3=∞, îñòàåòñÿ λ3=9; 4. L(v0, v4)=15, λ'4=0+15< λ4=∞; 5. L(v1, v4)=4, λ'4=7+4=11< λ4=15, îñòàåòñÿ λ4=11; 6. L(v2, v3)=3, λ'3=8+3=11 > λ3=9; 47 7. L(v2, v5)=6, λ'5=8+6=14< λ5=∞, 8. L(v3, v4)=2, λ'4=9+2=11= λ4=11, 9. L(v3, v5)=4, λ'5=9+4=13 < λ5=14, îñòàåòñÿ λ5=13; 10. L(v3, v6)=16, λ'6=9+16=25 < λ6=∞, 11. L(v4, v6)=8, λ'6=11+8=19 < λ6=25, 12. L(v5, v3)=2, λ'3=13+2=15 > λ3=9, 13. L(v5, v6)=6, λ'6=13+6=19, îñòàåòñÿ λ6=19. Ýòàï 2 (îáðàòíûé õîä) îïðåäåëåíèå ìèíèìàëüíîãî ïóòè. Èç âåðøèíû v6 íàõîäèì: 1. λ6 L(v4, v6)=198=11=λ4, λ4 L(v1, v4)=114=7=λ1, λ1 L(v0, v1)=77=0=λ0, çíà÷èò, ïóòü µ=( v0, v1, v4, v6) ìèíèìàëüíûé. 2. λ6 L(v3, v6)=1916=3<λ3=9, çíà÷èò, äóãà (v3, v6) íå âõîäèò â ìèíèìàëüíûé ïóòü. 3. λ6 L(v5, v6)=196=13=λ5, λ5 L(v3, v5)=134=9=λ3, λ3 L(v0, v3)=99=0=λ0, çíà÷èò, ïóòü µ = ( v0, v3, v5, v6) ìèíèìàëüíûé. 4. Òàê æå ìîæíî äîêàçàòü, ÷òî ïóòü µ=( v0, v3, v4, v6) ìèíèìàëüíûé. 3.1.2. Îáîñíîâàíèå àëãîðèòìà Ôîðäà Äîêàæåì, ÷òî ïîñëå êîíå÷íîãî ÷èñëà ïðèìåíåíèé ïðàâèëà 3 äëÿ êàæ- äîé äóãè ãðàôà ñòàíåò ñïðàâåäëèâûì íåðàâåíñòâî λjλi ≤ L(vi,vj) (ïðàâèëî 4). Íà ëþáîì øàãå èçìåíåíèÿ ìåòêà λj>0 ïðè j≠0 (ìåòêà λ0=0), ÷òî ìîæ- íî äîêàçàòü ïî èíäóêöèè. 1. Äåéñòâèòåëüíî, ïðè ïåðâîì ïðèìåíåíèè ïðàâèëà 3 áóäåò èçìåíå- íà ìåòêà λk ó îäíîé èç âåðøèí vk, ñìåæíûõ ñ âåðøèíîé v0 (vk∈Ãv0). Ýòà âåðøèíà vk ïîëó÷èò íîâóþ ìåòêó λk = L(v0,vk)>0, íàïðèìåð v4[15]. Ïðåäïîëîæèì, ÷òî ïîñëå ïðèìåíåíèÿ ïðàâèëà 3 m ðàç (m>1), ñòàíåò ñïðàâåäëèâûì óòâåðæäåíèå, ÷òî λ0=0, λi>0 äëÿ i>0. Íà m+1-ì øàãå êà- êàÿ-òî âåðøèíà vj ïîëó÷èò íîâóþ ìåòêó λj = λi + L(vi,vj). Íî â ñèëó ïðåäïîëîæåíèÿ èíäóêöèè λi ≥ 0, êðîìå òîãî, L(vi,vj)>0, ïîýòîìó λj>0. 48 2. Íåòðóäíî çàìåòèòü, ÷òî ïðè êàæäîì èçìåíåíèè ìåòêà âåðøèíû ãðàôà óìåíüøàåòñÿ íà ïîëîæèòåëüíóþ âåëè÷èíó, íå ìåíüøóþ, ÷åì ìè- íèìàëüíàÿ ðàçíîñòü äëèí ïóòåé ãðàôà. Èç ýòèõ äâóõ óòâåðæäåíèé ñëåäóåò, ÷òî ìåòêà ëþáîé âåðøèíû ãðàôà ìîæåò èçìåíÿòüñÿ ëèøü êîíå÷íîå ÷èñëî ðàç. Òàê êàê âåðøèí êîíå÷íîå ìíîæåñòâî, òî ïðàâèëî 3 ìîæåò ïðèìåíÿòüñÿ ëèøü êîíå÷íîå ÷èñëî ðàç. Ðàññìîòðèì îáðàòíûé ýòàï è ïîêàæåì, ÷òî, ïðèìåíÿÿ ïðàâèëî 5, ìû ìîæåì íàéòè ìèíèìàëüíûå ïóòè. Äåéñòâèòåëüíî, òàê êàê â ðåçóëüòàòå ïðèìåíåíèÿ ïðàâèëà 3 ìåòêà λn ìîíîòîííî óìåíüøàåòñÿ, òî ìû ïðèäåì ê òàêîé âåðøèíå vp (ýòî íà÷àëî 1 äóãè, ñ ïîìîùüþ êîòîðîé â ïîñëåäíèé ðàç óìåíüøèëàñü ìåòêà λn), ÷òî λn λp = L(vp , vn), íàïðèìåð λ6 λ4= L(v4, v6). 1 1 Ïî ýòîé æå ïðè÷èíå íàéäåòñÿ âåðøèíà vp , äëÿ êîòîðîé ñîáëþäàåòñÿ 2 ñîîòâåòñòâèå λp λp = L(vp ,vp ) è ò. ä. 1 2 2 1 Ïî óñëîâèþ çàäà÷è äëèíà äóãè ãðàôà L(vi, vj)>0, ïîýòîìó ìåòêè λn, λp , λp , ... îáðàçóþò ñòðîãî óáûâàþùóþ ïîñëåäîâàòåëüíîñòü íåîòðèöà- 1 2 òåëüíûõ ÷èñåë, îòëè÷àþùèõñÿ äðóã îò äðóãà íà âåëè÷èíó, áîëüøóþ èëè ðàâíóþ äëèíå êðàò÷àéøåé äóãè ãðàôà. Ñëåäîâàòåëüíî, ïðè íåêîòîðîì k ïîëó÷èì λp = 0, vp = v0. (Âåðøèíà v0 âûäåëåíà òåì, ÷òî åé â ñèëó ïðàâè- k k ëà 1 ñ ñàìîãî íà÷àëà ïðèñâîåíà ìåòêà λ0=0 è â ôîðìèðîâàíèè ýòîé ìåòêè íå ó÷àñòâóþò äóãè ãðàôà). Ïîêàæåì, ÷òî µ = ( v0=vp ,vp , ... ,vp , vp , vn ) ìèíèìàëüíûé ïóòü ñî k k1 2 1 çíà÷åíèåì äëèíû ïóòè L(µ)=λn, ò. å. çíà÷åíèå L( v0,vi , vi , ,vi , vn) ëþ- 1 2 m áîãî äðóãîãî ïóòè ìåæäó v0 è vn íå ìåíüøå λn. Èìååì íåðàâåíñòâà (ïî ïðàâèëó 4): λi λ0 ≤ L(v0, vi ), 1 1 + λi λi ≤ L(vi ,vi ), 2 1 1 2 .., + λn λi ≤ L(vi , vn). m m Ñêëàäûâàÿ ýòè íåðàâåíñòâà, ïîëó÷èì (ïðè λ0=0) λn ≤ L( v0,vi , vi , ,vi , vn). 1 2 m 49  òî æå âðåìÿ ïî ïîñòðîåíèþ ïóòè µ èìååì L(µ) = λn, îòêóäà ñëåäóåò L(µ) ≤ L( v0,vi , vi , ,vi , vn), 1 2 m ò. å. µ = ( v0=vp ,vp , ... ,vp , vp , vn ) ìèíèìàëüíûé ïóòü. k k1 2 1 Êàê ïîêàçàíî â ïðèìåðå, ìèíèìàëüíûé ïóòü â ãðàôå ìîæåò áûòü íå îäèí. 3.1.3. Ïîñòðîåíèå ìàøèííîãî àëãîðèòìà ïîèñêà ìèíèìàëüíûõ ïóòåé â ãðàôå Èñõîäíûìè äàííûìè ÿâëÿþòñÿ ìàòðèöà ñìåæíîñòè ãðàôà äëÿ n âåð- øèí (||S|| n×n) è ìàòðèöà äëèí äóã ãðàôà (||L|| n×n), íàïðèìåð äëÿ ãðàôà íà ðèñ. 3.2 ýòè ìàòðèöû èìåþò âèä, ïðèâåäåííûé íà ðèñ. 3.3. S: L: 0 1 2 3 4 5 6 0 1 2 3 4 5 6 0 0 1 1 1 1 0 0 0 0 7 8 9 15 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 4 0 0 2 1 0 0 1 0 1 0 2 7 0 0 3 0 6 0 3 1 0 0 0 1 1 1 3 5 0 0 0 2 4 16 4 0 0 0 0 0 0 1 4 0 0 0 0 0 0 8 5 0 0 0 1 0 0 1 5 0 0 0 2 0 0 6 6 0 0 0 0 0 1 0 6 0 0 0 0 0 4 0 Ðèñ. 3.3. Ìàòðèöû ñìåæíîñòè è äëèí äóã ãðàôà Ìàòðèöà äëèí äóã ãðàôà ïî ñóòè âêëþ÷àåò âñþ èíôîðìàöèþ î ãðà- ôå, ÷òî äåëàåò ìàòðèöó ñìåæíîñòè èçëèøíåé äëÿ äàííîé çàäà÷è. Äëÿ ïîñòðîåíèÿ àëãîðèòìà íåîáõîäèìû âåêòîð ìåòîê âåðøèí (Ì) è ìàòðèöà ðåçóëüòàòîâ, ñîäåðæàùàÿ âåðøèíû êðàò÷àéøèõ ïóòåé (||Ê|| n×n). Ïîñòðîåíèå ìàøèííîãî àëãîðèòìà îñíîâàíî íà àíàëèçå ìàòðèöû äëèí äóã ãðàôà (L), ïîñòåïåííîì çàïîëíåíèè âåêòîðà ìåòîê âåðøèí (Ì) íîâûìè ìåòêàìè è ïîëó÷åíèè ìàòðèöû êðàò÷àéøèõ ïóòåé (Ê).  ðåçóëüòàòå âåêòîð ìåòîê (Ì) îòðàæàåò ìèíèìàëüíûå ðàññòîÿ- íèÿ ìåæäó íà÷àëüíîé âåðøèíîé v0 è îñòàëüíûìè âåðøèíàìè. Ìàò- ðèöà êðàò÷àéøèõ ïóòåé (Ê) îòðàæàåò èíôîðìàöèþ î ïîäãðàôå ìèíè- ìàëüíûõ ïóòåé èñõîäíîãî ãðàôà ìåæäó íà÷àëüíîé âåðøèíîé v0 è êî- íå÷íîé âåðøèíîé vn. 50