В.Б. Алексеев - Введение в теорию сложности алгоритмов (В.Б. Алексеев - Введение в теорию сложности алгоритмов.pdf), страница 13

Îòñþäàñëåäóåò óòâåðæäåíèå ëåììû.Äîêàçàòåëüñòâî.Ëåììà 4.23. Àëãîðèòì ïðàâèëüíî ðåøàåò çàäà÷ó 2-ÂÛÏ.1) Ïóñòü K = D1 D2 · . . . · Ds èñõîäíàÿ 2-ÊÍÔ èïóñòü â êîíå÷íîé ÊÍÔ K 0 åñòü ñîìíîæèòåëü 0. Ïî ëåììå 4.21 K = K 0 è,ñëåäîâàòåëüíî, K ≡ 0, òî åñòü K íåâûïîëíèìà. 2) Ïóñòü â êîíå÷íîé2-ÊÍÔ K 0 íåò 0. Ïî ïîñòðîåíèþ K 0 çàìêíóòà îòíîñèòåëüíî âçÿòèÿðåçîëüâåíò, òî åñòü ðåçîëüâåíòà ëþáûõ äâóõ äèçúþíêòîâ èç K 0 ñíîâàñîäåðæèòñÿ â K 0 . Äîêàæåì, ÷òî ëþáàÿ 2-ÊÍÔ ñ òàêèì ñâîéñòâîì, íåñîäåðæàùàÿ ñîìíîæèòåëÿ 0, âûïîëíèìà.

Äîêàçàòåëüñòâî ïðîâåäåì èíÄîêàçàòåëüñòâî.57äóêöèåé ïî ÷èñëó ïåðåìåííûõ n â 2-ÊÍÔ K 0 .00Áàçèñ èíäóêöèè: n = 1. Òîãäà K = xi èëè K = x̄i .  ëþáîì ñëó÷àåK 0 âûïîëíèìà.Èíäóêòèâíûé ïåðåõîä. Ïóñòü óòâåðæäåíèå âåðíî äëÿ 2-ÊÍÔ ñ n <m ïåðåìåííûìè è ïóñòü â K 0 èìååòñÿ m ïåðåìåííûõ x1 , x2 , . . . , xm . ÒîãäàK 0 = (xm ∨ t1 )(xm ∨ t2 ) · . . . · (xm ∨ tk )(x̄m ∨ t01 )(x̄m ∨ t02 ) · . . .. .

. · (x̄m ∨ t0l ) · C1 · C2 · . . . · Cr ,ãäå ti , t0j ëèòåðàëû, ëèáî 0, è C1 · C2 · . . . · Cr 2-ÊÍÔ ñ ïåðåìåííûìèx1 , x2 , . . . , xm−1 , çàìêíóòàÿ îòíîñèòåëüíî âçÿòèÿ ðåçîëüâåíò. Ïî ïðåäïîëîæåíèþ èíäóêöèè ñóùåñòâóåò íàáîð α̃ = (α1 , . . . , αm−1 ), íà êîòîðîìC1 · C2 · . . . · Cr ðàâíî 1. Åñëè áû ñóùåñòâîâàëè ti è t0j òàêèå, ÷òî ti (α̃) = 0è t0j (α̃) = 0, òî áûëî áû è ti (α̃) ∨ t0j (α̃) = 0. Íî ti ∨ t0j ðåçîëüâåíòàäèçúþíêòîâ xm ∨ ti è x̄m ∨ t0j . Òàê êàê 2-ÊÍÔ K 0 çàìêíóòà îòíîñèòåëüíîâçÿòèÿ ðåâîëüâåíò, òî ti ∨ t0j ñîäåðæèòñÿ ñðåäè C1 , C2 , .

. . , Cr . Íî ýòîïðîòèâîðå÷èò òîìó, ÷òî Cv (α̃) = 1 ïðè âñåõ v . Ñëåäîâàòåëüíî, ëèáî âñåti (α̃) = 1, ëèáî âñå t0j (α̃) = 1.  ïåðâîì ñëó÷àå K 0 âûïîëíèìà íà íàáîðå(α̃, 0), âî âòîðîì íà íàáîðå (α̃, 1).Òåîðåìà 4.15 ïîëíîñòüþ äîêàçàíà.4.8. ÍåêîòîðûåN P -ïîëíûåçàäà÷è íà ãðàôàõÒåîðåìà 4.16. Çàäà÷à ÊËÈÊÀ ÿâëÿåòñÿN P -ïîëíîé.Äîêàçàòåëüñòâî. Ïîêàæåì, ÷òî çàäà÷à ÂÛÏ ïîëèíîìèàëüíî ñâîäèòñÿ ê çàäà÷å ÊËÈÊÀ. Äëÿ ýòîãî êàæäîìó ñëîâó ā â àëôàâèòå ÿçûêàÂÛÏ ñîïîñòàâèì ïàðó ϕ(ā) = (G, k), ãäå G íåêîòîðûé ãðàô è k íàòóðàëüíîå ÷èñëî, òàê, ÷òîáû â G ñóùåñòâîâàëà êëèêà ñ k âåðøèíàìèòîãäà è òîëüêî òîãäà, êîãäà ā âûïîëíèìàÿ ÊÍÔ. Åñëè ā íå ÊÍÔ,òî ïîëîæèì ϕ(ā) = (G2 , 2), ãäå G2 ãðàô ñ 2 âåðøèíàìè è áåç ðåáåð(î÷åâèäíî, â G2 íåò êëèêè ñ 2 âåðøèíàìè).

Ïóñòü òåïåðü ā ÊÍÔ èā = D1 · D2 · . . . · Ds , ãäå Di = ti,1 ∨ ti,2 ∨ . . . ∨ ti,mi äèçúþíêòû. Ïîñòðîèìãðàô ϕ(ā) = Gā = (V, E) ñ ìíîæåñòâîì âåðøèí V è ìíîæåñòâîì ðåáåðE ñëåäóþùèì îáðàçîì. Êàæäîìó ëèòåðàëó ti,j èç ā ñîïîñòàâèì âåðøèíóvi,j è áóäåì ñ÷èòàòü, ÷òî(vi1 ,j1 , vi2 ,j2 ) ∈ E ⇐⇒ (i1 6= i2 ) è (ti2 ,j2 6= t̄i1 ,j1 ).Ïîëîæèì k = s, ãäå s ÷èñëî äèçúþíêòîâ â ā.Ëåììà 4.24.

Âòîãäà, êîãäà ÊÍÔāGāåñòü êëèêà ñâûïîëíèìà.58sâåðøèíàìè òîãäà è òîëüêîÏóñòü ÊÍÔ ā ïðèíèìàåò çíà÷åíèå 1 íà íàáîðå α̃.Òîãäà Di (α̃) = 1 äëÿ âñåõ i. Ñëåäîâàòåëüíî, äëÿ êàæäîãî i ñóùåñòâóåò jiòàêîå, ÷òî ti,ji = 1. Òîãäà ñðåäè t1,j1 , t2,j2 , . . . , ts,js íåò ïðîòèâîïîëîæíûõëèòåðàëîâ. Ïîýòîìó ëþáûå âåðøèíû èç v1,j1 , v2,j2 , .

. . , vs,js ñîåäèíÿþòñÿ âGā ðåáðîì, òî åñòü îáðàçóþò êëèêó ñ s âåðøèíàìè.Îáðàòíî, ïóñòü â ãðàôå Gā åñòü êëèêà ñ s âåðøèíàìèvi1 ,j1 , vi2 ,j2 , . . . , vis ,js . Òîãäà i1 , i2 , . . . , is âñå ðàçëè÷íû, òî åñòü ëèòåðàëûèç ñåìåéñòâà M = {ti1 ,j1 , ti2 ,j2 , . . . , tis ,js } âõîäÿò ïî îäíîìó â êàæäûéäèçúþíêò ÊÍÔ ā, ïðè÷åì ñðåäè ýòèõ ëèòåðàëîâ íåò ïðîòèâîïîëîæíûõ.Ïóñòü x1 , x2 . .

. , xn âñå ïåðåìåííûå èç ā. Äëÿ êàæäîãî k ïîëîæèìxk = 1, åñëè ëèòåðàë xk âñòðå÷àåòñÿ â M , xk = 0, åñëè x̄k âñòðå÷àåòñÿ âM , è xk ëþáîå, åñëè íè xk , íè x̄k íåò â M . Òîãäà íà ïîñòðîåííîì íàáîðåα̃ âñå ëèòåðàëû èç M îáðàùàþòñÿ â 1 è, ñëåäîâàòåëüíî, âñå äèçúþíêòûè âñÿ ÊÍÔ ā ïðèíèìàþò çíà÷åíèå 1, òî åñòü ÊÍÔ ā âûïîëíèìà. Ëåììàäîêàçàíà.Òàêèì îáðàçîì ïåðåõîä ā → ϕ(ā) ÿâëÿåòñÿ ñâåäåíèåì çàäà÷è ÂÛÏê çàäà÷å ÊËÈÊÀ. Ðàñïîçíàòü, ÿâëÿåòñÿ ëè ā ÊÍÔ, è ïîñòðîèòü ïî āãðàô Gā è ÷èñëî k ìîæíî çà ïîëèíîìèàëüíîå âðåìÿ. Ïîýòîìó ýòî ïîëèíîìèàëüíîå ñâåäåíèå. Òàê êàê çàäà÷à ÂÛÏ N P -ïîëíà è ÊËÈÊÀ ∈ N P ,òî ïî òåîðåìå 4.13 ïîëó÷àåì, ÷òî è çàäà÷à ÊËÈÊÀ N P -ïîëíà. Òåîðåìà4.16 äîêàçàíà.Äîêàçàòåëüñòâî.Çàäà÷à î íåçàâèñèìîì ìíîæåñòâå âåðøèí (ÍÌ).ïàðà (G, k), ãäå G ãðàô, k íàòóðàëüíîå ÷èñëî.Âîïðîñ: ñóùåñòâóþò ëè â G k âåðøèí, îáðàçóþùèõ íåçàâèñèìîåìíîæåñòâî, òî åñòü ìíîæåñòâî, â êîòîðîì íèêàêèå âåðøèíû íå ñîåäèíåíûðåáðîì â G?Âõîä:HM ∈ N P .Äîêàçàòåëüñòâî.

Ñåðòèôèêàòîì ÿâëÿåòñÿ ñàìî íåçàâèñèìîå ìíîæåñòâî M ñ k âåðøèíàìè (åñëè òàêîå åñòü). Ïðîâåðèòü, ÷òî M ñîäåðæèòðîâíî k âåðøèí è ÿâëÿåòñÿ íåçàâèñèìûì, ìîæíî çà ïîëèíîìèàëüíîåâðåìÿ.Ëåììà 4.25.Çàäà÷à î âåðøèííîì ïîêðûòèè (ÂÏ).ïàðà (G, k), ãäå G ãðàô, k íàòóðàëüíîå ÷èñëî.Âîïðîñ: ñóùåñòâóåò ëè â G ìíîæåñòâî M èç k âåðøèí, îáðàçóþùèõâåðøèííîå ïîêðûòèå, òî åñòü òàêîå, ÷òî ëþáîå ðåáðî èç G èìååò õîòÿ áûîäèí êîíåö â M ?Âõîä:∈ NP .Äîêàçàòåëüñòâî. Ñåðòèôèêàòîì ÿâëÿåòñÿ ñàìî âåðøèííîå ïîêðûòèå M ñ k âåðøèíàìè (åñëè òàêîå åñòü). Ïðîâåðèòü, ÷òî M ñîäåðæèòËåììà 4.26.

ÂÏ59ðîâíî k âåðøèí è ÿâëÿåòñÿ âåðøèííûì ïîêðûòèåì, ìîæíî çà ïîëèíîìèàëüíîå âðåìÿ.Òåîðåìà 4.17. Çàäà÷è ÍÌ è ÂÏN P -ïîëíû.Ñîïîñòàâèì ïàðå (G, k) ïàðó (Ḡ, k), ãäå Ḡãðàô,ÿâëÿþùèéñÿ äîïîëíåíèåì ê G (òî åñòü â Ḡ òî æå ìíîæåñòâî âåðøèíV , ÷òî è â G, è äâå âåðøèíû ñîåäèíÿþòñÿ ðåáðîì â Ḡ òîãäà è òîëüêîòîãäà, êîãäà îíè íå ñîåäèíÿþòñÿ ðåáðîì â G).

Ïðè ýòîì ïîäìíîæåñòâîM ⊆ V ÿâëÿåòñÿ êëèêîé ñ k âåðøèíàìè â G òîãäà è òîëüêî òîãäà, êîãäàM ÿâëÿåòñÿ íåçàâèñèìûì ìíîæåñòâîì ñ k âåðøèíàìè â Ḡ. Ïîëó÷àåìñâåäåíèå (î÷åâèäíî, ïîëèíîìèàëüíîå) çàäà÷è ÊËÈÊÀ ê çàäà÷å ÍÌ. Òàêêàê çàäà÷à ÊËÈÊÀ N P -ïîëíà è HM ∈ N P , òî çàäà÷à ÍÌ N P -ïîëíàÿ.Ñîïîñòàâèì ïàðå (G, k) ïàðó (G, n − k), ãäå n = |V |÷èñëî âåðøèíâ ãðàôå G.

Ïðè ýòîì ïîäìíîæåñòâî M ⊆ V ÿâëÿåòñÿ íåçàâèñèìûììíîæåñòâîì ñ k âåðøèíàìè â G òîãäà è òîëüêî òîãäà, êîãäà V \ Mÿâëÿåòñÿ âåðøèííûì ïîêðûòèåì ñ n − k âåðøèíàìè â G. Ïîëó÷àåìïîëèíîìèàëüíîå ñâåäåíèå çàäà÷è ÍÌ ê çàäà÷å ÂÏ. Òàê êàê çàäà÷à ÍÌN P -ïîëíàÿ è ÂÏ ∈ N P , òî è çàäà÷à ÂÏ N P -ïîëíàÿ.Äîêàçàòåëüñòâî.Öèêë â ãðàôå, ïðîõîäÿùèé ÷åðåç êàæäóþ âåðøèíóðîâíî 1 ðàç, íàçûâàåòñÿ ãàìèëüòîíîâûì öèêëîì. Ãàìèëüòîíîâîé öåïüþíàçûâàåòñÿ íåçàìêíóòàÿ öåïü, ïðîõîäÿùàÿ ÷åðåç êàæäóþ âåðøèíó ðîâíî1 ðàç.Îïðåäåëåíèå.Çàäà÷à î ãàìèëüòîíîâîì öèêëå (ÃÖ).Âõîä:ïðîèçâîëüíûé ãðàô G.Âîïðîñ:åñòü ëè â G ãàìèëüòîíîâ öèêë?Ëåììà 4.27. ÃÖ∈ NP .Äëÿ äàííîãî ãðàôà G ñ n âåðøèíàìè ñåðòèôèêàòîì ÿâëÿåòñÿ ïîñëåäîâàòåëüíîñòü âåðøèí (v1 , v2 , .

. . , vn ). Àëãîðèòìïðîâåðêè ñåðòèôèêàòà äîëæåí óáåäèòüñÿ, ÷òî â ýòîì ñïèñêå ñòîëüêîæå âåðøèí, ñêîëüêî â ãðàôå G, ÷òî âñå îíè ðàçëè÷íû è ÷òî äëÿ âñåõj = 1, 2, . . . , n − 1 â ãðàôå G åñòü ðåáðî (vj , vj+1 ), à òàêæå åñòü ðåáðî(vn , v1 ). Âñå ýòî ìîæíî âûïîëíèòü çà ïîëèíîìèàëüíîå âðåìÿ.Äîêàçàòåëüñòâî.Òåîðåìà 4.18. Çàäà÷à ÃÖN P -ïîëíà.Ïîñòðîèì ïîëèíîìèàëüíîå ñâåäåíèå çàäà÷è3-ÂÛÏ ê çàäà÷å ÃÖ. Ðàññìîòðèì 2 âñïîìîãàòåëüíûõ ãðàôà: α-ãðàô èβ -ãðàô, èçîáðàæåííûå íà ðèñ.

1 è 2, ñîîòâåòñòâåííî.Äîêàçàòåëüñòâî.60Au1Au2uuuuuuuuuuuuBu1Bu2sPss C@C@ C @s Cs @ZZ @Z @sss ss Z s @sQRsSÐèñ. 2Ðèñ. 1Ïóñòü α-ãðàô (ðèñ. 1) ÿâëÿåòñÿ ïîäãðàôîì íåêîòîðîãî ãðàôà G,ïðè÷åì ñ äðóãèìè âåðøèíàìè ãðàôà ìîãóò ñîåäèíÿòüñÿ òîëüêî âåðøèíûA1 , A2 , B1 , B2 , è ïóñòü â G ñóùåñòâóåò ãàìèëüòîíîâ öèêë. Íåòðóäíî ïðîâåðèòü, ÷òî åñëè ýòîò öèêë âõîäèò âíóòðü α-ãðàôà, òî îí îáÿçàí ñðàçóîáîéòè âñå âíóòðåííèå âåðøèíû α-ãðàôà. Ïðè ýòîì, åñëè îí âõîäèò ÷åðåçâåðøèíó A1 , òî âûõîäèò îáÿçàòåëüíî ÷åðåç B1 è íàîáîðîò. Àíàëîãè÷íî,åñëè îí âõîäèò ÷åðåç A2 , òî âûõîäèò ÷åðåç B2 è íàîáîðîò. Ïîýòîìóóñëîâíî ìîæíî ñ÷èòàòü, ÷òî α-ãðàô èìååò âñåãî 2 ðåáðà A1 B1 è A2 B2è òðåáóåòñÿ, ÷òîáû öèêë ïðîõîäèë ðîâíî ïî îäíîìó èç íèõ.Ïóñòü β -ãðàô (ðèñ.

2) ÿâëÿåòñÿ ïîäãðàôîì íåêîòîðîãî ãðàôà G,ïðè÷åì ñ äðóãèìè âåðøèíàìè ãðàôà G ìîãóò ñîåäèíÿòüñÿ òîëüêî âåðøèíû P è S . Åñëè ãàìèëüòîíîâ öèêë âõîäèò â β -ãðàô ÷åðåç P èëè S ,òî îí äîëæåí ñðàçó îáîéòè âñå âåðøèíû ýòîãî β -ãðàôà (è âûéòè ÷åðåçäðóãóþ âåðøèíó ïàðû P, S ). β -ãðàôå (ðèñ. 2) 3 íèæíèõ ðåáðà P Q, QR è RS áóäåì íàçûâàòüîñíîâíûìè, à âåðøèíû P è S ãðàíè÷íûìè.Ëåììà 4.28. Íå ñóùåñòâóåò ãàìèëüòîíîâîé öåïè âβ -ãðàôåèçP â âåðøèíó S , ïðîõîäÿùåé ïî âñåì òðåì îñíîâíûì ðåáðàìP Q, QR, RS .

Äëÿ ëþáîãî äðóãîãî ïîäìíîæåñòâà îñíîâíûõ ðåáåð (âêëþ÷àÿ ïóñòîå ïîäìíîæåñòâî) ñóùåñòâóåò ãàìèëüòîíîâà öåïü èç P â S ,âåðøèíûïðîõîäÿùàÿ â òî÷íîñòè ïî ýòîìó ïîäìíîæåñòâó îñíîâíûõ ðåáåð.Ïåðâàÿ ÷àñòü ýòîé ëåììû î÷åâèäíà, äëÿ äîêàçàòåëüñòâà âòîðîé ÷àñòè äîñòàòî÷íî ðàññìîòðåòü âñå âîçìîæíûå ñëó÷àè è â êàæäîì ïîñòðîèòüñîîòâåòñòâóþùóþ ãàìèëüòîíîâó öåïü (ïîñòðîéòå).Ïóñòü A àëôàâèò çàäà÷è 3-ÂÛÏ. Êàæäîìó ñëîâó ā ∈ A∗ ìûñîïîñòàâèì ãðàô G òàê, ÷òîáû â G ñóùåñòâîâàë ãàìèëüòîíîâ öèêë òîãäàè òîëüêî òîãäà, êîãäà ā âûïîëíèìàÿ 3-ÊÍÔ. Åñëè ā ∈ A∗ è ā íå3-ÊÍÔ, òî ñîïîñòàâèì ā ãðàô G ñ äâóìÿ âåðøèíàìè è 1 ðåáðîì.

Î÷åâèäíî, â íåì íåò ãàìèëüòîíîâà öèêëà. Ïóñòü òåïåðü ā = K = D1 ·D2 ·. . .·Ds ïðîèçâîëüíàÿ 3-ÊÍÔ ñ ïåðåìåííûìè x1 , x2 , . . . , xn . Ïóñòü H1 , H2 , . . . , Hs β -ãðàôû ñ ãðàíè÷íûìè âåðøèíàìè Pj , Sj , j = 1, 2, . . . , s. Ñîåäèíèì61ðåáðàìè âåðøèíû Sj è Pj+1 äëÿ j = 1, 2, . . . , s − 1. Ïîëó÷åííûé ãðàôîáîçíà÷èì G1 . ×åðåç G2 îáîçíà÷èì ãðàô (òî÷íåå, ìóëüòèãðàô) ñ âåðøèíàìè C0 , C1 , . . . , Cn , â êîòîðîì äëÿ êàæäîãî i = 1, 2, .

. . , n åñòü 2 ðåáðà(Ci−1 , Ci ) è íåò äðóãèõ ðåáåð. Âåðøèíó P1 ãðàôà G1 ñîåäèíèì ðåáðîì ñC0 , à Ss ñîåäèíèì ðåáðîì ñ Cn . Èç äâóõ ðåáåð (Ci−1 , Ci ) îäíî ñîïîñòàâèìïåðåìåííîé xi , à äðóãîå x̄i . Ïåðâîå îáîçíà÷èì e1i , âòîðîå e0i .  êàæäîìïîäãðàôå Hj îñíîâíûå ðåáðà Pj Qj , Qj Rj , Rj Sj ñîïîñòàâèì ëèòåðàëàìtj,1 , tj,2 , tj,3 äèçúþíêòà Dj . Ïóñòü ëèòåðàë xi âñòðå÷àåòñÿ â k äèçúþíêòàõDj è â ïîäãðàôàõ Hj ëèòåðàëó xi ñîîòâåòñòâóþò k ðåáåð e1 , e2 , .