В.Б. Алексеев - Электронный коспект лекций, страница 12

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. dLQ KAVDOGO i POLOVIM xi = 0, ESLI WPROHODIT PO e0i , I xi = 1, ESLI W PROHODIT PO e1i . pOLU^ENNYJ NABOROBOZNA^IM ~ = (1; : : : ; n ). rASSMOTRIM ODIN IZ PODGRAFOW Hj W G1. pOLEMME GAMILXTONOW CIKL W NE PROHODIT PO KRAJNEJ MERE PO ODNOMU IZOSNOWNYH REBER PODGRAFA Hj .

pUSTX \TOMU REBRU SOSPOSTAWLEN LITERALt S PEREMENNOJ xi. eSLI t = xi , TO \TO REBRO SOEDINENO -GRAFOM S e1i ,ESLI t = xi, TO S e0i . tAK KAK PO DANNOMU REBRU CIKL W NE PROHODIT,ON DOLVEN PROHODITX PO e1i , ESLI t = xi , I PO e0i , ESLI t = xi . iZWYBORA i POLU^AEM, ^TO W L@BOM SLU^AE t(~) = 1 I, SLEDOWATELXNO,Dj (~) = 1. pOSKOLXKU \TO WERNO DLQ WSEH j , TO K (~) = 1, TO ESTX knfK WYPOLNIMA.oBRATNO, PUSTX knf K WYPOLNIMA I K (~) = 1, GDE ~ =,..61(1; : : : ; n ). pROWEDEM CIKL W PO PODGRAFU G2 TAK, ^TOBY DLQ KAVDOGOi = 1; 2; : : : ; n ON PROHODIL PO e0i , ESLI i = 0, I PO e1i , ESLI i = 1. tOGDAPO SWOJSTWAM -GRAFOW CIKL W NE MOVET PROHODITX PO OSNOWNOMU REBRUPODGRAFA G1, KOTOROMU PRIPISAN LITERAL t, TAKOJ, ^TO t(~) = 1, IOBQZAN PROHODITX PO OSNOWNOMU REBRU, ESLI EMU PRIPISAN LITERAL t,TAKOJ, ^TO t(~) = 0.

tAK KAK Dj (~) = 1 DLQ WSEH j , TO W KAVDOM PODGRAFEHj SU]ESTWUET HOTQ BY ODNO REBRO, TAKOE, ^TO DLQ SOOTWETSTWU@]EGOEMU LITERALA tj WYPOLNQETSQ tj (~) = 1. sLEDOWATELXNO W KAVDOMPODGRAFE Hj SU]ESTWUET ODNO, DWA ILI TRI OSNOWNYH REBRA, TAKIH,^TO CIKL W NE DOLVEN PO NIM PROHODITX, I DOLVEN PROHODITX POOSTALXNYM OSNOWNYM REBRAM. pO LEMME W KAVDOM Hj MOVNO POSTROITXGAMILXTONOWU CEPX, UDOWLETWORQ@]U@ \TIM TREBOWANIQM, I W CELOM WGRAFE Gk MOVNO POSTROITX GAMILXTONOW CIKL. lEMMA DOKAZANA.pROWERITX, QWLQETSQ LI SLOWO a 2 A 3-knf, I POSTROITX GRAFGk , ESLI a = K | \TO 3-knf, MOVNO ZA POLINOMIALXNOE (OT DLINY a)WREMQ.

pO\TOMU MY POLU^AEM POLINOMIALXNOE SWEDENIE ZADA^I 3-wypK ZADA^E gc. tAK KAK ZADA^A 3-wyp NP -POLNA I gc 2 NP , TO I ZADA^Agc NP -POLNA.62zADA^I OPTIMIZACIIw PRAKTI^ESKIH PRILOVENIQH ^ASTO WOZNIKA@T ZADA^I OPTIMIZACII, KOTORYE IME@T SLEDU@]U@ STRUKTURU. kAVDOMU WHODU x SOPOSTAWLQETSQ NEKOTOROE MNOVESTWO Yx DOPUSTIMYH RE[ENIJ. zADANFUNKCIONAL F : Yx ! R, GDE R | MNOVESTWO DEJSTWITELXNYH ^ISEL.tREBUETSQ NAJTI miny2Yx F (y), ILI maxy2Yx F (y), ILI TO DOPUSTIMOERE[ENIE y0, NA KOTOROM DOSTIGAETSQ OPTIMALXNOE ZNA^ENIE FUNKCIONALA. eSLI FUNKCIONAL F WY^ISLQETSQ BYSTRO, TO NAJDQ OPTIMALXNOE DOPUSTIMOE RE[ENIE, MY MOVEM LEGKO POLU^ITX I OPTIMALXNOEZNA^ENIE FUNKCIONALA FOPT. oBRATNOE, WOOB]E GOWORQ, NE QSNO: MOVETSU]ESTWOWATX BYSTRYJ ALGORITM, KOTORYJ NAHODIT FOPT, NE NAHODQOPTIMALXNOGO RE[ENIQ.s KAVDOJ ZADA^EJ OPTIMIZACII MOVNO SWQZATX ZADA^U RASPOZNAWANIQ.

pRI \TOM NA WHOD KROME x PODAETSQ ^ISLO k I SPRA[IWAETSQ,WERNO LI, ^TO FOPT 6 k (ILI FOPT > k).nA PRAKTIKE DLQ RE[ENIQ ZADA^ OPTIMIZACII ^ASTO ISPOLXZU@TSQALGORITMY, NAZYWAEMYE VADNYMI ILI GRADIENTNYMI. w TAKIH ALGORITMAH DOPUSTIMOE RE[ENIE STROITSQ POSTEPENNO PO [AGAM, PRI^EMNA KAVDOM [AGE DELAETSQ WYBOR, OPTIMALXNYJ DLQ DANNOGO [AGA. kAKMY UWIDIM NIVE, TAKOJ PODHOD NE WSEGDA PRIWODIT K OPTIMALXNOMU RE[ENI@ W CELOM. oDNAKO DLQ SLEDU@]EJ ZADA^I ON WSEGDA DAET OPTIMALXNOE RE[ENIE. nAPOMNIM, ^TO DEREWOM NAZYWAETSQ L@BOJNEORIENTIROWANNYJ SWQZNYJ GRAF BEZ CIKLOW.

pODGRAF G1 GRAFA GNAZYWAETSQ OSTOWNYM, ESLI G1 SODERVIT WSE WER[INY GRAFA G. ~EREZKn OBOZNA^AETSQ POLNYJ GRAF NA n WER[INAH, TO ESTX GRAF, W KOTOROMKAVDAQ PARA WER[IN SOEDINENA REBROM.zADA^A O KRAT^AJ[EM OSTOWNOM DEREWE.wHOD NEORIENTIROWANNYJ POLNYJ GRAF Kn, W KOTOROM DLQ L@BOGOREBRA e ZADAN WES w(e) > 0.tREBUETSQ WYDELITX W Kn OSTOWNOE DEREWO S MINIMALXNOJ SUMMOJ WESOW REBER.zAME^ANIE. nA PRAKTIKE \TO OZNA^AET TREBOWANIE POSTROITXSETX MINIMALXNOJ STOIMOSTI, SWQZYWA@]U@ n DANNYH OB_EKTOW.nAPOMNIM NEKOTORYE FAKTY IZ TEORII GRAFOW.uTWERVDENIE 1.

eSLI W GRAFE S n WER[INAMI ^ISLO REBER q <n ; 1 TO GRAF NE SWQZNYJuTWERVDENIE 2. eSLI W GRAFE G NET CIKLOW I q = n ; 1q; n ^ISLO REBER I WER[IN TO G DEREWO::,(|.),|63.uTWERVDENIE 3. w L@BOM DEREWE S n WER[INAMI ^ISLO REBERq = n;1uTWERVDENIE 4. eSLI K DEREWU DOBAWITX NOWOE REBRO NA TEH.VE WER[INAH TO OBRAZUETSQ ROWNO CIKLrASSMOTRIM SLEDU@]IJ ALGORITM DLQ ZADA^I O KRAT^AJ[EM OSTOWNOM DEREWE.1.

wZQTX L@BOE REBRO e1 MINIMALXNOGO WESA.2. rEKURSIWNYJ [AG: PUSTX UVE WYBRANY REBRA e1; e2; : : : ; em . eSLIm = n ; 1, TO OSTANOWITXSQ. iNA^E, SREDI WSEH REBER, NE OBRAZU@]IHCIKLOW S e1; e2 ; : : : ; em , WZQTX REBRO em+1 MINIMALXNOGO WESA I POWTORITXREKURSIWNYJ [AG.aLGORITM DELAET MENX[E, ^EM n ITERACIJ I NA KAVDOJ PROSMATRIWAET MENEE, ^EM n2 REBER.