Лекция 5. Задача маршрутизации. Алгоритм Флойда-Уоршалла_ Туэга_ Мерлина-Сигалла_ Чанди-Мисры (1185655), страница 3
Текст из файла (страница 3)
. . , uk i ýòî ÷èñëî, ðàâíîåÐàññòîÿíèå ìåæäó âåðøèíàìèïóòè, ñîåäèíÿþùåãî âåðøèíûd(u, v ) = ∞Pk−1i=0ωui ui+1.u è v íàèìåíüøèé âåñ d(u, v )u è v (åñëè òàêèõ ïóòåé íåò, òî).Çàäà÷à ïîñòðîåíèÿ êðàò÷àéøèõ ïóòåé äëÿ âñåõ ïàð âåðøèíñîñòîèò â òîì, ÷òîáû âû÷èñëèòü ðàññòîÿíèåêàæäîé ïàðû âåðøèíuèv.d(u, v )äëÿÀëãîðèòì ÔëîéäàÓîðøàëëàÄëÿ âû÷èñëåíèÿ âñåõ ðàññòîÿíèé â àëãîðèòìåÔëîéäàÓîðøàëëà èñïîëüçóåòñÿ ïîíÿòèåS -ïóòåé, â êîòîðûõâñå ïðîìåæóòî÷íûå âåðøèíû ïðèíàäëåæàò ïîäìíîæåñòâóìíîæåñòâà âåðøèíVS.Îïðåäåëåíèå 5.1. (S -ðàññòîÿíèÿ)S íåêîòîðîå ïîäìíîæåñòâî ìíîæåñòâà âåðøèí V .hu0 , .
. . , uk i íàçûâàåòñÿ S -ïóòåì, åñëè ui ∈ S äëÿêàæäîãî i, 0 < i < k . S -ðàññòîÿíèåì ìåæäó âåðøèíàìè u è vS, êîòîðîå îáîçíà÷àåòñÿ d (u, v ) , íàçûâàåòñÿ íàèìåíüøèé âåñS -ïóòè ìåæäó u è v (åñëè òàêèõ ïóòåé íåò, òî d S (u, v ) = ∞ ).ÏóñòüÏóòüÀëãîðèòì ÔëîéäàÓîðøàëëàÄëÿ âû÷èñëåíèÿ âñåõ ðàññòîÿíèé â àëãîðèòìåÔëîéäàÓîðøàëëà èñïîëüçóåòñÿ ïîíÿòèåS -ïóòåé, â êîòîðûõâñå ïðîìåæóòî÷íûå âåðøèíû ïðèíàäëåæàò ïîäìíîæåñòâóìíîæåñòâà âåðøèíVS.Îïðåäåëåíèå 5.1. (S -ðàññòîÿíèÿ)S íåêîòîðîå ïîäìíîæåñòâî ìíîæåñòâà âåðøèí V .hu0 , . .
. , uk i íàçûâàåòñÿ S -ïóòåì, åñëè ui ∈ S äëÿêàæäîãî i, 0 < i < k . S -ðàññòîÿíèåì ìåæäó âåðøèíàìè u è vS, êîòîðîå îáîçíà÷àåòñÿ d (u, v ) , íàçûâàåòñÿ íàèìåíüøèé âåñS -ïóòè ìåæäó u è v (åñëè òàêèõ ïóòåé íåò, òî d S (u, v ) = ∞ ).ÏóñòüÏóòüÐàáîòà àëãîðèòìà íà÷èíàåòñÿ ñ ïîñòðîåíèÿ âñåõçàòåì ìíîæåñòâîSîáøèðíûõ ïîäìíîæåñòâðàññìîòðåíû âñåV∅-ïóòåé, à-ïóòåé íàðàùèâàåòñÿ äëÿ âñå áîëååS-ïóòè., äî òåõ ïîð ïîêà íå áóäóòÀëãîðèòì ÔëîéäàÓîðøàëëàÒåîðåìà 5.2. (îá S -ïóòÿõ)Äëÿ âñåõ âåðøèíd S (u, u) = 0u.
Åñëèè ïîäìíîæåñòâu 6= vñëåäóþùèì ïðàâèëàì., òîSSâûïîëíÿåòñÿ ðàâåíñòâî-ïóòè ïîä÷èíÿþòñÿÀëãîðèòì ÔëîéäàÓîðøàëëàÒåîðåìà 5.2. (îá S -ïóòÿõ)Äëÿ âñåõ âåðøèíd S (u, u) = 0u. Åñëèè ïîäìíîæåñòâu 6= v, òîSSâûïîëíÿåòñÿ ðàâåíñòâî-ïóòè ïîä÷èíÿþòñÿñëåäóþùèì ïðàâèëàì.1.∅-ïóòüèç âåðøèíûuâ âåðøèíóvuv ∈ E.òîëüêî òîì ñëó÷àå, êîãäàñóùåñòâóåò â òîì èÀëãîðèòì ÔëîéäàÓîðøàëëàÒåîðåìà 5.2.
(îá S -ïóòÿõ)Äëÿ âñåõ âåðøèíd S (u, u) = 0u. Åñëèè ïîäìíîæåñòâu 6= v, òîSSâûïîëíÿåòñÿ ðàâåíñòâî-ïóòè ïîä÷èíÿþòñÿñëåäóþùèì ïðàâèëàì.1.∅-ïóòüèç âåðøèíûuâ âåðøèíóvuv ∈ E.òîëüêî òîì ñëó÷àå, êîãäà2. Åñëèuv ∈ E, òîd ∅ (u, v ) = ωuvñóùåñòâóåò â òîì è; èíà÷åd ∅ (u, v ) = ∞.Àëãîðèòì ÔëîéäàÓîðøàëëàÒåîðåìà 5.2. (îá S -ïóòÿõ)Äëÿ âñåõ âåðøèíd S (u, u) = 0u. Åñëèè ïîäìíîæåñòâu 6= v, òîSSâûïîëíÿåòñÿ ðàâåíñòâî-ïóòè ïîä÷èíÿþòñÿñëåäóþùèì ïðàâèëàì.1.∅-ïóòüèç âåðøèíûuâ âåðøèíóvuv ∈ E.òîëüêî òîì ñëó÷àå, êîãäà2. Åñëèuv ∈ E03.
Åñëè Sëèáî, òîd ∅ (u, v ) = ωuvñóùåñòâóåò â òîì è; èíà÷åd ∅ (u, v ) = ∞0, òî ïðîñòîé S -ïóòü èç= S ∪ {w }S -ïóòü èç u â vuâ, ëèáî ñîåäèíåíèå äâóõSîäèí èç êîòîðûõ âåäåò èçuâwv, à äðóãîé èç. ýòî-ïóòåé,wâv.Àëãîðèòì ÔëîéäàÓîðøàëëàÒåîðåìà 5.2. (îá S -ïóòÿõ)Äëÿ âñåõ âåðøèíd S (u, u) = 0u. Åñëèè ïîäìíîæåñòâu 6= vS, òîSâûïîëíÿåòñÿ ðàâåíñòâî-ïóòè ïîä÷èíÿþòñÿñëåäóþùèì ïðàâèëàì.1.∅-ïóòüèç âåðøèíûuâ âåðøèíóvuv ∈ E.òîëüêî òîì ñëó÷àå, êîãäà2. Åñëèuv ∈ E03. Åñëè Sëèáî, òîd ∅ (u, v ) = ωuvñóùåñòâóåò â òîì è; èíà÷åd ∅ (u, v ) = ∞0, òî ïðîñòîé S -ïóòü èç= S ∪ {w }S -ïóòü èç u â vuâ, ëèáî ñîåäèíåíèå äâóõSîäèí èç êîòîðûõ âåäåò èç04. Åñëè S = S ∪ {w } , òî0d S (u, v ) = min ( d S (u, v ),uâwv.
ýòî-ïóòåé,, à äðóãîé èçd S (u, w ) + d S (w , v ) )w.âv.Àëãîðèòì ÔëîéäàÓîðøàëëàÒåîðåìà 5.2. (îá S -ïóòÿõ)Äëÿ âñåõ âåðøèíd S (u, u) = 0u. Åñëèè ïîäìíîæåñòâu 6= vS, òîSâûïîëíÿåòñÿ ðàâåíñòâî-ïóòè ïîä÷èíÿþòñÿñëåäóþùèì ïðàâèëàì.1.∅-ïóòüèç âåðøèíûuâ âåðøèíóvuv ∈ E.òîëüêî òîì ñëó÷àå, êîãäà2. Åñëèuv ∈ E, òî03. Åñëè Sëèáîd ∅ (u, v ) = ωuv; èíà÷åd ∅ (u, v ) = ∞0, òî ïðîñòîé S -ïóòü èç= S ∪ {w }S -ïóòü èç u â vuâ, ëèáî ñîåäèíåíèå äâóõSîäèí èç êîòîðûõ âåäåò èç04.
Åñëè S = S ∪ {w } , òî0d S (u, v ) = min ( d S (u, v ),5. Âåðøèíûñóùåñòâóåò â òîì èuèvuâwv. ýòî-ïóòåé,, à äðóãîé èçd S (u, w ) + d S (w , v ) )wâv..ñîåäèíåíû ïóòåì â òîì è òîëüêî òîìñëó÷àå, êîãäà ìåæäó âåðøèíàìèuèvñóùåñòâóåòV-ïóòü.Àëãîðèòì ÔëîéäàÓîðøàëëàÒåîðåìà 5.2. (îá S -ïóòÿõ)Äëÿ âñåõ âåðøèíd S (u, u) = 0u. Åñëèè ïîäìíîæåñòâu 6= vS, òîSâûïîëíÿåòñÿ ðàâåíñòâî-ïóòè ïîä÷èíÿþòñÿñëåäóþùèì ïðàâèëàì.1.∅-ïóòüèç âåðøèíûuâ âåðøèíóvuv ∈ E.òîëüêî òîì ñëó÷àå, êîãäà2.
Åñëèuv ∈ E, òîd ∅ (u, v ) = ωuv03. Åñëè Sëèáîâ, ëèáî ñîåäèíåíèå äâóõS04. Åñëè S = S ∪ {w } , òî0d S (u, v ) = min ( d S (u, v ),uèvuâwd V (u,v. ýòî-ïóòåé,, à äðóãîé èçd S (u, w ) + d S (w , v ) )wâv..ñîåäèíåíû ïóòåì â òîì è òîëüêî òîìñëó÷àå, êîãäà ìåæäó âåðøèíàìèd(u, v ) =d ∅ (u, v ) = ∞uîäèí èç êîòîðûõ âåäåò èç6.; èíà÷å0, òî ïðîñòîé S -ïóòü èç= S ∪ {w }S -ïóòü èç u â v5.
Âåðøèíûñóùåñòâóåò â òîì èv),uèvñóùåñòâóåòV-ïóòü.Àëãîðèòì ÔëîéäàÓîðøàëëàÄîêàçàòåëüñòâîÏðàâèëà (1)(3) è (5)(6) ñàìîñòîÿòåëüíî .Àëãîðèòì ÔëîéäàÓîðøàëëàÄîêàçàòåëüñòâîÏðàâèëà (1)(3) è (5)(6) ñàìîñòîÿòåëüíî .Ïðàâèëî (4).Ïðèìåíÿÿ ëåììó 5.1. (î ïðîñòûõ ïóòÿõ), ìîæíîS 0 -ïóòü èç ud (u, v ) èç u â v .ïîêàçàòü, ÷òî â òîì ñëó÷àå, åñëè â ãðàôå åñòü, ñóùåñòâóåò èïðîñòîéS 0 -ïóòü äëèíûS0Ñîãëàñíî ïðàâèëó (3) îòñþäà ñëåäóåò ðàâåíñòâî0d S (u, v ) = min ( d S (u, v ), d S (u, w ) + d S (w , v ) ).âvÀëãîðèòì ÔëîéäàÓîðøàëëàbegin(*Âíà÷àëåS := ∅Sðàâíî∅,à âDçàäàíû∅-ðàññòîÿíèÿ*);forall u , v doif u = v then D[u, v ] := 0else if uv ∈ E then D[u, v ] := ωuv else D[u, v ] := ∞(* Äîáàâèòü êS;îïîðíóþ âåðøèíó *)while S 6= V do∀u, v : D[u, v ] = d S (u, v ) *)begin pick w from V \ S ;Ãëîáàëüíàÿ îáðàáîòêà îïîðíîé âåðøèíû w *)forall u ∈ V doËîêàëüíàÿ îáðàáîòêó îïîðíîé âåðøèíû w äëÿ u *)forall v ∈ V doD[u, v ] := min ( D[u, v ], D[u, w ] + D[w , v ] )S := S ∪ {w }end (* ∀u, v : D[u, v ] = d(u, v ) *)(* Èíâàðèàíò öèêëà:(*(*end;Àëãîðèòì ÔëîéäàÓîðøàëëàÒåîðåìà 5.3.
(îá àëãîðèòì ÔëîéäàÓîðøàëëà)Àëãîðèòì ÔëîéäàÓîðøàëëà âû÷èñëÿåò ðàññòîÿíèå ìåæäóâñåìè ïàðàìè âåðøèí çàΘ(N 3 )øàãîâ.Àëãîðèòì ÔëîéäàÓîðøàëëàÒåîðåìà 5.3. (îá àëãîðèòì ÔëîéäàÓîðøàëëà)Àëãîðèòì ÔëîéäàÓîðøàëëà âû÷èñëÿåò ðàññòîÿíèå ìåæäóâñåìè ïàðàìè âåðøèí çàΘ(N 3 )øàãîâ.Äîêàçàòåëüñòâî.D[u, v ] = 0 , åñëè u = v ,uv ∈ E , è D[u, v ] = ∞ â îñòàëüíûõñëó÷àÿõ. Ïðè ýòîì S = ∅ .
Ñîãëàñíî ïðàâèëàì (1) è (2)SÒåîðåìû 5.2. î S -ïóòÿõ, ∀u, v : D[u, v ] = d (u, v ) . Åñëèäîáàâëÿåòñÿ âåðøèíà w , òî ñîãëàñíî ïðàâèëàì (3) è (4)îïåðàòîð ïðèñâàèâàíèÿ, óòî÷íÿþùèé çíà÷åíèå D[u, v ] , íà÷àëå ðàáîòû àëãîðèòìàD[u, v ] = ωuv, åñëèêSîáåñïå÷èâàåò ñîõðàíåíèå âûïîëíèìîñòè èíâàðèàíòà öèêëà∀u, v : D[u, v ] = d S (u, v ) . Ïðîãðàììà çàâåðøàåò âûïîëíåíèå,êîãäà S = V . Ïðèíèìàÿ âî âíèìàíèå ïðàâèëà (5) è (6), àòàêæå èíâàðèàíò öèêëà, çàêëþ÷àåì, ÷òî S -ðàññòîÿíèÿ ìåæäóâñåìè âåðøèíàìè ðàâíû ðàññòîÿíèÿì.Îñíîâíîé öèêë âûïîëíÿåòñÿ2âûïîëíÿåòñÿ N îïåðàöèé.Nðàç, è â êàæäîé åãî èòåðàöèèÀëãîðèòì Òóýãà ïîñòðîåíèÿ êðàò÷àéøèõ ïóòåéÎñíîâíûå äîïóùåíèÿ.A1.
Êàæäûé öèêë â ñåòè èìååò ïîëîæèòåëüíûé âåñ.Àëãîðèòì Òóýãà ïîñòðîåíèÿ êðàò÷àéøèõ ïóòåéÎñíîâíûå äîïóùåíèÿ.A1. Êàæäûé öèêë â ñåòè èìååò ïîëîæèòåëüíûé âåñ.A2. Êàæäûé ïðîöåññ ñåòè ðàñïîëàãàåò èíôîðìàöèåé îáîòëè÷èòåëüíûõ ïðèçíàêàõ âñåõ óçëîâ ñèñòåìû (ìíîæåñòâàâåðøèíV).Àëãîðèòì Òóýãà ïîñòðîåíèÿ êðàò÷àéøèõ ïóòåéÎñíîâíûå äîïóùåíèÿ.A1. Êàæäûé öèêë â ñåòè èìååò ïîëîæèòåëüíûé âåñ.A2. Êàæäûé ïðîöåññ ñåòè ðàñïîëàãàåò èíôîðìàöèåé îáîòëè÷èòåëüíûõ ïðèçíàêàõ âñåõ óçëîâ ñèñòåìû (ìíîæåñòâàâåðøèíV).A3.
Êàæäûé ïðîöåññ ðàñïîëàãàåò èíôîðìàöèåé î òîì, êàêèåóçëû ÿâëÿþòñÿ åãî ñîñåäÿìè (äëÿ êàæäîé âåðøèíûñâåäåíèÿ ñîäåðæàòñÿ â ìàññèâåneighuuýòè) è êàêîé âåñ èìåþòêàíàëû, ñîåäèíÿþùèå ïðîöåññ ñ åãî ñîñåäÿìè.Àëãîðèòì Òóýãà ïîñòðîåíèÿ êðàò÷àéøèõ ïóòåéÎñíîâíûå äîïóùåíèÿ.A1. Êàæäûé öèêë â ñåòè èìååò ïîëîæèòåëüíûé âåñ.A2. Êàæäûé ïðîöåññ ñåòè ðàñïîëàãàåò èíôîðìàöèåé îáîòëè÷èòåëüíûõ ïðèçíàêàõ âñåõ óçëîâ ñèñòåìû (ìíîæåñòâàâåðøèíV).A3.
Êàæäûé ïðîöåññ ðàñïîëàãàåò èíôîðìàöèåé î òîì, êàêèåóçëû ÿâëÿþòñÿ åãî ñîñåäÿìè (äëÿ êàæäîé âåðøèíûñâåäåíèÿ ñîäåðæàòñÿ â ìàññèâåneighuuýòè) è êàêîé âåñ èìåþòêàíàëû, ñîåäèíÿþùèå ïðîöåññ ñ åãî ñîñåäÿìè.Íàì áóäåò ïðîùå ðàçîáðàòüñÿ ñ êîððåêòíîñòüþ àëãîðèòìàÒóýãà, åñëè âíà÷àëå ìû ðàññìîòðèì åãî óïðîùåííûé âàðèàíò.Àëãîðèòì Òóýãà (óïðîùåííûé âàðèàíò)I Ïåðåìåííûå è îïåðàöèè àëãîðèòìà Ôëîéäà-Óîðøàëëàðàçíîñÿòñÿ ïî ðàçíûì óçëàì ñåòè. Ïåðåìåííàÿîòäàåòñÿ ïðîöåññóçàïèñûâàòüuuD[u, v ]; äëÿ óäîáñòâà îáîçíà÷åíèÿ ìû áóäåìíà ìåñòå èíäåêñà ñëåäóþùèì îáðàçîìDu [v ].Àëãîðèòì Òóýãà (óïðîùåííûé âàðèàíò)I Ïåðåìåííûå è îïåðàöèè àëãîðèòìà Ôëîéäà-Óîðøàëëàðàçíîñÿòñÿ ïî ðàçíûì óçëàì ñåòè.
Ïåðåìåííàÿîòäàåòñÿ ïðîöåññóçàïèñûâàòüuuD[u, v ]; äëÿ óäîáñòâà îáîçíà÷åíèÿ ìû áóäåìíà ìåñòå èíäåêñà ñëåäóþùèì îáðàçîìDu [v ].I Îïåðàöèè, êîòîðûå ïðèñâàèâàþò çíà÷åíèÿ ïåðåìåííîéDu [v ]äîëæíû âûïîëíÿòüñÿ â óçëåu, è êîãäà çíà÷åíèåíåêîòîðîé ïåðåìåííîé, îòíîñÿùåéñÿ ê óçëów, íåîáõîäèìîäëÿ ýòîé îïåðàöèè, ýòî çíà÷åíèå äîëæíî áûòü ïîñëàíîïðîöåññóu.Àëãîðèòì Òóýãà (óïðîùåííûé âàðèàíò)I Ïåðåìåííûå è îïåðàöèè àëãîðèòìà Ôëîéäà-Óîðøàëëàðàçíîñÿòñÿ ïî ðàçíûì óçëàì ñåòè.
Ïåðåìåííàÿîòäàåòñÿ ïðîöåññóçàïèñûâàòüuuD[u, v ]; äëÿ óäîáñòâà îáîçíà÷åíèÿ ìû áóäåìíà ìåñòå èíäåêñà ñëåäóþùèì îáðàçîìDu [v ].I Îïåðàöèè, êîòîðûå ïðèñâàèâàþò çíà÷åíèÿ ïåðåìåííîéDu [v ]äîëæíû âûïîëíÿòüñÿ â óçëåu, è êîãäà çíà÷åíèåíåêîòîðîé ïåðåìåííîé, îòíîñÿùåéñÿ ê óçëów, íåîáõîäèìîäëÿ ýòîé îïåðàöèè, ýòî çíà÷åíèå äîëæíî áûòü ïîñëàíîïðîöåññóu.I  àëãîðèòìå Ôëîéäà-Óîðøàëëà âñå âåðøèíû äîëæíûèñïîëüçîâàòü èíôîðìàöèþ îò îïîðíîé âåðøèíû, êîòîðàÿîòïðàâëÿåò ýòó èíôîðìàöèþ îäíîâðåìåííî âñåì âåðøèíàìïîñðåäñòâîì ¾øèðîêîâåùàòåëüíîé¿ ðàññûëêè .Àëãîðèòì Òóýãà (óïðîùåííûé âàðèàíò)I Ïåðåìåííûå è îïåðàöèè àëãîðèòìà Ôëîéäà-Óîðøàëëàðàçíîñÿòñÿ ïî ðàçíûì óçëàì ñåòè. Ïåðåìåííàÿîòäàåòñÿ ïðîöåññóçàïèñûâàòüuuD[u, v ]; äëÿ óäîáñòâà îáîçíà÷åíèÿ ìû áóäåìíà ìåñòå èíäåêñà ñëåäóþùèì îáðàçîìDu [v ].I Îïåðàöèè, êîòîðûå ïðèñâàèâàþò çíà÷åíèÿ ïåðåìåííîéDu [v ]äîëæíû âûïîëíÿòüñÿ â óçëåu, è êîãäà çíà÷åíèåíåêîòîðîé ïåðåìåííîé, îòíîñÿùåéñÿ ê óçëów, íåîáõîäèìîäëÿ ýòîé îïåðàöèè, ýòî çíà÷åíèå äîëæíî áûòü ïîñëàíîïðîöåññóu.I  àëãîðèòìå Ôëîéäà-Óîðøàëëà âñå âåðøèíû äîëæíûèñïîëüçîâàòü èíôîðìàöèþ îò îïîðíîé âåðøèíû, êîòîðàÿîòïðàâëÿåò ýòó èíôîðìàöèþ îäíîâðåìåííî âñåì âåðøèíàìïîñðåäñòâîì ¾øèðîêîâåùàòåëüíîé¿ ðàññûëêè .I Íóæíî ââåñòè ñïåöèàëüíóþ îïåðàöèþ, äëÿ òîãî ÷òîáû íåòîëüêî âû÷èñëÿòü äëèíû êðàò÷àéøèõS-ïóòåé, íî òàêæå èïåðâûé êàíàë â êàæäîì òàêîì ïóòè (äëÿ ýòîãî ìû áóäåìèñïîëüçîâàòü ïåðåìåííûåNbu [v ]).Àëãîðèòì Òóýãà (óïðîùåííûé âàðèàíò)Ëåììà 5.3.
(îá îòñóòñòâèè öèêëîâ)Ïóñòü çàäàíû ìíîæåñòâî âåðøèíSè âåðøèíàw.Ïðåäïîëîæèì òàêæå, ÷òî1. äëÿ âñåõ âåðøèíS2. åñëè d (u,Nbu [w ]uâåðíî ðàâåíñòâîw) < ∞èu 6= wDu [w ] = d S (u, w ), òî çíà÷åíèåì ïåðåìåííîéÿâëÿåòñÿ èìÿ ñîñåäà âåðøèíû-ïóòè, âåäóùåì ê âåðøèíåÒîãäà îðèåíòèðîâàííûé ãðàôVw = {u : Du [w ] < ∞}èw,uíà êðàò÷àéøåìS.Tw = (Vw , Ew ), ãäåEw = {ux : u 6= w ∧ Nbu [w ] = x},ÿâëÿåòñÿ äåðåâîì, â êîðíå êîòîðîãî ðàñïîëîæåíà âåðøèíàw.Àëãîðèòì Òóýãà (óïðîùåííûé âàðèàíò)Äîêàçàòåëüñòâî.u 6= w âûïîëíÿåòñÿNbu [w ] 6= udef è DNbu [w ] [w ] < ∞Çíà÷èò äëÿ êàæäîé âåðøèíû u ∈ Vw , u 6= w , ñóùåñòâóåòâåðøèíà x ∈ Vw , äëÿ êîòîðîé âåðíî ðàâåíñòâî Nbu [w ] = x .Çàìåòèì, ÷òî åñëè äëÿ âåðøèíûíåðàâåíñòâîDu [w ] < ∞, òî.Àëãîðèòì Òóýãà (óïðîùåííûé âàðèàíò)Äîêàçàòåëüñòâî.u 6= w âûïîëíÿåòñÿNbu [w ] 6= udef è DNbu [w ] [w ] < ∞ .Çíà÷èò äëÿ êàæäîé âåðøèíû u ∈ Vw , u 6= w , ñóùåñòâóåòâåðøèíà x ∈ Vw , äëÿ êîòîðîé âåðíî ðàâåíñòâî Nbu [w ] = x .Äëÿ êàæäîé âåðøèíû u ∈ Vw , u 6= w , â ìíîæåñòâå Ew åñòüîäíî ðåáðî, è ïîýòîìó ÷èñëî âåðøèí â Tw áîëüøå ÷èñëà ðåáåðíà 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
