Лекция 5. Задача маршрутизации. Алгоритм Флойда-Уоршалла_ Туэга_ Мерлина-Сигалла_ Чанди-Мисры

ÐàñïðåäåëåííûåàëãîðèòìûËÅÊÒÎÐ: Â.À. ÇàõàðîâËåêöèÿ 5.Çàäà÷à ìàðøðóòèçàöèè.Ìàðøðóòèçàöèÿ íà îñíîâå óçëîâ-àäðåñàòîâ.Çàäà÷à ïîñòðîåíèÿ êðàò÷àéøèõ ïóòåé äëÿ âñåõïàð âåðøèí.Àëãîðèòì ÔëîéäàÓîðøàëëà.Àëãîðèòì Òóýãà.Àëãîðèòì ÌåðëèíàÑèãàëëà.Àëãîðèòì ×àíäèÌèñðû.Çàäà÷à ìàðøðóòèçàöèè îáùåì ñëó÷àå ïðîöåññ (óçåë â êîìïüþòåðíîé ñåòè)íåïîñðåäñòâåííî íå ñîåäèíåí êàíàëàìè ñâÿçè ñ êàæäûì äðóãèìïðîöåññîì.Èç êàæäîãî óçëà ïàêåòû èíôîðìàöèè ìîãóò íåïîñðåäñòâåííîïåðåäàâàòüñÿ òîëüêî íåêîòîðîìó ïîäìíîæåñòâó äðóãèõ óçëîâ,êîòîðûå íàçûâàþòñÿ ñîñåäÿìè ýòîãî óçëà.Ìàðøðóòèçàöèÿ ýòî ïðîöåäóðà ïðèíÿòèÿ ðåøåíèÿ î òîì,êàêîìó ñîñåäó (èíîãäà íå åäèíñòâåííîìó) ñëåäóåò ïåðåäàòüïàêåò, ÷òîáû îí â êîíöå êîíöîâ áûë äîñòàâëåí ïî íàçíà÷åíèþ.Öåëü, êîòîðàÿ ñòàâèòñÿ ïðè ïðîåêòèðîâàíèè àëãîðèòìàìàðøðóòèçàöèè, ñîñòîèò â òîì, ÷òîáû ñíàáäèòü êàæäûé óçåëïðîöåäóðîé, êîòîðàÿ ñìîæåò âûïîëíÿòü ýòó ôóíêöèþ èãàðàíòèðîâàòü äîñòàâêó êàæäîãî ïàêåòà ïî íàçíà÷åíèþ.Çàäà÷à ìàðøðóòèçàöèè êàæäîì óçåë äîëæíà õðàíèòüñÿ íåêîòîðàÿ èíôîðìàöèÿ îòîïîëîãèè ñåòè, è ëîêàëüíàÿ ïðîöåäóðà äîëæíà ïðèíèìàòüðåøåíèå íà îñíîâå ýòîé èíôîðìàöèè.Ýòà èíôîðìàöèÿ ïðåäñòàâëåíà â òàáëèöåé ìàðøðóòèçàöèè .Çàäà÷ó ìàðøðóòèçàöèè ìîæíî ðàçáèòü íà äâå àëãîðèòìè÷åñêèåñîñòàâëÿþùèå:Çàäà÷à ìàðøðóòèçàöèè êàæäîì óçåë äîëæíà õðàíèòüñÿ íåêîòîðàÿ èíôîðìàöèÿ îòîïîëîãèè ñåòè, è ëîêàëüíàÿ ïðîöåäóðà äîëæíà ïðèíèìàòüðåøåíèå íà îñíîâå ýòîé èíôîðìàöèè.Ýòà èíôîðìàöèÿ ïðåäñòàâëåíà â òàáëèöåé ìàðøðóòèçàöèè .Çàäà÷ó ìàðøðóòèçàöèè ìîæíî ðàçáèòü íà äâå àëãîðèòìè÷åñêèåñîñòàâëÿþùèå:1.

Âû÷èñëåíèå òàáëèö. Òàáëèöû ìàðøðóòèçàöèè äîëæíûáûòü âû÷èñëåíû ïðè èíèöèàëèçàöèè ñåòè è äîëæíûîáíîâëÿòüñÿ ïðè èçìåíåíèè òîïîëîãèè ñåòè.Çàäà÷à ìàðøðóòèçàöèè êàæäîì óçåë äîëæíà õðàíèòüñÿ íåêîòîðàÿ èíôîðìàöèÿ îòîïîëîãèè ñåòè, è ëîêàëüíàÿ ïðîöåäóðà äîëæíà ïðèíèìàòüðåøåíèå íà îñíîâå ýòîé èíôîðìàöèè.Ýòà èíôîðìàöèÿ ïðåäñòàâëåíà â òàáëèöåé ìàðøðóòèçàöèè .Çàäà÷ó ìàðøðóòèçàöèè ìîæíî ðàçáèòü íà äâå àëãîðèòìè÷åñêèåñîñòàâëÿþùèå:1. Âû÷èñëåíèå òàáëèö.

Òàáëèöû ìàðøðóòèçàöèè äîëæíûáûòü âû÷èñëåíû ïðè èíèöèàëèçàöèè ñåòè è äîëæíûîáíîâëÿòüñÿ ïðè èçìåíåíèè òîïîëîãèè ñåòè.2. Ïðîäâèæåíèå ïàêåòà. Êîãäà ïàêåò ïåðåñûëàåòñÿ ïî ñåòè, òîåãî ïðîäâèæåíèå îñóùåñòâëÿåòñÿ íà îñíîâå òàáëèöìàðøðóòèçàöèè.Çàäà÷à ìàðøðóòèçàöèèÊðèòåðèè îöåíêè êà÷åñòâà ìåòîäîâ ìàðøðóòèçàöèè ó÷èòûâàþòñëåäóþùèå ïîêàçàòåëè.Çàäà÷à ìàðøðóòèçàöèèÊðèòåðèè îöåíêè êà÷åñòâà ìåòîäîâ ìàðøðóòèçàöèè ó÷èòûâàþòñëåäóþùèå ïîêàçàòåëè.1. Êîððåêòíîñòü.2. Ýôôåêòèâíîñòü.3. Ñëîæíîñòü.4. Óñòîé÷èâîñòü.5. Àäàïòèâíîñòü.6.

Ñïðàâåäëèâîñòü.Çàäà÷à ìàðøðóòèçàöèèÊðèòåðèè îöåíêè êà÷åñòâà ìåòîäîâ ìàðøðóòèçàöèè ó÷èòûâàþòñëåäóþùèå ïîêàçàòåëè.1. Êîððåêòíîñòü. Àëãîðèòì äîëæåí äîñòàâëÿòü êàæäûé ïàêåò,ïîñòóïèâøèé â ñåòü, â òî÷íîñòè ïî íàçíà÷åíèþ.2. Ýôôåêòèâíîñòü.3. Ñëîæíîñòü.4. Óñòîé÷èâîñòü.5. Àäàïòèâíîñòü.6. Ñïðàâåäëèâîñòü.Çàäà÷à ìàðøðóòèçàöèèÊðèòåðèè îöåíêè êà÷åñòâà ìåòîäîâ ìàðøðóòèçàöèè ó÷èòûâàþòñëåäóþùèå ïîêàçàòåëè.1.

Êîððåêòíîñòü.2. Ýôôåêòèâíîñòü. Àëãîðèòì äîëæåí îòïðàâëÿòü ïàêåòû ïî¾íàèëó÷øèì¿ ïóòÿì; íàïðèìåð, îæèäàåòñÿ, ÷òîâûáðàííûå ïóòè ïðèâîäÿò ê íåáîëüøîé çàäåðæêå èîáåñïå÷èâàþò âûñîêóþ ïðîïóñêíóþ ñïîñîáíîñòü âñåé ñåòè.Àëãîðèòì íàçûâàåòñÿ îïòèìàëüíûì , åñëè îí ïîçâîëÿåòçàäåéñòâîâàòü ¾íàèëó÷øèå¿ ïóòè.3. Ñëîæíîñòü.4. Óñòîé÷èâîñòü.5. Àäàïòèâíîñòü.6. Ñïðàâåäëèâîñòü.Çàäà÷à ìàðøðóòèçàöèèÊðèòåðèè îöåíêè êà÷åñòâà ìåòîäîâ ìàðøðóòèçàöèè ó÷èòûâàþòñëåäóþùèå ïîêàçàòåëè.1. Êîððåêòíîñòü.2. Ýôôåêòèâíîñòü.3.

Ñëîæíîñòü. Àëãîðèòì âû÷èñëåíèÿ òàáëèö äîëæåíèñïîëüçîâàòü êàê ìîæíî ìåíüøå ñîîáùåíèé, ðàñõîäîâàòüêàê ìîæíî áîëåå ýêîíîìíî âðåìÿ è ïàìÿòü.4. Óñòîé÷èâîñòü.5. Àäàïòèâíîñòü.6. Ñïðàâåäëèâîñòü.Çàäà÷à ìàðøðóòèçàöèèÊðèòåðèè îöåíêè êà÷åñòâà ìåòîäîâ ìàðøðóòèçàöèè ó÷èòûâàþòñëåäóþùèå ïîêàçàòåëè.1. Êîððåêòíîñòü.2. Ýôôåêòèâíîñòü.3. Ñëîæíîñòü.4. Óñòîé÷èâîñòü.  ñëó÷àå èçìåíåíèÿ òîïîëîãèè (äîáàâëåíèèèëè óäàëåíèè êàíàëà èëè âåðøèíû) àëãîðèòì âíîñèòèçìåíåíèÿ â òàáëèöû ìàðøðóòèçàöèè, äëÿ òîãî ÷òîáûçàäà÷ó ìàðøðóòèçàöèè ìîæíî áûëî ðåøèòü âìîäèôèöèðîâàííîé ñåòè.5.

Àäàïòèâíîñòü.6. Ñïðàâåäëèâîñòü.Çàäà÷à ìàðøðóòèçàöèèÊðèòåðèè îöåíêè êà÷åñòâà ìåòîäîâ ìàðøðóòèçàöèè ó÷èòûâàþòñëåäóþùèå ïîêàçàòåëè.1. Êîððåêòíîñòü.2. Ýôôåêòèâíîñòü.3. Ñëîæíîñòü.4. Óñòîé÷èâîñòü.5. Àäàïòèâíîñòü. Äëÿ òîãî ÷òîáû âûðîâíÿòü çàãðóæåííîñòüêàíàëîâ è âåðøèí, àëãîðèòì ïðèñïîñàáëèâàåò ê ýòîìóòàáëèöû, èçáåãàÿ ïðîêëàäûâàòü ïóòè ÷åðåç òå êàíàëû èâåðøèíû, êîòîðûå ÷ðåçìåðíî çàãðóæåíû, è îòäàâàÿïðåäïî÷òåíèå òåì êàíàëàì è âåðøèíàì, íà êîòîðûå â ýòîâðåìÿ âîçëîæåíà íàèìåíüøàÿ íàãðóçêà.6.

Ñïðàâåäëèâîñòü.Çàäà÷à ìàðøðóòèçàöèèÊðèòåðèè îöåíêè êà÷åñòâà ìåòîäîâ ìàðøðóòèçàöèè ó÷èòûâàþòñëåäóþùèå ïîêàçàòåëè.1. Êîððåêòíîñòü.2. Ýôôåêòèâíîñòü.3. Ñëîæíîñòü.4. Óñòîé÷èâîñòü.5. Àäàïòèâíîñòü.6. Ñïðàâåäëèâîñòü. Àëãîðèòì äîëæåí îáñëóæèâàòü âñåõïîëüçîâàòåëåé â ðàâíîé ìåðå.Çàäà÷à ìàðøðóòèçàöèèÑåòü ïðåäñòàâëÿåòñÿ ãðàôîì, âåðøèíû êîòîðîãî ñîîòâåòñòâóþòâåðøèíàì ñåòè; ñîñåäíèå âåðøèíû ñîåäèíåíû ðåáðîì, åñëèìåæäó íèìè åñòü êàíàë ñâÿçè. Ñóùåñòâóåò íåñêîëüêî âàðèàíòîâïîíÿòèÿ ¾íàèëó÷øèé ïóòü¿.Çàäà÷à ìàðøðóòèçàöèèÑåòü ïðåäñòàâëÿåòñÿ ãðàôîì, âåðøèíû êîòîðîãî ñîîòâåòñòâóþòâåðøèíàì ñåòè; ñîñåäíèå âåðøèíû ñîåäèíåíû ðåáðîì, åñëèìåæäó íèìè åñòü êàíàë ñâÿçè.

Ñóùåñòâóåò íåñêîëüêî âàðèàíòîâïîíÿòèÿ ¾íàèëó÷øèé ïóòü¿.1. Ìèíèìàëüíîå êîëè÷åñòâî çâåíüåâ.2. Ìèíèìàëüíàÿ ñòîèìîñòü.3. Ìèíèìàëüíàÿ çàäåðæêà.Çàäà÷à ìàðøðóòèçàöèèÑåòü ïðåäñòàâëÿåòñÿ ãðàôîì, âåðøèíû êîòîðîãî ñîîòâåòñòâóþòâåðøèíàì ñåòè; ñîñåäíèå âåðøèíû ñîåäèíåíû ðåáðîì, åñëèìåæäó íèìè åñòü êàíàë ñâÿçè. Ñóùåñòâóåò íåñêîëüêî âàðèàíòîâïîíÿòèÿ ¾íàèëó÷øèé ïóòü¿.1. Ìèíèìàëüíîå êîëè÷åñòâî çâåíüåâ. Ñòîèìîñòüèñïîëüçîâàíèÿ ïóòè îïðåäåëÿåòñÿ êîëè÷åñòâîì çâåíüåâ(ïðîéäåííûõ êàíàëîâ èëè øàãîâ îò îäíîé âåðøèíû êäðóãîé) â ýòîì ïóòè. Àëãîðèòì ìàðøðóòèçàöèè ñìèíèìàëüíûì ÷èñëîì çâåíüåâ âûáèðàåò ïóòè, èìåþùèõíàèìåíüøåå âîçìîæíîå ÷èñëî çâåíüåâ.2.

Ìèíèìàëüíàÿ ñòîèìîñòü.3. Ìèíèìàëüíàÿ çàäåðæêà.Çàäà÷à ìàðøðóòèçàöèèÑåòü ïðåäñòàâëÿåòñÿ ãðàôîì, âåðøèíû êîòîðîãî ñîîòâåòñòâóþòâåðøèíàì ñåòè; ñîñåäíèå âåðøèíû ñîåäèíåíû ðåáðîì, åñëèìåæäó íèìè åñòü êàíàë ñâÿçè. Ñóùåñòâóåò íåñêîëüêî âàðèàíòîâïîíÿòèÿ ¾íàèëó÷øèé ïóòü¿.1. Ìèíèìàëüíîå êîëè÷åñòâî çâåíüåâ.2. Ìèíèìàëüíàÿ ñòîèìîñòü. Êàæäîìó êàíàëó ñâÿçèïðèäàåòñÿ íåèçìåííàÿ (îáû÷íî íåîòðèöàòåëüíàÿ)ñòîèìîñòü (èëè âåñ ), è ñòîèìîñòü ïóòè ïîëàãàåòñÿ ðàâíîéñóììàðíîìó âåñó âñåõ êàíàëîâ ïóòè. Àëãîðèòìêðàò÷àéøåãî ïóòè âûáèðàåò ïóòü íàèìåíüøåé ñòîèìîñòè.3. Ìèíèìàëüíàÿ çàäåðæêà.Çàäà÷à ìàðøðóòèçàöèèÑåòü ïðåäñòàâëÿåòñÿ ãðàôîì, âåðøèíû êîòîðîãî ñîîòâåòñòâóþòâåðøèíàì ñåòè; ñîñåäíèå âåðøèíû ñîåäèíåíû ðåáðîì, åñëèìåæäó íèìè åñòü êàíàë ñâÿçè.

Ñóùåñòâóåò íåñêîëüêî âàðèàíòîâïîíÿòèÿ ¾íàèëó÷øèé ïóòü¿.1. Ìèíèìàëüíîå êîëè÷åñòâî çâåíüåâ.2. Ìèíèìàëüíàÿ ñòîèìîñòü.3. Ìèíèìàëüíàÿ çàäåðæêà. Êàæäîìó êàíàëó ñâÿçè ïðèäàåòñÿäèíàìè÷åñêè èçìåíÿåìàÿ õàðàêòåðèñòèêà, çàâèñÿùàÿ îòòðàôèêà ÷åðåç ýòîò êàíàë. Àëãîðèòì ìèíèìàëüíîéçàäåðæêè ïîñòîÿííî ïåðåñìàòðèâàåò òàáëèöû òàê, ÷òîáûâñåãäà âûáèðàëèñü ïóòè ñ (ïî÷òè) ìèíèìàëüíîé îáùåéçàäåðæêîé.Ìàðøðóòèçàöèÿ íà îñíîâå óçëîâ-àäðåñàòîâÂûáîð ìàðøðóòà äëÿ ïðîäâèæåíèÿ ïàêåòà îáû÷íî ïðîâîäèòñÿòîëüêî ñ ó÷åòîì óçëà-àäðåñàòà ïàêåòà íåçàâèñèìî îò èñõîäíîãîîòïðàâèòåëÿ (èñòî÷íèêà) ïàêåòà.Ìàðøðóòèçàöèÿ íà îñíîâå óçëîâ-àäðåñàòîâÂûáîð ìàðøðóòà äëÿ ïðîäâèæåíèÿ ïàêåòà îáû÷íî ïðîâîäèòñÿòîëüêî ñ ó÷åòîì óçëà-àäðåñàòà ïàêåòà íåçàâèñèìî îò èñõîäíîãîîòïðàâèòåëÿ (èñòî÷íèêà) ïàêåòà.Îñíîâíûå äîïóùåíèÿ î ñâîéñòâàõ ìàðøðóòîâ.Ìàðøðóòèçàöèÿ íà îñíîâå óçëîâ-àäðåñàòîâÂûáîð ìàðøðóòà äëÿ ïðîäâèæåíèÿ ïàêåòà îáû÷íî ïðîâîäèòñÿòîëüêî ñ ó÷åòîì óçëà-àäðåñàòà ïàêåòà íåçàâèñèìî îò èñõîäíîãîîòïðàâèòåëÿ (èñòî÷íèêà) ïàêåòà.Îñíîâíûå äîïóùåíèÿ î ñâîéñòâàõ ìàðøðóòîâ.1.

Ñòîèìîñòü îòïðàâëåíèÿ ïàêåòà ïî ïóòèòîãî, èñïîëüçóþòñÿ ëè ðåáðà ïóòèPPíå çàâèñèò îòäëÿ ïðîäâèæåíèÿäðóãèõ ñîîáùåíèé. Ïîýòîìó ñòîèìîñòüC (P)ôóíêöèÿ, çàâèñÿùàÿ òîëüêî îò ñàìîãî ïóòè.ïóòèP ýòîÌàðøðóòèçàöèÿ íà îñíîâå óçëîâ-àäðåñàòîâÂûáîð ìàðøðóòà äëÿ ïðîäâèæåíèÿ ïàêåòà îáû÷íî ïðîâîäèòñÿòîëüêî ñ ó÷åòîì óçëà-àäðåñàòà ïàêåòà íåçàâèñèìî îò èñõîäíîãîîòïðàâèòåëÿ (èñòî÷íèêà) ïàêåòà.Îñíîâíûå äîïóùåíèÿ î ñâîéñòâàõ ìàðøðóòîâ.1. Ñòîèìîñòü îòïðàâëåíèÿ ïàêåòà ïî ïóòèòîãî, èñïîëüçóþòñÿ ëè ðåáðà ïóòèPPíå çàâèñèò îòäëÿ ïðîäâèæåíèÿäðóãèõ ñîîáùåíèé. Ïîýòîìó ñòîèìîñòüC (P)ïóòèP ýòîôóíêöèÿ, çàâèñÿùàÿ òîëüêî îò ñàìîãî ïóòè.2.

Ïðè ïîñëåäîâàòåëüíîì ñîåäèíåíèè äâóõ ïóòåé îáðàçóåòñÿíîâûé ïóòü, ñòîèìîñòü êîòîðîãî ðàâíà ñóììå ñòîèìîñòåéäâóõ èñõîäíûõ ïóòåé, ò.å.C (hu0 , u1 , . . . , uk i) = C (hu0 , . . . , ui i) + C (hui , . . . , uk i).hu0 i ðàâíà 0.Còîèìîñòü ïóñòîãî ïóòèÌàðøðóòèçàöèÿ íà îñíîâå óçëîâ-àäðåñàòîâÂûáîð ìàðøðóòà äëÿ ïðîäâèæåíèÿ ïàêåòà îáû÷íî ïðîâîäèòñÿòîëüêî ñ ó÷åòîì óçëà-àäðåñàòà ïàêåòà íåçàâèñèìî îò èñõîäíîãîîòïðàâèòåëÿ (èñòî÷íèêà) ïàêåòà.Îñíîâíûå äîïóùåíèÿ î ñâîéñòâàõ ìàðøðóòîâ.1.

Ñòîèìîñòü îòïðàâëåíèÿ ïàêåòà ïî ïóòèòîãî, èñïîëüçóþòñÿ ëè ðåáðà ïóòèPPíå çàâèñèò îòäëÿ ïðîäâèæåíèÿäðóãèõ ñîîáùåíèé. Ïîýòîìó ñòîèìîñòüC (P)ïóòèP ýòîôóíêöèÿ, çàâèñÿùàÿ òîëüêî îò ñàìîãî ïóòè.2. Ïðè ïîñëåäîâàòåëüíîì ñîåäèíåíèè äâóõ ïóòåé îáðàçóåòñÿíîâûé ïóòü, ñòîèìîñòü êîòîðîãî ðàâíà ñóììå ñòîèìîñòåéäâóõ èñõîäíûõ ïóòåé, ò.å.C (hu0 , u1 , . . . , uk i) = C (hu0 , . .

. , ui i) + C (hui , . . . , uk i).hu0 i ðàâíà 0.Còîèìîñòü ïóñòîãî ïóòè3.  ãðàôå íåò öèêëîâ îòðèöàòåëüíîé ñòîèìîñòè.Ìàðøðóòèçàöèÿ íà îñíîâå óçëîâ-àäðåñàòîâÂûáîð ìàðøðóòà äëÿ ïðîäâèæåíèÿ ïàêåòà îáû÷íî ïðîâîäèòñÿòîëüêî ñ ó÷åòîì óçëà-àäðåñàòà ïàêåòà íåçàâèñèìî îò èñõîäíîãîîòïðàâèòåëÿ (èñòî÷íèêà) ïàêåòà.Îñíîâíûå äîïóùåíèÿ î ñâîéñòâàõ ìàðøðóòîâ.P1. Ñòîèìîñòü îòïðàâëåíèÿ ïàêåòà ïî ïóòèòîãî, èñïîëüçóþòñÿ ëè ðåáðà ïóòèPíå çàâèñèò îòäëÿ ïðîäâèæåíèÿäðóãèõ ñîîáùåíèé. Ïîýòîìó ñòîèìîñòüC (P)ïóòèP ýòîôóíêöèÿ, çàâèñÿùàÿ òîëüêî îò ñàìîãî ïóòè.2.

Ïðè ïîñëåäîâàòåëüíîì ñîåäèíåíèè äâóõ ïóòåé îáðàçóåòñÿíîâûé ïóòü, ñòîèìîñòü êîòîðîãî ðàâíà ñóììå ñòîèìîñòåéäâóõ èñõîäíûõ ïóòåé, ò.å.C (hu0 , u1 , . . . , uk i) = C (hu0 , . . . , ui i) + C (hui , . . . , uk i).hu0 i ðàâíà 0.Còîèìîñòü ïóñòîãî ïóòè3.  ãðàôå íåò öèêëîâ îòðèöàòåëüíîé ñòîèìîñòè.Ïóòü èç âåðøèíûuâ âåðøèíóvíàçûâàåòñÿ îïòèìàëüíûì ,åñëè íåò ïóòè ìåíüøåé ñòîèìîñòè èçuâv.Ìàðøðóòèçàöèÿ íà îñíîâå óçëîâ-àäðåñàòîâËåììà 5.1.

(î ïðîñòûõ ïóòÿõ).Ïóñòüèçuâu è v âåðøèíû ãðàôà G . Åñëè â ãðàôå G åñòü ïóòü Pv , òî èìååòñÿ òàêæå è ïðîñòîé ïóòü èç u â v , êîòîðûéÿâëÿåòñÿ ïðè ýòîì îïòèìàëüíûì.Ìàðøðóòèçàöèÿ íà îñíîâå óçëîâ-àäðåñàòîâËåììà 5.1. (î ïðîñòûõ ïóòÿõ).Ïóñòüèçuâu è v âåðøèíû ãðàôà G . Åñëè â ãðàôå G åñòü ïóòü Pv , òî èìååòñÿ òàêæå è ïðîñòîé ïóòü èç u â v , êîòîðûéÿâëÿåòñÿ ïðè ýòîì îïòèìàëüíûì.Çàäà÷à.1. Âåðíî ëè, ÷òî êàæäûé îïòèìàëüíûé ïóòü îáÿçàòåëüíîäîëæåí áûòü ïðîñòûì ïóòåì?2. Íàñêîëüêî ñóùåñòâåííûì çäåñü ÿâëÿåòñÿ òðåáîâàíèåîòñóòñòâèÿ öèêëîâ îòðèöàòåëüíîé ñòîèìîñòè?Ìàðøðóòèçàöèÿ íà îñíîâå óçëîâ-àäðåñàòîâÒåîðåìà 5.1. (î äåðåâå îïòèìàëüíûõ ïóòåé).u ∈ V ñâÿçíîãî ãðàôà G ñóùåñòâóåòTu = (V , Eu ), Eu ⊆ E , â êîòîðîì äëÿ ëþáîéâåðøèíû v ∈ V , åäèíñòâåííûé ïóòü èç v â u â äåðåâå Tuÿâëÿåòñÿ îïòèìàëüíûì ïóòåì èç v â u â ãðàôå G .Äëÿ êàæäîé âåðøèíûòàêîå äåðåâîÌàðøðóòèçàöèÿ íà îñíîâå óçëîâ-àäðåñàòîâÒåîðåìà 5.1.