В.Б. Алексеев - Введение в теорию сложности алгоритмов (1114532), страница 14
Текст из файла (страница 14)
. . , ek .Ìåæäó ðåáðîì e1i = (Ci−1 , Ci ), ñîîòâåòñòâóþùèì xi , è êàæäûì èç ðåáåðe1 , e2 , . . . , ek âñòàâèì ñîåäèíèòåëüíûå ðåáðà òàê, ÷òîáû îáðàçîâàëîñü kα-ãðàôîâ. Òàê ïîñòóïèì äëÿ âñåõ xi . Àíàëîãè÷íî ïîñòóïèì äëÿ âñåõ x̄iñ çàìåíîé e1i íà e0i . Ïîëó÷åííûé ãðàô îáîçíà÷èì Gā .Ëåììà 4.29.
Âêîãäà ÊÍÔKGā åñòü ãàìèëüòîíîâ öèêë òîãäà è òîëüêî òîãäà,âûïîëíèìà.Ïóñòü â Gā ñóùåñòâóåò ãàìèëüòîíîâ öèêë W . Ïîñâîéñòâàì α-ãðàôà (ñì.âûøå) ìîæíî óñëîâíî ñ÷èòàòü, ÷òî ãàìèëüòîíîâöèêë ïðîõîäèò ðîâíî ïî îäíîìó èç ðåáåð A1 B1 èëè A2 B2 α-ãðàôà.Ñëåäîâàòåëüíî, ìîæíî ñ÷èòàòü, ÷òî öèêë W ñíà÷àëà ïðîõîäèò ïî âñåìâåðøèíàì ïîäãðàôà G1 , ïîòîì ïî âñåì âåðøèíàì ïîäãðàôà G2 , ïðèýòîì âûïîëíÿåòñÿ òðåáóåìîå ñâîéñòâî äëÿ êàæäîãî α-ãðàôà. Äëÿ êàæäîéïàðû ðåáåð e0i , e1i â G2 öèêë W , î÷åâèäíî, äîëæåí ïðîõîäèòü ðîâíî ïîîäíîìó èç ýòèõ ðåáåð. Äëÿ êàæäîãî i ïîëîæèì xi = 0, åñëè W ïðîõîäèòïî e0i , è xi = 1, åñëè W ïðîõîäèò ïî e1i .
Ïîëó÷åííûé íàáîð îáîçíà÷èìγ̃ = (γ1 , . . . , γn ). Ðàññìîòðèì îäèí èç ïîäãðàôîâ Hj â G1 . Ïî ëåììå4.28 ãàìèëüòîíîâ öèêë W íå ïðîõîäèò ïî êðàéíåé ìåðå ïî îäíîìó èçîñíîâíûõ ðåáåð ïîäãðàôà Hj . Ïóñòü ýòîìó ðåáðó ñîñïîñòàâëåí ëèòåðàë tñ ïåðåìåííîé xi . Åñëè t = xi , òî ýòî ðåáðî ñîåäèíåíî α-ãðàôîì ñ e1i , åñëèt = x̄i , òî ñ e0i . Òàê êàê ïî äàííîìó ðåáðó öèêë W íå ïðîõîäèò, îí äîëæåíïðîõîäèòü ïî e1i , åñëè t = xi , è ïî e0i , åñëè t = x̄i . Èç âûáîðà γi ïîëó÷àåì,÷òî â ëþáîì ñëó÷àå t(γ̃) = 1 è, ñëåäîâàòåëüíî, Dj (γ̃) = 1. Ïîñêîëüêó ýòîâåðíî äëÿ âñåõ j , òî K(γ̃) = 1, òî åñòü ÊÍÔ K âûïîëíèìà.Äîêàçàòåëüñòâî.Îáðàòíî, ïóñòü ÊÍÔ K âûïîëíèìà è K(γ̃) = 1, ãäå γ̃ = (γ1 , .
. . , γn ).Ïðîâåäåì öèêë W ïî ïîäãðàôó G2 òàê, ÷òîáû äëÿ êàæäîãî i = 1, 2, . . . , nîí ïðîõîäèë ïî e0i , åñëè γi = 0, è ïî e1i , åñëè γi = 1. Òîãäà ïî ñâîéñòâàìα-ãðàôîâ öèêë W íå ìîæåò ïðîõîäèòü ïî îñíîâíîìó ðåáðó ïîäãðàôà G1 ,êîòîðîìó ïðèïèñàí ëèòåðàë t, òàêîé, ÷òî t(γ̃) = 1, è îáÿçàí ïðîõîäèòü ïîîñíîâíîìó ðåáðó, åñëè åìó ïðèïèñàí ëèòåðàë t, òàêîé, ÷òî t(γ̃) = 0. Òàêêàê Dj (γ̃) = 1 äëÿ âñåõ j , òî â êàæäîì ïîäãðàôå Hj ñóùåñòâóåò õîòÿ áû62îäíî ðåáðî, òàêîå, ÷òî äëÿ ñîîòâåòñòâóþùåãî åìó ëèòåðàëà tj âûïîëíÿåòñÿ tj (γ̃) = 1. Ñëåäîâàòåëüíî â êàæäîì ïîäãðàôå Hj ñóùåñòâóåò îäíî, äâàèëè òðè îñíîâíûõ ðåáðà, òàêèõ, ÷òî öèêë W íå äîëæåí ïî íèì ïðîõîäèòü,è äîëæåí ïðîõîäèòü ïî îñòàëüíûì îñíîâíûì ðåáðàì.
Ïî ëåììå 4.28 âêàæäîì Hj ìîæíî ïîñòðîèòü ãàìèëüòîíîâó öåïü, óäîâëåòâîðÿþùóþ ýòèìòðåáîâàíèÿì, è â öåëîì â ãðàôå Gā ìîæíî ïîñòðîèòü ãàìèëüòîíîâ öèêë.Ëåììà äîêàçàíà.Ïðîâåðèòü, ÿâëÿåòñÿ ëè ñëîâî ā ∈ A∗ 3-ÊÍÔ, è ïîñòðîèòü ãðàôGā , åñëè ā = K ýòî 3-ÊÍÔ, ìîæíî çà ïîëèíîìèàëüíîå (îò äëèíû ā)âðåìÿ. Ïîýòîìó ìû ïîëó÷àåì ïîëèíîìèàëüíîå ñâåäåíèå çàäà÷è 3-ÂÛÏê çàäà÷å ÃÖ. Òàê êàê çàäà÷à 3-ÂÛÏ N P -ïîëíà è ÃÖ ∈ N P , òî è çàäà÷àÃÖ N P -ïîëíà. Òåîðåìà 4.18 äîêàçàíà.Èíòåðåñíî, ÷òî ñëåäóþùàÿ áëèçêàÿ çàäà÷à îêàçûâàåòñÿ ïîëèíîìèàëüíîé.Îïðåäåëåíèå.
Ìóëüòèãðàôîì íàçûâàåòñÿ ãðàô, â êîòîðîì ðàçðåøåíû êðàòíûå ðåáðà (òî åñòü ðåáðà, ñîåäèíÿþùèå îäíó è òó æå ïàðóâåðøèí).Îïðåäåëåíèå. Ýéëåðîâûì öèêëîì â ìóëüòèãðàôå íàçûâàåòñÿöèêë, ïðîõîäÿùèé ïî êàæäîìó ðåáðó ðîâíî îäèí ðàç è ïðîõîäÿùèé ïîâñåì âåðøèíàì.Òåîðåìà 4.19. Ýéëåðîâ öèêë â ìóëüòèãðàôå ñóùåñòâóåò òîãäàè òîëüêî òîãäà, êîãäà ìóëüòèãðàô ñâÿçíûé è ñòåïåíè âñåõ âåðøèí âìóëüòèãðàôå ÷åòíû, ïðè÷åì ñóùåñòâóåò ïîëèíîìèàëüíûé àëãîðèòì,êîòîðûé, â ñëó÷àå, êîãäà ìóëüòèãðàô ñâÿçíûé è ñòåïåíè âñåõ âåðøèíâ ìóëüòèãðàôå ÷åòíû, ñòðîèò ýéëåðîâ öèêë.Íåîáõîäèìîñòü ñëåäóåò èç òîãî, ÷òî åñëè ýéëåðîâöèêë ïðîõîäèò ÷åðåç âåðøèíó k ðàç, òî ñòåïåíü ýòîé âåðøèíû äîëæíàðàâíÿòüñÿ 2k .
Ïóñòü òåïåðü âñå ñòåïåíè ÷åòíû. Âûáåðåì ëþáóþ âåðøèíóv1 è áóäåì ñòðîèòü ïóòü ïî ðåáðàì, èñïîëüçóÿ ëþáûå åùå íå ïðîéäåííûåðåáðà, äî òåõ ïîð, ïîêà íå îêàæåìñÿ â òóïèêå. Òàê êàê ñòåïåíü ëþáîéâåðøèíû ÷åòíà, òî òóïèê íå ìîæåò îáðàçîâàòüñÿ íè â îäíîé âåðøèíå,îòëè÷íîé îò v1 .  ðåçóëüòàòå ïîëó÷èì íåêîòîðûé öèêë. Åñëè ýòîò öèêëíå ñîäåðæèò âñåõ ðåáåð ìóëüòèãðàôà, òî, â ñèëó ñâÿçíîñòè ìóëüòèãðàôà,ñóùåñòâóåò íà ïîñòðîåííîì öèêëå õîòÿ áû îäíà âåðøèíà v2 , êîòîðàÿèíöèäåíòíà íå ïðîéäåííîìó ðåáðó. Òîãäà ðàññìîòðèì óæå ïîñòðîåííûéöèêë, êàê íà÷èíàþùèéñÿ è êîí÷àþùèéñÿ â âåðøèíå v2 .
Ïîñëå ÷åãîîïÿòü ïðîäîëæèì ïîñòðîåíèå öèêëà èç âåðøèíû v2 . Ýòîò ïðîöåññ áóäåìïðîäîëæàòü ðåêóðñèâíî, ïîêà â öèêë íå âîéäóò âñå ðåáðà. Îïèñàííûéàëãîðèòì, î÷åâèäíî, ïîëèíîìèàëåí îòíîñèòåëüíî ÷èñëà ðåáåð.Äîêàçàòåëüñòâî.635. Çàäà÷è îïòèìèçàöèè ïðàêòè÷åñêèõ ïðèëîæåíèÿõ ÷àñòî âîçíèêàþò çàäà÷è îïòèìèçàöèè, êîòîðûå èìåþò ñëåäóþùóþ ñòðóêòóðó. Êàæäîìó âõîäó x ñîïîñòàâëÿåòñÿ íåêîòîðîå ìíîæåñòâî Yx äîïóñòèìûõ ðåøåíèé. Çàäàí ôóíêöèîíàëF : Yx → R, ãäå Rìíîæåñòâî äåéñòâèòåëüíûõ ÷èñåë. Òðåáóåòñÿ íàéòèmin F (y)y∈Yxèëèmax F (y)y∈Yxèëè òî äîïóñòèìîå ðåøåíèå y0 , íà êîòîðîì äîñòèãàåòñÿ îïòèìàëüíîåçíà÷åíèå ôóíêöèîíàëà. Åñëè ôóíêöèîíàë F âû÷èñëÿåòñÿ áûñòðî, òîíàéäÿ îïòèìàëüíîå äîïóñòèìîå ðåøåíèå, ìû ìîæåì ëåãêî ïîëó÷èòü èîïòèìàëüíîå çíà÷åíèå ôóíêöèîíàëà Fîïò . Îáðàòíîå, âîîáùå ãîâîðÿ, íåÿñíî: ìîæåò ñóùåñòâîâàòü áûñòðûé àëãîðèòì, êîòîðûé íàõîäèò Fîïò , íåíàõîäÿ îïòèìàëüíîãî ðåøåíèÿ.Ñ êàæäîé çàäà÷åé îïòèìèçàöèè ìîæíî ñâÿçàòü çàäà÷ó ðàñïîçíàâàíèÿ. Ïðè ýòîì íà âõîä êðîìå x ïîäàåòñÿ ÷èñëî k è ñïðàøèâàåòñÿ, âåðíîëè, ÷òî Fîïò 6 k (èëè Fîïò > k ).Íà ïðàêòèêå äëÿ ðåøåíèÿ çàäà÷ îïòèìèçàöèè ÷àñòî èñïîëüçóþòñÿàëãîðèòìû, íàçûâàåìûå æàäíûìè èëè ãðàäèåíòíûìè.
 òàêèõ àëãîðèòìàõ äîïóñòèìîå ðåøåíèå ñòðîèòñÿ ïîñòåïåííî ïî øàãàì, ïðè÷åì íàêàæäîì øàãå äåëàåòñÿ âûáîð, îïòèìàëüíûé äëÿ äàííîãî øàãà. Êàê ìûóâèäèì íèæå, òàêîé ïîäõîä íå âñåãäà ïðèâîäèò ê îïòèìàëüíîìó ðåøåíèþâ öåëîì. Îäíàêî äëÿ ñëåäóþùåé çàäà÷è îí âñåãäà äàåò îïòèìàëüíîåðåøåíèå. Íàïîìíèì, ÷òî äåðåâîì íàçûâàåòñÿ ëþáîé íåîðèåíòèðîâàííûéñâÿçíûé ãðàô áåç öèêëîâ. Ïîäãðàô G1 ãðàôà G íàçûâàåòñÿ îñòîâíûì,åñëè G1 ñîäåðæèò âñå âåðøèíû ãðàôà G. ×åðåç Kn îáîçíà÷àåòñÿ ïîëíûéãðàô íà n âåðøèíàõ, òî åñòü ãðàô, â êîòîðîì êàæäàÿ ïàðà âåðøèíñîåäèíåíà ðåáðîì.5.1. Çàäà÷à î êðàò÷àéøåì îñòîâíîì äåðåâåíåîðèåíòèðîâàííûé ïîëíûé ãðàô Kn , â êîòîðîì äëÿ ëþáîãîðåáðà e çàäàí âåñ w(e) > 0.Òðåáóåòñÿ: âûäåëèòü â Kn îñòîâíîå äåðåâî ñ ìèíèìàëüíîé ñóììîéâåñîâ ðåáåð.Çàìå÷àíèå. Íà ïðàêòèêå ýòî îçíà÷àåò òðåáîâàíèå ïîñòðîèòü ñåòüìèíèìàëüíîé ñòîèìîñòè, ñâÿçûâàþùóþ n äàííûõ îáúåêòîâ.Íàïîìíèì íåêîòîðûå ôàêòû èç òåîðèè ãðàôîâ [3].Âõîä:Óòâåðæäåíèå 1.
Åñëè â ãðàôå ñn − 1,òî ãðàô íå ñâÿçíûé.64nâåðøèíàìè ÷èñëî ðåáåðq <Óòâåðæäåíèå 2. Åñëè â ãðàôå÷èñëî ðåáåð è âåðøèí), òîGGíåò öèêëîâ èq = n − 1 (q, n äåðåâî.Óòâåðæäåíèå 3.  ëþáîì äåðåâå ñnâåðøèíàìè ÷èñëî ðåáåðq=n − 1.Óòâåðæäåíèå 4. Åñëè ê äåðåâó äîáàâèòü íîâîå ðåáðî íà òåõ æåâåðøèíàõ, òî îáðàçóåòñÿ ðîâíî 1 öèêë.Ðàññìîòðèì ñëåäóþùèé àëãîðèòì äëÿ çàäà÷è î êðàò÷àéøåì îñòîâíîì äåðåâå.1. Âçÿòü ëþáîå ðåáðî e1 ìèíèìàëüíîãî âåñà.2.
Ðåêóðñèâíûé øàã: ïóñòü óæå âûáðàíû ðåáðà e1 , e2 , . . . , em . Åñëèm = n − 1, òî îñòàíîâèòüñÿ. Èíà÷å, ñðåäè âñåõ ðåáåð, íå îáðàçóþùèõöèêëîâ ñ e1 , e2 , . . . , em , âçÿòü ðåáðî em+1 ìèíèìàëüíîãî âåñà, è ïîâòîðèòüðåêóðñèâíûé øàã.Àëãîðèòì äåëàåò ìåíüøå, ÷åì n èòåðàöèé è íà êàæäîé ïðîñìàòðèâàåò ìåíåå, ÷åì n2 ðåáåð. Ïðè ýòîì, åñëè èç ðåáåð e1 , e2 , . . . , em ñôîðìèðîâàòü ñâÿçíûå êîìïîíåíòû, òî òîò ôàêò, ÷òî em+1 íå îáðàçóåò ñ íèìèöèêëîâ, ýêâèâàëåíòåí òîìó, ÷òî êîíöû ðåáðà em+1 íå ëåæàò â îäíîéñâÿçíîé êîìïîíåíòå. Ýòî ñâîéñòâî ëåããêî ïðîâåðÿåòñÿ.
Òàêèì îáðàçîì,àëãîðèòì ìîæåò áûòü ðåàëèçîâàí ñ ïîëèíîìèàëüíûì îò n ÷èñëîì îïåðàöèé, âêëþ÷àþùèõ ïîèñê èíôîðìàöèè è ñðàâíåíèå âåñîâ.Òåîðåìà 5.1. Îïèñàííûé àëãîðèòì êîððåêòíî ñòðîèò ìèíèìàëüíîå îñòîâíîå äåðåâî.1) Äîêàæåì, ÷òî åñëè m < n − 1, òî ñóùåñòâóþòðåáðà, íå îáðàçóþùèå öèêëîâ ñ e1 , e2 , . . . , em .
Åñëè m < n−1, òî ïîäãðàô,ñîñòîÿùèé èç âñåõ âåðøèí è ðåáåð e1 , e2 , . . . , em , íå ñâÿçíûé (ïî óòâ. 1).Åñëè âçÿòü ëþáîå ðåáðî, ñîåäèíÿþùåå äâå âåðøèíû èç ðàçíûõ êîìïîíåíòýòîãî ïîäãðàôà, òî öèêëû íå îáðàçóþòñÿ. Òàêèì îáðàçîì, àëãîðèòìïðîðàáîòàåò äî m = n − 1.2) Ïðè îñòàíîâêå m = n − 1 è ðåáðà e1 , e2 , . .
. , em íå îáðàçóþòöèêëîâ. Òîãäà (ïî óòâ. 2) îíè îáðàçóþò îñòîâíîå äåðåâî.3) Ïóñòü àëãîðèòì ñòðîèò îñòîâíîå äåðåâî D. Äîêàæåì, ÷òî Dìèíèìàëüíîå îñòîâíîå äåðåâî. Ðàññìîòðèì âñå ìèíèìàëüíûå îñòîâíûå äåðåâüÿ, è ïóñòü T ìèíèìàëüíîå îñòîâíîå äåðåâî, èìåþùåå ñ Díàèáîëüøåå ÷èñëî îáùèõ ðåáåð. Äîêàæåì (îò ïðîòèâíîãî), ÷òî D = T .Äîïóñòèì, ÷òî T 6= D. Òàê êàê è â T è â D n − 1 ðåáðî (óòâ. 3), òî â Dåñòü ðåáðà, íå âõîäÿùèå â T . Ïóñòü â àëãîðèòìå ðåáðà äåðåâà D ïîÿâëÿëèñü â ïîðÿäêå: e1 , e2 , . . . , en−1 è ïóñòü ðåáðà e1 , e2 , . . .
, ek ïðèíàäëåæàòäåðåâó T , à ek+1 ∈/ T . Ðàññìîòðèì ãðàô H = T ∪ {ek+1 }. Â H èìååòñÿåäèíñòâåííûé öèêë C (óòâ. 4), ñîäåðæàùèé ek+1 . Òàê êàê D íå ñîäåðæèòÄîêàçàòåëüñòâî.65öèêëîâ, òî â C åñòü õîòÿ áû îäíî ðåáðî e òàêîå, ÷òî e ∈/ D. Ïðè ýòîìe ∈ T . Ðàññìîòðèì H1 = H \ {e}. Ãðàô H1 ñâÿçíûé è áåç öèêëîâ, òîåñòü H1 îñòîâíîå äåðåâî. Ïóñòü w(H1 ) è w(T ) ñóììû âåñîâ ðåáåð âH1 è T . Òàê êàê T ìèíèìàëüíîå îñòîâíîå äåðåâî, òî w(H1 ) > w(T ) èw(H1 ) = w(T ) + w(ek+1 ) − w(e) > w(T ).Îòñþäà w(e) 6 w(ek+1 ). Ïîñêîëüêó e ∈ T è e1 , e2 , . .
. , ek ïðèíàäëåæàò äåðåâó T , òî e íå îáðàçóåò öèêëîâ ñ e1 , e2 , . . . , ek . Åñëè áû áûëîw(e) < w(ek+1 ), òî íà k + 1-ì øàãå àëãîðèòìà íå ìîãëî áû âûáèðàòüñÿðåáðî ek+1 . Çíà÷èò w(e) = w(ek+1 ) è w(H1 ) = w(T ). Ïîëó÷àåì, ÷òî H1 òàêæå ìèíèìàëüíîå îñòîâíîå äåðåâî, íî èìåþùåå ñ D íà 1 îáùåå ðåáðîáîëüøå, ÷åì T ñ D. Ýòî ïðîòèâîðå÷èò âûáîðó äåðåâà T . Èç ïîëó÷åííîãîïðîòèâîðå÷èÿ ñëåäóåò, ÷òî äîëæíî áûòü D = T , òî åñòü D ìèíèìàëüíîå îñòîâíîå äåðåâî.
Òåîðåìà äîêàçàíà.5.2. Ïðèáëèæåííûå àëãîðèòìûÇàäà÷à î ìèíèìàëüíîì âåðøèííîì ïîêðûòèè (ÌÂÏ).Áóäåì ãîâîðèòü, ÷òî âåðøèíà v ïîêðûâàåò ðåáðî e, åñëè îíà ÿâëÿåòñÿ îäíèì èç êîíöîâ ðåáðà e. Ïîäìíîæåñòâî A ⊆ V âåðøèí ãðàôàG = (V, E) íàçûâàåòñÿ âåðøèííûì ïîêðûòèåì, åñëè âåðøèíû èç Aïîêðûâàþò âñå ðåáðà èç E .Âõîä: íåîðèåíòèðîâàííûé ãðàô G = (V, E).Òðåáóåòñÿ: íàéòè âåðøèííîå ïîêðûòèå (ÂÏ) ìèíèìàëüíîé ìîùíîñòè.Æàäíûé àëãîðèòì äëÿ ÌÂÏ.Íà êàæäîì øàãå âûáèðàåòñÿ ëþáàÿ âåðøèíà, ïîêðûâàþùàÿ íàèáîëüøåå ÷èñëî åùå íå ïîêðûòûõ ðåáåð.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
