Диссертация (1149954), страница 7
Текст из файла (страница 7)
ÏóñòüF =Rè ñåòü ñ íåïðåðûâíûìè êóñî÷íî-ëèíåéíûìè óñèëåíèÿìè â äóãàõ. Ýòîïîäñëó÷àé ñëó÷àÿ 2, êîòîðûé äëÿ âåùåñòâåííûõ ïîòîêîâ ìîæíî ðåøèòü áîëåå ýåêòèâíûìè ìåòîäàìè, ÷åì îáùèå ìåòîäû êóñî÷íî-ëèíåéíîãî ïðîãðàììèðîâàíèÿ. Áîëååïîäðîáíî îí ðàññìîòðåí â ñëåäóþùåì ðàçäåëå.1.2.3Ñåòè ñ íåëèíåéíûìè óñèëåíèÿìè â äóãàõ äàííîì ðàçäåëå ðàññìàòðèâàþòñÿ çàäà÷è íàõîæäåíèÿ ìàêñèìàëüíîãî ïîòîêà è ïîòîêà ìèíèìàëüíîé ñòîèìîñòè â ñåòè ñ ÍÊË-óñèëåíèÿìè â äóãàõ [48℄.
Ýòè çàäà÷è îáîáùàåò àíàëîãè÷íûå çàäà÷è äëÿ ñåòè ñ ëèíåéíûìè óñèëåíèÿìè, êîòîðûå, â ñâîþ î÷åðåäü, îáîáùàþò êëàññè÷åñêèå çàäà÷è î ïîòîêàõ â ñåòÿõ. Äîêàçàíà òåîðåìà î êîìïîçèöèè äóã, ïîçâîëÿþùàÿ ñâåñòèóíêöèþ óñèëåíèÿ â äóãå ê íàáîðó áîëåå ïðîñòûõ óíêöèé äëÿ ïàðàëëåëüíûõ äóã.  ÷àñòíîñòè, âîãíóòûå êóñî÷íî-ëèíåéíûå óñèëåíèÿ ñâîäÿòñÿ ê íàáîðó ëèíåéíûõ óñèëåíèé â ïàðàëëåëüíûõ äóãàõ. Òàêèì îáðàçîì, çàäà÷à íàõîæäåíèÿ îïòèìàëüíîãî ïîòîêà â ñåòè ñ âîãíóòûìèêóñî÷íî-ëèíåéíûìè óñèëåíèÿìè ñâîäèòñÿ ê çàäà÷å íàõîæäåíèÿ îïòèìàëüíîãî ïîòîêà â ñåòè ñ ëèíåéíûìè óñèëåíèÿìè, äëÿ êîòîðîé åñòü ýåêòèâíûå àëãîðèòìû ðåøåíèÿ. Ïîñòðîåíïîëóïåðåáîðíûé àëãîðèòì íàõîæäåíèÿ îïòèìàëüíîãî ïîòîêà â ñåòè ñ ÍÊË-óñèëåíèÿìè.Ýòó çàäà÷ó ëó÷øå ðàññìàòðèâàòü äëÿ ìóëüòèãðàîâ, ïîñêîëüêó â íåé âàæíû ïàðàëëåëüíûå äóãè.
Ñîðìóëèðóåì åå áîëåå ñòðîãî:Îïðåäåëåíèå 12. Êîíå÷íàÿ ñåòü ñ íåëèíåéíûìè óñèëåíèÿìè è íåëèíåéíîé ñòîèìîñòüþ ýòî êîíå÷íûé îðèåíòèðîâàííûé ìóëüòèãðàâûäåëåííàÿ âåðøèíàv : L → R+ ,íàÿ ñïîñîáíîñòü c : M → R+ ,àðãóìåíòàè äëÿ êàæäîé äóãè íåîòðèöàòåëüíàÿpm : R+ → R+ñëåäóþùèì óñëîâèÿì:f (m) ∈ [0; c(m)]âåðõíÿÿ ïðîïóñê-íåîòðèöàòåëüíàÿ ÍÊË-óíêöèÿ íåîòðèöàòåëüíîãî àðãóìåíòàóíêöèÿ óñèëåíèÿ,Îïðåäåëåíèå 13. Ïîòîê1.äëÿ êîòîðîãî çàäàíà îäíàs′ ∈ L, íàçûâàåìàÿ ñòîêîì, à äëÿ êàæäîé âåðøèíû, êðîìå ñòîêà, çàäàíäîïóñòèìûé äåèöèòg m : R+ → R+N = (L, M, s, e),è íåîòðèöàòåëüíàÿ ÍÊË-óíêöèÿ íåîòðèöàòåëüíîãîóíêöèÿ ñòîèìîñòè.â ñåòèN ýòî óíêöèÿ íà äóãàõf : M → R,óäîâëåòâîðÿþùàÿ292.V (x) =Pe(m)=x(çíà÷åíèåV (x)Ïñåâäîïîòîêíåðàâåíñòâógm (f (m)) −Ps(m)=xáóäåì íàçûâàòüf (m) ∈ [0; v(x)]èçëèøêîìïîòîêàfäëÿ âñåõ âåðøèí, êðîìå ñòîêàâ âåðøèíås′x).îïðåäåëÿåòñÿ àíàëîãè÷íî, òîëüêî èçëèøåê äëÿ ïñåâäîïîòîêà óäîâëåòâîðÿåòV (x) ≤ v(x).Òàê æå, êàê è äëÿ ñåòåé ñ ëèíåéíûìè óñèëåíèÿìè [34℄, ìû ìîæåì ðàññìàòðèâàòü êàêçàäà÷ó ìàêñèìèçàöèè (ïñåâäî)ïîòîêàmaxf (p · f ).maxf (−Vf (s′ )),òàê è çàäà÷ó ìèíèìèçàöèè ñòîèìîñòèÇàìåòèì, ÷òî äëÿ íåîòðèöàòåëüíûõ (ïñåâäî)ïîòîêîâ, âîçðàñòàþùèõ óñèëåíèé èñòîèìîñòåé çàäà÷à ìèíèìèçàöèè ñòîèìîñòè ðåøàåòñÿ òðèâèàëüíî: åå ðåøåíèåì áóäåò íóëåâîéïîòîê.
Ïîýòîìó ðàññìîòðèì ñëåäóþùèå çàäà÷è:1. Ìàêñèìèçàöèÿ íåêîòîðîé ëèíåéíîé êîìáèíàöèè çíà÷åíèÿ è ñòîèìîñòè (ñ ïðîòèâîïîëîæíûì çíàêîì). Ýòî ýêâèâàëåíòíî ìàêñèìèçàöèè ðàçíîñòè−Vf (s′ ) − p · f(ñ ñîîòâåò-ñòâóþùèì îáðàçîì ìàñøòàáèðîâàííûìè ñòîèìîñòÿìè).2. Ìèíèìèçàöèÿ ñòîèìîñòèp·fïðè îãðàíè÷åíèè íà âåëè÷èíó ïîòîêàäîáàâèòü äóãó, èäóùóþ îò ñòîêà, ñ ïðîïóñêíîé ñïîñîáíîñòüþðàçíîñòüa(−Vf (s′ )) − p · f ,òî ïðèa → +∞ ïîëó÷èòñÿV−Vf (s′ ) ≥ V .Åñëèè ìàêñèìèçèðîâàòüðåøåíèå èñõîäíîé çàäà÷è. Òàêèìîáðàçîì, âòîðàÿ çàäà÷à ñâåäåíà ê ïåðâîé ñ ëåêñèêîãðàè÷åñêîé ìàêñèìèçàöèåé (îáùàÿçàäà÷à ëåêñèêîãðàè÷åñêîé ìàêñèìèçàöèè ïîòîêà ðàññìîòðåíà â ñëåäóþùåé ãëàâå).3.
Ìàêñèìèçàöèÿ âåëè÷èíû ïîòîêà−Vf (s′ ) ïðè îãðàíè÷åíèè íà ñòîèìîñòü p·f ≤ P . Ìèíè-ìàëüíàÿ ñòîèìîñòü åñòü âîçðàñòàþùàÿ óíêöèÿ îò âåëè÷èíû ïîòîêà. Ýòî çíà÷èò, ÷òîäàííóþ çàäà÷ó ìîæíî ðåøèòü ìåòîäîì äåëåíèÿ ïîïîëàì, ðàññìàòðèâàÿ ðàçíûå îãðàíè÷åíèÿ íà âåëè÷èíó ïîòîêà è íà êàæäîì øàãå ðåøàÿ âòîðóþ çàäà÷ó. Òàêèì îáðàçîì,òðåòüÿ çàäà÷à ñâåäåíà êî âòîðîé.Íåñëîæíî âèäåòü, ÷òî ïåðâàÿ çàäà÷à ÷àñòíûé ñëó÷àé îáùåé çàäà÷è ìèíèìèçàöèè ñòîèìîñòè ïîòîêà, ðàññìîòðåííîé â ïðåäûäóùåì ðàçäåëå. Ïðè ýòîì êàæäàÿ âåðøèíà ñóììàòîðóñèëèòåëü ñ íåëèíåéíûìè óñèëåíèÿìè â äóãàõ íà âõîäå è ðàñïðåäåëèòåëü íà âûõîäå.
 äàëüíåéøåì áóäåì ðàññìàòðèâàòü âòîðóþ çàäà÷ó ò.å. ìèíèìèçàöèþ ñòîèìîñòè ïîòîêà ïðè èêñèðîâàííîé åãî âåëè÷èíå.Çàäà÷è äëÿ ñåòè ñ ëèíåéíûìè óñèëåíèÿìè ÿâëÿþòñÿ ÷àñòíûìè ñëó÷àÿìè ýòèõ çàäà÷, êîãäàgm (z) = gm z(óñèëåíèå ëèíåéíàÿ óíêöèÿ). Äëÿ ñåòåé ñ ëèíåéíûìè óñèëåíèÿìè ñó-ùåñòâóþò ïðèáëèæåííûå ïîëèíîìèàëüíûå àëãîðèòìû íàõîæäåíèÿ îïòèìàëüíîãî ïîòîêà íàïðèìåð, àëãîðèòì àäçèêà èëè àëãîðèòì Òàðäîñ-Âåéíà [86℄.
Ñëîæíîñòü àëãîðèòìà ÒàðäîñÂåéíà äëÿ íàõîæäåíèÿ ìàêñèìàëüíîãî ïîòîêà O((m2 + mn log log ε−1 ) log ε−1 ),äëÿ íàõîæ-30èñ. 1.2: ðà ñ íåðàçëîæèìûì ïîòîêîì11äåíèÿ ïîòîêà ìèíèìàëüíîé ñòîèìîñòè m êîëè÷åñòâî äóã,εO(m2 n2 log ε−1 ),ãäån êîëè÷åñòâî âåðøèí â ñåòè, ïîãðåøíîñòü.ëàâíîå îòëè÷èå ñåòåé ñ íåëèíåéíûìè óñèëåíèÿìè îò ñåòåé ñ ëèíåéíûìè óñèëåíèÿìè îòñóòñòâèå âîçìîæíîñòè îáðàùåíèÿ äóã (âïðî÷åì, âîçìîæíîñòü îáðàùåíèÿ ñîõðàíÿåòñÿ, åñëè óñèëåíèÿ ñòðîãî ìîíîòîííû). Ïîýòîìó â íåëèíåéíîì ñëó÷àå ðàññìàòðèâàåòñÿ ïîñòàíîâêàçàäà÷è òîëüêî íà ÿçûêå îðèåíòèðîâàííûõ ñåòåé. Åñëè ëèíåéíîå óñèëåíèå ýòî âñåãäà âîçðàñòàþùàÿ óíêöèÿ, òî íåëèíåéíîå ìîæåò íà íåêîòîðûõ ó÷àñòêàõ âîçðàñòàòü, íà íåêîòîðûõ óáûâàòü.
 êîíöå ðàçäåëà ïîêàçàíî, ÷òî ñâîéñòâà âîçðàñòàíèÿ è óáûâàíèÿ òåñíî ñâÿçàíûñ ïîòîêàìè è ïñåâäîïîòîêàìè, à äî ýòîãî ðàññìàòðèâàåòñÿ òîëüêî ñàìûé ïðîñòîé ñëó÷àé:âîçðàñòàþùèå (ìîæåò áûòü, íåñòðîãî) óñèëåíèÿ è ïñåâäîïîòîêè. íåëèíåéíîì ñëó÷àå íå âûïîëíÿåòñÿ òåîðåìà îíäðàíà-Ìàéíàêñà [86℄ î ðàçëîæåíèè êàæäîãî ïñåâäîïîòîêà íà ýëåìåíòàðíûå ñëàãàåìûå ïñåâäîïîòîêè, èäóùèå ïî ïóòÿì, öèêëàì èïåòëÿì.Ïðèìåð 3.àññìîòðèì ãðà, èçîáðàæåííûé íà ðèñóíêå 1.2.Çäåñü öèðû íàä äóãàìè îçíà÷àþò ïðîïóñêíûå ñïîñîáíîñòè, óñèëåíèÿ â ïðÿìûõ äóãàõîòñóòñòâóþò, à óñèëåíèå â ïåòëå ðàâíîgx =1, 5x,x≤11, 5 + εx, x ≥ 1εãäå äîñòàòî÷íî ìàëîå ïîëîæèòåëüíîå ÷èñëî. Çàìåòèì, ÷òî, åñëèùèé ÷åðåç ïåòëþ, òî ïðèïðèx << 1.5x >> 1.5 ïîãëîùàþùèé.öèêë ãåíåðèðóþùèé, ïðèx ïîòîê, ïðîòåêàþ-x ≈ 1.5àññìîòðèì òåïåðü ïîòîê, ðàâíûé1 íåéòðàëüíûé, àâ ïðÿìûõ äóãàõ è äîñòà-òî÷íî áîëüøîìó ÷èñëó â ïåòëå.
Ïðåäïîëîæèì, ÷òî åãî ìîæíî ðàçëîæèòü íà ýëåìåíòàðíûåñëàãàåìûå. Äàæå åñëè âû÷åñòü èç ïåòëè íåéòðàëüíûé öèêë, â íåé âñå ðàâíî îñòàíåòñÿ ïîòîê,êîòîðûé ìîæíî áóäåò óñòðàíèòü, òîëüêî âû÷èòàÿ ïîòîêè, ïðîõîäÿùèå ÷åðåç äóãè è ïîãëîùåííûå â ïåòëå. Íî ïîòîê, ïðîõîäÿùèé ÷åðåç äóãó, íå áîëüøå 1, à ïðè ýòîì öèêë â ïåòëå ãåíåðèðóþùèé, à çíà÷èò, ïîòîê íå ìîæåò áûòü ïîãëîùåí.Òàêèì îáðàçîì, íåëèíåéíóþ çàäà÷ó íåëüçÿ ðåøàòü, êàê ëèíåéíóþ, ïîñëåäîâàòåëüíûìäîáàâëåíèåì ïîòîêîâ ÷åðåç ýëåìåíòàðíûå ïóòè. Äëÿ ðåøåíèÿ íåëèíåéíîé çàäà÷è â äàííîì31ðàçäåëå ìû ïðåäëîæèì äðóãèå ìåòîäû.Âû÷èòàíèå ïîòîêà èç ñåòè ñ íåëèíåéíûìè óñèëåíèÿìè ñåòè ñ íåëèíåéíûìè âîçðàñòàþùèìè óñèëåíèÿìè, êàê è â ñåòè ñ ëèíåéíûìè óñèëåíèÿìè,ìîæíî ââåñòè îïåðàöèþ âû÷èòàíèÿ ïîòîêà [86℄.
Îäíàêî, ïîñêîëüêó ìû ðàññìàòðèâàåì òîëüêîîðèåíòèðîâàííûå ñåòè è ïîëîæèòåëüíûå ïîòîêè, âû÷èòàíèå ïðîèçâîäèòñÿ òîëüêî â îäíóñòîðîíó.Óòâåðæäåíèå 1.2.1(î âû÷èòàíèè).Ïóñòü f äîïóñòèìûé ïîòîê â ñåòè ñ íåëèíåéíûìèâîçðàñòàþùèìè óñèëåíèÿìè g . Òîãäà â îñòàòî÷íîé ñåòè ñ óñèëåíèÿìè∗gm(x) = gm (x + f (m)) − gm (f (m))êàæäûé äîïóñòèìûé ïîòîê f ′ ñîîòâåòñòâóåò äîïóñòèìîìó ïîòîêó f +f ′ â èñõîäíîé ñåòè.Îáðàòíîå íåâåðíî (ò.å. ìíîæåñòâî äîïóñòèìûõ ïîòîêîâ ïðè âû÷èòàíèè ñóæàåòñÿ).Äîêàçàòåëüñòâî.Âî-ïåðâûõ, óíêöèè óñèëåíèÿ â ìîäèèöèðîâàííîé ñåòè îïðåäåëåíû êîð-ðåêòíî, ïîñêîëüêó óíêöèÿg ∗ ïî-ïðåæíåìó îñòàåòñÿ íåîòðèöàòåëüíîé (èç íåå âû÷èòàåòñÿ äî-ïóñòèìûé ïîòîê, ò.å.
ðàçíîñòü íåîòðèöàòåëüíà), âîçðàñòàþùåé è íåïðåðûâíîé (ïî îïðåäåëåíèþ). Òåïåðü èñòèííîñòü ïðÿìîãî óòâåðæäåíèÿ î÷åâèäíà. Ëîæíîñòü îáðàòíîãî óòâåðæäåíèÿñëåäóåò, íàïðèìåð, èç òîãî, ÷òî íóëåâîìó ïîòîêó â èñõîäíîé ñåòè ìîæåò íå ñîîòâåòñòâîâàòüíèêàêîé äîïóñòèìûé ïîòîê â îñòàòî÷íîé ñåòè.Âèðòóàëüíûå ñåòè ñ íåëèíåéíûìè óñèëåíèÿìè è òåîðåìà î äîñòèæåíèè ìàêñèìóìàÒåîðåìà 1(î äîñòèæåíèè ìàêñèìàëüíîãî çíà÷åíèÿ îïòèìàëüíûì ïîòîêîì).1.
Åñëèóñèëåíèå â äóãå m gm (x) = max(g1m (x), . . . , gkm(x)), òî ñóùåñòâóåò îïòèìàëüíûéïñåâäîïîòîê, ñîâïàäàþùèé ñ îïòèìàëüíûì ïñåâäîïîòîêîì â îäíîé èç k âñïîìîãàòåëüíûõ çàäà÷, â êîòîðûõ óñèëåíèå â äóãå m çàìåíÿåòñÿ íà gjm .2. Åñëè ñòîèìîñòü â äóãå m pm (x) = min(p1m (x), . . . , pkm (x)), òî ñóùåñòâóåò îïòèìàëüíûé (ïñåâäî)ïîòîê, ñîâïàäàþùèé ñ îïòèìàëüíûì (ïñåâäî)ïîòîêîì â îäíîé èç kâñïîìîãàòåëüíûõ çàäà÷, â êîòîðûõ ñòîèìîñòü â äóãå m çàìåíÿåòñÿ íà pjm.Äîêàçàòåëüñòâî.1.
Äëÿ îïòèìàëüíîãî ïñåâäîïîòîêàðÿäî÷åííîñòè, äîñòèãàåòñÿ íà îäíîé èç óíêöèéñòèìûì è îïòèìàëüíûì âj -éf (m)gjm.ìàêñèìóì, ïî ëèíåéíîé óïî-Äîêàæåì, ÷òîfÿâëÿåòñÿ äîïó-âñïîìîãàòåëüíîé çàäà÷å. Äîïóñòèìîñòü ñëåäóåò èç ñî-îòíîøåíèé, îïðåäåëÿþùèõ ïñåâäîïîòîê, â êîòîðûõ âj -éçàäà÷å ñòîèò óñèëåíèågjm .32Îïòèìàëüíîñòü èç òîãî, ÷òî ïðè ïåðåõîäå êj -éçàäà÷å óíêöèÿ óñèëåíèÿ óìåíüøà-åòñÿ, à ñëåäîâàòåëüíî, ìíîæåñòâî ïñåâäîïîòîêîâ ñóæàåòñÿ.2. Äëÿ îïòèìàëüíîãî (ïñåâäî)ïîòîêàf (m)ìèíèìóì ñòîèìîñòè, ïî ëèíåéíîé óïîðÿäî÷åí-íîñòè, äîñòèãàåòñÿ íà îäíîé èç óíêöèépjm .Ïðè ýòîìâñïîìîãàòåëüíîé çàäà÷å, ïîñêîëüêó ïðè ïåðåõîäå êj -éfÿâëÿåòñÿ îïòèìàëüíûì âj -éçàäà÷å óíêöèÿ ñòîèìîñòè íåóìåíüøàåòñÿ, à ñëåäîâàòåëüíî, ìíîæåñòâî ñòîèìîñòèåé (ïñåâäî)ïîòîêîâ íå óìåíüøàåòñÿ.Òåîðåìó î äîñòèæåíèè ìàêñèìàëüíîãî çíà÷åíèÿ îïòèìàëüíûì ïîòîêîì ìîæíî èíòåðïðåòèðîâàòü òàê.
àññìàòðèâàåòñÿ âèðòóàëüíàÿ ñåòü, â êîòîðîé âìåñòî îäíîé äóãèïàðàëëåëüíûõ äóãm1 , . . . mk ,mkíî èñïîëüçîâàòü ìîæíî òîëüêî îäíó èç íèõ. Òîãäà îïòèìàëü-íûé ïîòîê â èñõîäíîé ñåòè ñ óñèëåíèåìâ âèðòóàëüíîé ñåòè ñ óñèëåíèÿìègm = max(g1m , . . . , gkm )g1m , . . . , gkm .ðàâåí îïòèìàëüíîìó ïîòîêóÈ íàîáîðîò, çàäà÷ó â âèðòóàëüíîé ñåòèìîæíî àíàëîãè÷íî ñâåñòè ê çàäà÷å â îáû÷íîé ñåòè, îáúåäèíÿÿ óñèëåíèÿ ñ ïîìîùüþ óíêöèèìàêñèìóìà. Àíàëîãè÷íàÿ èíòåðïðåòàöèÿ âîçìîæíà äëÿ ñòîèìîñòåé.Î ðîëè ïðîïóñêíîé ñïîñîáíîñòè â ñåòè ñ íåëèíåéíûìè óñèëåíèÿìè çàäà÷å ñ ëèíåéíûìè óñèëåíèÿìè âàæíóþ ðîëü èãðàþò êàê óñèëåíèÿ, òàê è ïðîïóñêíûå ñïîñîáíîñòè. Íî îêàçûâàåòñÿ, ÷òî â çàäà÷å ñ íåëèíåéíûìè óñèëåíèÿìè ïðîïóñêíûå ñïîñîáíîñòèìîæíî îòêèíóòü:Óòâåðæäåíèå 1.2.2(î ðîëè ïðîïóñêíîé ñïîñîáíîñòè).Åñëè â ñåòè N íåò äóã, èäóùèõèç ñòîêà, òî ìíîæåñòâî F ′ (N) îïòèìàëüíûõ (â ñìûñëå çíà÷åíèÿ è ñòîèìîñòè) ïñåâäîïîòîêîâ â ñåòè ñ âîçðàñòàþùèìè óíêöèÿìè óñèëåíèÿ gm è ïðîïóñêíûìè ñïîñîáíîñòÿìèc(m) ñîâïàäàåò ñ ìíîæåñòâîì F ′ (N ∗ ) îïòèìàëüíûõ ïñåâäîïîòîêîâ â ñåòè N ∗ ñ óíêöèÿìè∗óñèëåíèÿ gm(x) = gm (min(x, c(m))) è áåñêîíå÷íûìè ïðîïóñêíûìè ñïîñîáíîñòÿìè.Äîêàçàòåëüñòâî.ñåòèN ∗.Äîêàæåì, ÷òî êàæäûé ïñåâäîïîòîê â ñåòèÄåéñòâèòåëüíî, ïóñòüf ïñåâäîïîòîê â ñåòèN.∗c(m) ⇒ gm(f (m)) = gm (f (m)).Äîêàæåì òåïåðü, ÷òî êàæäîìó ïñåâäîïîòîêó â ñåòèïñåâäîïîòîê â ñåòèf = min(f ∗ , c)N.Äåéñòâèòåëüíî, åñëèf∗Nÿâëÿåòñÿ ïñåâäîïîòîêîì è âÒîãäà äëÿ ëþáîé äóãèN∗m f (m) ≤ñîîòâåòñòâóåò ýêâèâàëåíòíûé ïñåâäîïîòîê â ñåòèN ∗,òî ïñåâäîïîòîêêîððåêòåí, äàåò òî æå çíà÷åíèå â ñòîêå è íå áîëüøóþ ñòîèìîñòü.33Çàìå÷àíèå1.2.3.
Äàæå, åñëè â ñåòè åñòü äóãè, èäóùèå èç ñòîêà, ìîæíî ïðåîáðàçîâàòü åå âýêâèâàëåíòíóþ ñåòü, â êîòîðîé òàêèõ äóã íå áóäåò. Äîñòàòî÷íî äëÿ ýòîãî äîáàâèòü âåðøèíó íîâûé ñòîê, è ê íåé äóãó îò ñòàðîãî ñòîêà.1.2.4Ñåòü ñ íåëèíåéíûìè óñèëåíèÿìè ñ ïàðàëëåëüíûì ñîåäèíåíèåìäóãÏàðàëëåëüíîå ñîåäèíåíèå äóã ýòî ñåòü ñ 2 âåðøèíàìè, ñîåäèíåííûìèçàäàíû âåðõíèå ïðîïóñêíûå ñïîñîáíîñòèñòîèìîñòèp1 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
