В.Б. Алекссев - Сложные алгоритмы (1132790), страница 11
Текст из файла (страница 11)
eSLI 1 = 0, TO t1(~) _ t2(~) = 1 I Di(~) = 1. eSLIm;3 = 1, TO tm;1 (~) _ tm(~) = 1 I Di(~) = 1. eSLI VE 1 = 1 I m;3 = 0,TO NAJDETSQ k TAKOE, ^TO k = 1, k+1 = 0. tAK KAK k _ tk+2 _ k+1 = 1,TO W \TOM SLU^AE tk+2(~) = 1 I Di(~) = 1. sLEDOWATELXNO, ESLI Fi = 1,TO I Di = 1. oBRATNO PUSTX Di(~) = 1. tOGDA SU]ESTWUET tk TAKOE, ^TOtk (~) = 1. eSLI k = 1 ILI k = 2, TO WYBEREM 1 = 2 = : : : = m;3 = 0.pRI \TOM Fi (~; ~) = 1. eSLI k = m ; 1 ILI k = m, TO WYBEREM1 = 2 = : : : = m;3 = 1. pRI \TOM OPQTX Fi (~; ~) = 1. w OSTALXNYHSLU^AQH POLOVIM 1 = 2 = : : : = k;2 = 1, k;1 = k = : : : = m;3 = 0:sNOWA POLU^IM Fi (~; ~) = 1. lEMMA DOKAZANA.pRODELAEM UKAZANNYE WY[E W PUNKTAH 2)-4) ZAMENY Di NA Fi,ISPOLXZUQ DLQ RAZNYH Di RAZNYE PEREMENNYE yj . tOGDA PO LEMME POLU^AEM, ^TO ESLI 3-knf F1 F2 : : : Fs RAWNA 1 NA KAKOM-TO NABORE, TO NATOM VE NABORE RAWNA 1 I knf D1 D2 : : : Ds, I OBRATNO, ESLI knfD1 D2 : : : Ds RAWNA 1 NA NEKOTOROM NABORE, TO SU]ESTWUET NABOR, NAKOTOROM 3-knf F1 F2 : : : Fs TAKVE RAWNA 1.
tAKIM OBRAZOM 3-knfF1 F2 : : : Fs WYPOLNIMA TOGDA I TOLXKO TOGDA, KOGDA WYPOLNIMA knfD1 D2 : : : Ds, TO ESTX NA[E PREOBRAZOWANIE QWLQETSQ SWEDENIEM ZADA^Iwyp K ZADA^E 3-wyp.rASPOZNATX, QWLQETSQ LI WHODNOE SLOWO a 2 A knf MOVNO ZAPOLINOMIALXNOE OT DLINY a WREMQ. pREOBRAZOWATX WSE Di W Fi TAKVEMOVNO ZA POLINOMIALXNOE WREMQ. pO\TOMU MY IMEEM POLINOMIALXNOESWEDENIE ZADA^I wyp K ZADA^E 3-wyp. pOSKOLXKU ZADA^A wyp QWLQETSQ NP -POLNOJ I 3-wyp 2 NP , TO PO TEOREME POLU^AEM, ^TO ZADA^A3-wyp QWLQETSQ NP -POLNOJ.pOSMOTRIM, NELXZQ LI W POSLEDNEJ TEOREME ZAMENITX 3 NA 2.,.,,.55.oPREDELENIE. knf, U KOTOROJ W KAVDOM DIZ_@NKTE NE BOLEE 2LITERALOW, BUDEM NAZYWATX 2-knf.zADA^A 2-WYPOLNIMOSTX (2-wyp).wHODNOJ ALFAWIT TOT VE, ^TO I W ZADA^E wyp.wOPROS WERNO LI, ^TO WHODNOE SLOWO | \TO 2-knf, KOTORAQ WYPOLNIMA.tEOREMA. dLQ ZADA^I wyp SU]ESTWUET ALGORITM S POLINOMIALXNOJ SLOVNOSTX@ TO ESTX wyp 2 PdOKAZATELXSTWO pROWERITX, QWLQETSQ LI WHODNOE SLOWO 2-knf,MOVNO ZA POLINOMIALXNOE WREMQ. pO\TOMU BUDEM S^ITATX, ^TO NAM UVEDANA 2-knf D1 D2 : : : Ds I TREBUETSQ WYQSNITX, WYPOLNIMA LI ONA.pUSTX DIZ_@NKTY D0 = xi _ t1 I D00 = xi _ t2 IME@T PROTIWOPOLOVNYELITERALY xi I xi (PRI \TOM MOVET BYTX t1 = ? ILI t2 = ?).
tOGDAREZOLXWENTOJ DIZ_@NKTOW D0 I D00 PO xi BUDEM NAZYWATX DIZ_@NKT D =t1 _ t2 (ESLI t1 = t2, TO t1 _ t2 = t1). eSLI t1 = ? I t2 = ?, TO POLOVIMD 0.lEMMA. dLQ L@BYH FORMUL A I B WYPOLNQETSQ RAWENSTWO(xi _ A)(xi _ B ) = (xi _ A)(xi _ B )(A _ B ):dOKAZATELXSTWO eSLI PRAWAQ ^ASTX RAWNA 1, TO, O^EWIDNO, I LEWAQ^ASTX RAWNA 1. eSLI PRAWAQ ^ASTX RAWNA 0, TO LIBO xi _ A = 0, LIBOxi _ B = 0, LIBO A _ B = 0. w PERWYH DWUH SLU^AQH LEWAQ ^ASTX RAWNA0.
w POSLEDNEM SLU^AE A = 0 I B = 0. tOGDA LEWAQ ^ASTX RAWNA (xi _0)(xi _ 0) = xi xi = 0. lEMMA DOKAZANA.lEMMA ( ) POKAZYWAET, ^TO DOBAWLENIE K 2-knf REZOLXWENTY L@BOJ PARY DIZ_@NKTOW NE MENQET FUNKCI@, REALIZUEMU@ 2-knf. bUDEMPROSMATRIWATX WSE PARY DIZ_@NKTOW TEKU]EJ 2-knf I STROITX IHREZOLXWENTY. eSLI OKAVETSQ, ^TO NEKOTORAQ REZOLXWENTA OTSUTSTWUET WTEKU]EJ 2-knf, TO DOBAWIM EE I NA^NEM PROSMOTR SNA^ALA. tAK BUDEMDELATX DO TEH POR, POKA NE OKAVETSQ, ^TO WSE REZOLXWENTY TEKU]EJ2-knf UVE SODERVATSQ W NEJ.eSLI PRI \TOM BUDET POROVDENA REZOLXWENTA 0, TO WYDAEM OTWET: \iSHODNAQ 2-knf NEWYPOLNIMA", INA^EWYDAEM OTWET: \iSHODNAQ 2-knf WYPOLNIMA".lEMMA.
aLGORITM OBQZATELXNO OSTANOWITSQ I RABOTAET POLINOMIALXNOE WREMQdOKAZATELXSTWO eSLI DLINA ISHODNOJ 2-knf RAWNA n, TO W NEJNE BOLEE n PEREMENNYH, IZ KOTORYH MOVNO POSTROITX NE BOLEE (n + 1)2DIZ_@NKTOW S ODNOJ ILI DWUMQ PEREMENNYMI. pO\TOMU POISK NOWYHREZOLXWENT BUDET POWTORQTXSQ NE BOLEE (n + 1)2 RAZ, PRI \TOM ^ISLO:2-(-2-)...-..56PROSMATRIWAEMYH PAR DIZ_@NKTOW NE PREWOSHODIT (n + 1)4. oTS@DASLEDUET UTWERVDENIE LEMMY.lEMMA. aLGORITM PRAWILXNO RE[AET ZADA^U wypdOKAZATELXSTWO 1) pUSTX K = D1D2 : : : Ds| ISHODNAQ 2-knfI PUSTX W KONE^NOJ knf K 0 ESTX SOMNOVITELX 0. pO LEMME K = K 0 I,SLEDOWATELXNO, K 0, TO ESTX K NEWYPOLNIMA.
2) pUSTX W KONE^NOJ2-knf K 0 NET 0. pO POSTROENI@ K 0 ZAMKNUTA OTNOSITELXNO WZQTIQREZOLXWENT, TO ESTX REZOLXWENTA L@BYH DWUH DIZ_@NKTOW IZ K 0 SNOWASODERVITSQ W K 0 . dOKAVEM, ^TO L@BAQ 2-knf S TAKIM SWOJSTWOM WYPOLNIMA. dOKAZATELXSTWO PROWEDEM INDUKCIEJ PO ^ISLU PEREMENNYH nW 2-knf K 0 .bAZIS INDUKCII n = 1.
tOGDA K 0 = xi ILI K 0 = x0i . w L@BOMSLU^AE K 0 WYPOLNIMA.iNDUKTIWNYJ PEREHOD pUSTX UTWERVDENIE WERNO DLQ 2-knf Sn < m PEREMENNYMI I PUSTX W K 0 IMEETSQ m PEREMENNYH x1; x2; : : : ; xm .tOGDAK 0 = (xm _ t1)(xm _ t2) : : : (xm _ tk )(xm _ t01)(xm _ t02) : : :: : : (xm _ t0l ) C1 C2 : : : Cr ; (19)GDE ti ; t0j | LITERALY, LIBO 0, I C1 C2 : : : Cr | 2-knf S PEREMENNYMIx1; x2; : : : ; xm;1 , ZAMKNUTAQ OTNOSITELXNO WZQTIQ REZOLXWENT. pO PREDPOLOVENI@ INDUKCII SU]ESTWUET NABOR ~ = (1; : : : ; m;1 ), NA KOTOROMC1 C2 : : : Cr RAWNO 1. eSLI BY SU]ESTWOWALI ti I t0j TAKIE, ^TO ti(~) = 0I t0j (~) = 0, TO BYLO BY I ti (~) _ t0j (~) = 0. nO ti _ t0j | REZOLXWENTADIZ_@NKTOW xm _ ti I xm _ t0j .
tAK KAK 2-knf K 0 ZAMKNUTA OTNOSITELXNOWZQTIQ REWOLXWENT, TO ti _ t0j SODERVITSQ SREDI C1; C2; : : : ; Cr . nO \TOPROTIWORE^IT TOMU, ^TO Cv (~) = 1 PRI WSEH v. sLEDOWATELXNO, LIBO WSEti(~) = 1, LIBO WSE t0j (~) = 1. w PERWOM SLU^AE K 0 WYPOLNIMA NA NABORE(~; 0), WO WTOROM | NA NABORE (~; 1):tEOREMA POLNOSTX@ DOKAZANA.2-.:.57.tEOREMA. zADA^A klika QWLQETSQ NP POLNOJ-.dOKAZATELXSTWO pOKAVEM, ^TO ZADA^A wyp POLINOMIALXNO SWODITSQ K ZADA^E klika.
dLQ \TOGO KAVDOMU SLOWU a W ALFAWITE QZYKAwyp SOPOSTAWIM PARU '(a) = (G; k), GDE G | NEKOTORYJ GRAF I k |NATURALXNOE ^ISLO, TAK, ^TOBY W G SU]ESTWOWALA KLIKA S k WER[INAMITOGDA I TOLXKO TOGDA, KOGDA a | WYPOLNIMAQ knf. eSLI a | NE knf,TO POLOVIM '(a) = (G2; 2), GDE G2 | GRAF S 2 WER[INAMI I BEZ REBER(O^EWIDNO, W G2 NET KLIKI S 2 WER[INAMI). pUSTX TEPERX a | knf Ia = D1 D2 : : : Ds, GDE Di = ti;1 _ ti;2 _ : : : _ ti;mi | DIZ_@NKTY.
pOSTROIMGRAF '(a) = Ga = (V; E ) S MNOVESTWOM WER[IN V I MNOVESTWOM REBERE SLEDU@]IM OBRAZOM. kAVDOMU LITERALU ti;j IZ a SOPOSTAWIM WER[INUvi;j I BUDEM S^ITATX, ^TO(vi1;j1 ; vi2;j2 ) 2 E () (i1 6= i2) I (ti2;j2 6= ti1;j1 ):pOLOVIM k = s, GDE s | ^ISLO DIZ_@NKTOW W a.lEMMA. w Ga ESTX KLIKA S s WER[INAMI TOGDA I TOLXKO TOGDAKOGDA knf a WYPOLNIMAdOKAZATELXSTWO pUSTX knf a PRINIMAET ZNA^ENIE 1 NA NABORE~. tOGDA Di(~) = 1 DLQ WSEH i. sLEDOWATELXNO, DLQ KAVDOGO i SU]ESTWUET ji TAKOE, ^TO ti;ji = 1. tOGDA SREDI t1;j1 ; t2;j2 ; : : : ; ts;js NET PROTIWOPOLOVNYH LITERALOW.
pO\TOMU L@BYE WER[INY IZ v1;j1 ; v2;j2 ; : : : ; vs;jsSOEDINQ@TSQ W Ga REBROM, TO ESTX OBRAZU@T KLIKU S s WER[INAMI.oBRATNO, PUSTX W GRAFE Ga ESTX KLIKA S s WER[INAMIvi1;j1 ; vi2 ;j2 ; : : : ; vis;js . tOGDA i1; i2; : : : ; is WSE RAZLI^NY, TO ESTX LITERALYIZ SEMEJSTWA M = fti1;j1 ; ti2;j2 ; : : : ; tis ;js g WHODQT PO ODNOMU W KAVDYJDIZ_@NKT knf a, PRI^EM SREDI \TIH LITERALOW NET PROTIWOPOLOVNYH.pUSTX x1; x2 : : : ; xn | WSE PEREMENNYE IZ a. dLQ KAVDOGO k POLOVIMxk = 1, ESLI LITERAL xk WSTRE^AETSQ W M , xk = 0, ESLI xk WSTRE^AETSQW M , I xk | L@BOE, ESLI NI xk , NI xk NET W M .
tOGDA NA POSTROENNOMNABORE ~ WSE LITERALY IZ M OBRA]A@TSQ W 1 I, SLEDOWATELXNO, WSEDIZ_@NKTY I WSQ knf a PRINIMA@T ZNA^ENIE 1, TO ESTX knf aWYPOLNIMA. lEMMA DOKAZANA.tAKIM OBRAZOM PEREHOD a ! '(a) QWLQETSQ SWEDENIEM ZADA^I wypK ZADA^E klika. rASPOZNATX, QWLQETSQ LI a knf, I POSTROITX POa GRAF Ga I ^ISLO k MOVNO ZA POLINOMIALXNOE WREMQ. pO\TOMU \TOPOLINOMIALXNOE SWEDENIE. tAK KAK ZADA^A wyp NP -POLNA I klika 2NP , TO PO TEOREME POLU^AEM, ^TO I ZADA^A klika NP -POLNA.zADA^A O NEZAWISIMOM MNOVESTWE WER[IN (nm).wHOD PARA (G; k), GDE G | GRAF, k | NATURALXNOE ^ISLO..,..:58wOPROS SU]ESTWU@T LI W G k WER[IN, OBRAZU@]IH NEZAWISIMOEMNOVESTWO, TO ESTX MNOVESTWO, W KOTOROM NIKAKIE WER[INY NE SOEDINENY REBROM W G?lEMMA.
HM 2 NPdOKAZATELXSTWO sERTIFIKATOM QWLQETSQ SAMO NEZAWISIMOE PODMNOVESTWO M S k WER[INAMI (ESLI TAKOE ESTX). pROWERITX, ^TO MSODERVIT ROWNO k WER[IN I QWLQETSQ NEZAWISIMYM, MOVNO ZA POLINOMIALXNOE WREMQ.zADA^A O WER[INNOM POKRYTII (wp).wHOD PARA (G; k), GDE G | GRAF, k | NATURALXNOE ^ISLO.wOPROS SU]ESTWUET LI W G MNOVESTWO M IZ k WER[IN, OBRAZU@]IH WER[INNOE POKRYTIE, TO ESTX TAKOE, ^TO L@BOE REBRO IZ G IMEETHOTQ BY ODIN KONEC W M ?lEMMA.
wp 2 NPdOKAZATELXSTWO sERTIFIKATOM QWLQETSQ SAMO WER[INNOE POKRYTIE M S k WER[INAMI (ESLI TAKOE ESTX). pROWERITX, ^TO M SODERVIT ROWNO k WER[IN I QWLQETSQ WER[INNYM POKRYTIEM, MOVNO ZAPOLINOMIALXNOE WREMQ.tEOREMA. zADA^I nm I wp NP POLNY k), GDEdOKAZATELXSTWO sOPOSTAWIM PARE (G; k) PARU (G;G |GRAF, QWLQ@]IJSQ DOPOLNENIEM K G (TO ESTX W G TO VE MNOVESTWOWER[IN V , ^TO I W G, I DWE WER[INY SOEDINQ@TSQ REBROM W G TOGDAI TOLXKO TOGDA, KOGDA ONI NE SOEDINQ@TSQ REBROM W G). pRI \TOM PODMNOVESTWO M V QWLQETSQ KLIKOJ S k WER[INAMI W G TOGDA I TOLXKOTOGDA, KOGDA M QWLQETSQ NEZAWISIMYM MNOVESTWOM S k WER[INAMIW G . pOLU^AEM SWEDENIE (O^EWIDNO, POLINOMIALXNOE) ZADA^I klikaK ZADA^E nm.
tAK KAK ZADA^A klika NP -POLNA I HM 2 NP , TOZADA^A nm NP -POLNAQ. sOPOSTAWIM PARE (G; k) PARU (G; n ; k), GDEn = jV j|^ISLO WER[IN W GRAFE G. pRI \TOM PODMNOVESTWO M VQWLQETSQ NEZAWISIMYM MNOVESTWOM S k WER[INAMI W G TOGDA I TOLXKOTOGDA, KOGDA V n M QWLQETSQ WER[INNYM POKRYTIEM S n ; k WER[INAMIW G. pOLU^AEM POLINOMIALXNOE SWEDENIE ZADA^I nm K ZADA^E wp.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
