Алексеев - Сложность алгоритмов (1123759), страница 11
Текст из файла (страница 11)
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. tAKKAK ZADA^A nm NP -POLNAQ I wp 2 NP , TO I ZADA^A wp NP -POLNAQ.oPREDELENIE. cIKL W GRAFE, PROHODQ]IJ ^EREZ KAVDU@ WER[INU ROWNO 1 RAZ, NAZYWAETSQ GAMILXTONOWYM. gAMILXTONOWOJ CEPX@ NAZYWAETSQ NEZAMKNUTAQ CEPX, PROHODQ]AQ ^EREZ KAVDU@ WER[INU ROWNO1 RAZ.zADA^A O GAMILXTONOWOM CIKLE (gc).wHOD PROIZWOLXNYJ GRAF G.:..::..-.:59.wOPROS ESTX LI W G GAMILXTONOW CIKL?lEMMA. gc 2 NPdOKAZATELXSTWO dLQ DANNOGO GRAFA G S n WER[INAMI SERTIFIKATOM QWLQETSQ POSLEDOWATELXNOSTX WER[IN (v1; v2; : : : ; vn). aLGORITMPROWERKI SERTIFIKATA DOLVEN UBEDITXSQ, ^TO W \TOM SPISKE STOLXKOVE WER[IN, SKOLXKO W GRAFE G, ^TO WSE ONI RAZLI^NY I ^TO DLQ WSEHj = 1; 2; : : : ; n ; 1 W GRAFE G ESTX REBRO (vj ; vj+1 ), A TAKVE ESTX REBRO(vn; v1).
wSE \TO MOVNO WYPOLNITX ZA POLINOMIALXNOE WREMQ.tEOREMA. zADA^A gc NP POLNAdOKAZATELXSTWO pOSTROIM POLINOMIALXNOE SWEDENIE ZADA^I3-wyp K ZADA^E gc. rASSMOTRIM 2 WSPOMOGATELXNYH GRAFA: -GRAFI -GRAF, IZOBRAVENNYE NA RIS. pUSTX -GRAF QWLQETSQ PODGRAFOMNEKOTOROGO GRAFA G, PRI^EM S DRUGIMI WER[INAMI GRAFA MOGUT SOEDINQTXSQ TOLXKO WER[INY A1; A2; B1; B2 , I PUSTX W G SU]ESTWUETGAMILXTONOW CIKL. nETRUDNO PROWERITX, ^TO ESLI \TOT CIKL WHODITWNUTRX -GRAFA, TO ON OBQZAN SRAZU OBOJTI WSE WNUTRENNIE WER[INY-GRAFA.
pRI \TOM, ESLI ON WHODIT ^EREZ WER[INU A1, TO WYHODITOBQZATELXNO ^EREZ B1 I NAOBOROT. aNALOGI^NO, ESLI ON WHODIT ^EREZA2, TO WYHODIT ^EREZ B2 I NAOBOROT. pO\TOMU USLOWNO MOVNO S^ITATX,^TO -GRAF IMEET WSEGO 2 REBRA A1B1 I A2B2 I TREBUETSQ, ^TOBY CIKLPROHODIL ROWNO PO ODNOMU IZ NIH.pUSTX -GRAF (RIS.) QWLQETSQ PODGRAFOM NEKOTOROGO GRAFA G,PRI^EM S DRUGIMI WER[INAMI GRAFA G MOGUT SOEDINQTXSQ TOLXKOWER[INY P I S .
eSLI GAMILXTONOW CIKL WHODIT W -GRAF ^EREZ P ILIS , TO ON DOLVEN SRAZU OBOJTI WSE WER[INY \TOGO -GRAFA (I WYJTI^EREZ DRUGU@ WER[INU PARY P; S ).w -GRAFE (RIS.) 3 PRAWYH REBRA PQ; QR I RS BUDEM NAZYWATXOSNOWNYMI, A WER[INY P I S | GRANI^NYMI.lEMMA. nE SU]ESTWUET GAMILXTONOWOJ CEPI W GRAFE IZ WER[INY P W WER[INU S PROHODQ]EJ PO WSEM TREM OSNOWNYM REBRAM PQ; QR; RS dLQ L@BOGO DRUGOGO PODMNOVESTWA OSNOWNYH REBERWKL@^AQ PUSTOE PODMNOVESTWO SU]ESTWUET GAMILXTONOWA CEPX IZP W S PROHODQ]AQ W TO^NOSTI PO \TOMU PODMNOVESTWU OSNOWNYHREBERpERWAQ ^ASTX \TOJ LEMMY O^EWIDNA, DLQ DOKAZATELXSTWA WTOROJ^ASTI DOSTATO^NO RASSMOTRETX WSE WOZMOVNYE SLU^AI I W KAVDOM POSTROITX SOOTWETSTWU@]U@ GAMILXTONOWU CEPX (POSTROJTE).pUSTX A | ALFAWIT ZADA^I 3-wyp.
kAVDOMU SLOWU a 2 A MYSOPOSTAWIM GRAF G TAK, ^TOBY W G SU]ESTWOWAL GAMILXTONOW CIKL:..-..-,-.(-),.60TOGDA I TOLXKO TOGDA, KOGDA a | WYPOLNIMAQ 3-knf. eSLI a 2 A I a| NE 3-knf, TO SOPOSTAWIM a GRAF G S DWUMQ WER[INAMI I 1 REBROM.o^EWIDNO, W NEM NET GAMILXTONOWA CIKLA. pUSTX TEPERX a = K = D1 D2 : : : Ds | PROIZWOLXNAQ 3-knf S PEREMENNYMI x1; x2; : : : ; xn. pUSTXH1; H2 ; : : : ; Hs | -GRAFY S GRANI^NYMI WER[INAMI Pj ; Sj . sOEDINIMREBRAMI WER[INY Sj I Pj+1 DLQ j = 1; 2; : : : ; s ; 1. pOLU^ENNYJ GRAFOBOZNA^IM G1. ~EREZ G2 OBOZNA^IM GRAF S WER[INAMI C0; C1; : : : ; Cn,W KOTOROM DLQ KAVDOGO i ESTX 2 REBRA (Ci;1; Ci ) I NET DRUGIH REBER.wER[INU P1 GRAFA G1 SOEDINIM REBROM S C0, A Ss SOEDINIM REBROM SCn.
iZ DWUH REBER (Ci;1; Ci ) ODNO SOPOSTAWIM PEREMENNOJ xi, A DRUGOE| xi . pERWOE OBOZNA^IM e1i , WTOROE e0i . w KAVDOM PODGRAFE Hj OSNOWNYEREBRA Pj Qj ; Qj Rj ; Rj Sj SOPOSTAWIM LITERALAM tj;1; tj;2; tj;3 DIZ_@NKTADj . pUSTX LITERAL xi WSTRE^AETSQ W k DIZ_@NKTAH Dj I W PODGRAFAHHj LITERALU xi SOOTWETSTWU@T k REBER e1; e2; : : : ; ek . mEVDU REBROMe1i = (Ci;1; Ci ), SOOTWETSTWU@]IM xi, I KAVDYM IZ REBER e1; e2; : : : ; ekWSTAWIM SOEDINITELXNYE REBRA TAK, ^TOBY OBRAZOWALOSX k -GRAFOW.tAK POSTUPIM DLQ WSEH xi . aNALOGI^NO POSTUPIM DLQ WSEH xi S ZAMENOJe1i NA e0i .
pOLU^ENNYJ GRAF OBOZNA^IM Gk .lEMMA. w Gk ESTX GAMILXTONOW CIKL TOGDA I TOLXKO TOGDAKOGDA knf K WYPOLNIMAdOKAZATELXSTWO pUSTX W Gk SU]ESTWUET GAMILXTONOW CIKL W .pO SWOJSTWAM -GRAFA (SM.WY[E) MOVNO USLOWNO S^ITATX, ^TO GAMILXTONOW CIKL PROHODIT ROWNO PO ODNOMU IZ REBER A1B1 ILI A2B2 -GRAFA.sLEDOWATELXNO, MOVNO S^ITATX, ^TO CIKL W SNA^ALA PROHODIT POWSEM WER[INAM PODGRAFA G1, POTOM PO WSEM WER[INAM PODGRAFA G2,PRI \TOM WYPOLNQETSQ TREBUEMOE SWOJSTWO DLQ KAVDOGO -GRAFA. dLQKAVDOJ PARY REBER e0i ; e1i W G2 CIKL W , O^EWIDNO, DOLVEN PROHODITXROWNO PO ODNOMU IZ \TIH REBER.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
