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

pRI \TOM, ESLI IZ REBER e1; e2; : : : ; emSFORMIROWATX SWQZNYE KOMPONENTY, TO TOT FAKT, ^TO em+1 NE OBRAZUETS NIMI CIKLOW, \KWIWALENTEN TOMU, ^TO KONCY REBRA em+1 NE LEVATW ODNOJ SWQZNOJ KOMPONENTE. |TO SWOJSTWO LEGKO PROWERQETSQ. tAKIMOBRAZOM, ALGORITM MOVET BYTX REALIZOWAN S POLINOMIALXNYM OT n^ISLOM OPERACIJ, WKL@^A@]IH POISK INFORMACII I SRAWNENIE WESOW.tEOREMA.

oPISANNYJ ALGORITM KORREKTNO STROIT MINIMALXNOE OSTOWNOE DEREWOdOKAZATELXSTWO 1) dOKAVEM, ^TO ESLI m < n ; 1, TO SU]ESTWU@TREBRA, NE OBRAZU@]IE CIKLOW S e1; e2; : : : ; em . eSLI m < n ; 1, TOPODGRAF, SOSTOQ]IJ IZ WSEH WER[IN I REBER e1; e2; : : : ; em , NE SWQZNYJ(PO UTW. 1). eSLI WZQTX L@BOE REBRO, SOEDINQ@]EE DWE WER[INY IZRAZNYH KOMPONENT \TOGO PODGRAFA, TO CIKLY NE OBRAZU@TSQ. tAKIMOBRAZOM, ALGORITM PRORABOTAET DO m = n ; 1.2) pRI OSTANOWKE m = n ; 1 I REBRA e1; e2; : : : ; em NE OBRAZU@TCIKLOW. tOGDA (PO UTW.

2) ONI OBRAZU@T OSTOWNOE DEREWO.3) pUSTX ALGORITM STROIT OSTOWNOE DEREWO D. dOKAVEM, ^TO D |MINIMALXNOE OSTOWNOE DEREWO. rASSMOTRIM WSE MINIMALXNYE OSTOWNYEDEREWXQ, I PUSTX T | MINIMALXNOE OSTOWNOE DEREWO, IME@]EE S DNAIBOLX[EE ^ISLO OB]IH REBER. dOKAVEM (OT PROTIWNOGO), ^TO D = T .dOPUSTIM, ^TO T 6= D. tAK KAK I W T I W D n ; 1 REBRO (UTW. 3), TOW D ESTX REBRA, NE WHODQ]IE W T . pUSTX W ALGORITME REBRA DEREWAD POQWLQLISX W PORQDKE: e1; e2 ; : : : ; en;1 I PUSTX REBRA e1; e2; : : : ; ekPRINADLEVAT DEREWU T , A ek+1 2= T .

rASSMOTRIM GRAF H = T [fek+1g. wH IMEETSQ EDINSTWENNYJ CIKL C (UTW.4), SODERVA]IJ ek+1. tAK KAK DNE SODERVIT CIKLOW, TO W C ESTX HOTQ BY ODNO REBRO e TAKOE, ^TO e 2= D.pRI \TOM e 2 T . rASSMOTRIM H1 = H n feg. gRAF H1 | SWQZNYJ I BEZ,1.-..64CIKLOW, TO ESTX H1| OSTOWNOE DEREWO. pUSTX w(H1) I w(T ) | SUMMYWESOW REBER W H1 I T1. tAK KAK T | MINIMALXNOE OSTOWNOE DEREWO, TOw(H1) > w(T ) Iw(H1) = w(T ) + w(ek+1) ; w(e) > w(T ):oTS@DA w(e) 6 w(ek+1). pOSKOLXKU e 2 T I e1; e2; : : : ; ek PRINADLEVAT DEREWU T , TO e NE OBRAZUET CIKLOW S e1; e2 ; : : : ; ek . eSLI BY BYLOw(e) < w(ek+1), TO NA k + 1-M [AGE ALGORITMA NE MOGLO BY WYBIRATXSQREBRO ek+1 .

zNA^IT w(e) = w(ek+1) I w(H1) = w(T ). pOLU^AEM, ^TO H1| TAKVE MINIMALXNOE OSTOWNOE DEREWO, NO IME@]EE S D NA 1 OB]EEREBRO BOLX[E, ^EM T S D. |TO PROTIWORE^IT WYBORU DEREWA T . iZPOLU^ENNOGO PROTIWORE^IQ SLEDUET, ^TO DOLVNO BYTX D = T , TO ESTXD | MINIMALXNOE OSTOWNOE DEREWO. tEOREMA DOKAZANA.pRIBLIVENNYE ALGORITMY.zADA^A O MINIMALXNOM WER[INNOM POKRYTII (mwp).bUDEM GOWORITX, ^TO WER[INA v POKRYWAET REBRO e, ESLI e QWLQETSQ ODNIM IZ KONCOW REBRA e. PODMNOVESTWO A V WER[IN GRAFAG = (V; E ) NAZYWAETSQ WER[INNYM POKRYTIEM, ESLI WER[INY IZ APOKRYWA@T WSE REBRA IZ E .wHOD NEORIENTIROWANNYJ GRAF G = (V; E ).tREBUETSQ NAJTI WER[INNOE POKRYTIE (wp) MINIMALXNOJ MO]NOSTI."vADNYJ" ALGORITM DLQ mwp.nA KAVDOM [AGE WYBIRAETSQ L@BAQ WER[INA, POKRYWA@]AQ NAIBOLX[EE ^ISLO E]E NE POKRYTYH REBER. aLGORITM OSTANAWLIWAETSQ,KOGDA WSE REBRA POKRYTY.lEGKO POKAZATX, ^TO "VADNYJ" ALGORITM DLQ mwp IMEET POLINOMIALXNU@ SLOVNOSTX.tEOREMA. dLQ VADNOGO ALGORITMA DLQ ZADA^I mwp DLQ L@BOGO NATURALXNOGO n SU]ESTWUET GRAF Gn TAKOJ ^TO PRI WHODE GnWYPOLNQETSQ NERAWENSTWOFALG > FOPT(ln n ; ln2 ; 1):::""-,:dOKAZATELXSTWO wKL@^IM W GRAF Gn SNA^ALA WER[INYu1; u2; : : : ; un , MEVDU KOTORYMI NE BUDET REBER.

dALEE WYDELIM IZ WER[IN u1; u2 ; : : : ; un [ n2 ] NEPERESEKA@]IHSQ PAR (ODNA WER[INA MOVET NE.65U^ASTWOWATX W PARAH) I KAVDU@ PARU SOEDINIM S NOWOJ WER[INOJ, PRI\TOM POLU^IM NOWYE WER[INY v1; v2; : : : ; v[ n2 ] STEPENI 2. zATEM WYDELIMIZ WER[IN u1 ; u2; : : : ; un [ n3 ] NEPERESEKA@]IHSQ TROEK I KAVDU@ TROJKUSOEDINIM S NOWOJ WER[INOJ (STEPENI 3). dALEE ANALOGI^NO WYDELIMNEPERESEKA@]IESQ ^ETWERKI, PQTERKI WER[IN I T.D. nA POSLEDNEM\TAPE WYDELIM IZ u1 ; u2; : : : ; un GRUPPU IZ n ; 1 WER[IN I SOEDINIMEE S NOWOJ WER[INOJ (STEPENI n ; 1).

zAMETIM, ^TO POSLE DOBAWLENIQNOWYH WER[IN STEPENI k WER[INY u1; u2 ; : : : ; un IME@T STEPENX NE BOLEEk ; 1, W ^ASTNOSTI, W ZAKL@^ITELXNOM GRAFE Gn ONI IME@T STEPENX NEBOLEE n ; 2. pO\TOMU "VADNYJ" ALGORITM, PRIMENENNYJ K Gn, SNA^ALAWYBERET DOBAWLENNU@ WER[INU STEPENI n ; 1, ZATEM (POSLE UDALENIQ\TOJ WER[INY I POKRYWAEMYH E@ REBER) WYBERET WSE DOBAWLENNYEWER[INY STEPENI n ; 2, ZATEM WSE DOBAWLENNYE WER[INY STEPENI n ; 3 IT.D.

nA POSLEDNEM \TAPE ON WYBERET WSE DOBAWLENNYE WER[INY STEPENI2. tAKIM OBRAZOMih inn >FALG = 2 + n3 + : : : + n ;1nnn> 2 ;1 + 3 ; 1 +::: + n; 1 ; 1 =111= n + +::: +2 3n ; 1 ; (n ; 2) >Zn> n x1 dx ; n = n(ln n ; ln 2) ; n (20)h2s DRUGOJ STORONY MNOVESTWO fu1; u2 ; : : : ; un g QWLQETSQ WER[INNYM POKRYTIEM W Gn. pO\TOMU FOPT 6 n IFALG = n(ln n ; ln 2 ; 1) > FOPT(ln n ; ln 2 ; 1):oPREDELENIE. pUSTX DANA ZADA^A OPTIMIZACII S FUNKCIONALOMF . aLGORITM DLQ \TOJ ZADA^I NAZYWAETSQ "- PRIBLIVENNYM, ESLI WSEGDA FALG ; FOPT < ";FOPTGDE FALG I FOPT |ZNA^ENIE FUNKCIONALA, WYDAWAEMOE ALGORITMOM, IOPTIMALXNOE ZNA^ENIE.eSLI DANA ZADA^A MINIMIZACII I FOPT > 0, TO UKAZANNOE NERAWENSTWO \KWIWALENTNO NERAWENSTWU:FALG 6 (1 + ")FOPT:sLEDSTWIE. vADNYJ ALGORITM DLQ mwp NE QWLQETSQ" PRIBLIVENNYM NI PRI KAKOM FIKSIROWANNOM "-.66sLEDU@]AQ TEOREMA POKAZYWAET, ^TO TEORETI^ESKI "VADNAQ"STRATEGIQ DLQ ZADA^I mwp NE QWLQETSQ HORO[EJ.tEOREMA.

dLQ ZADA^I mwp SU]ESTWUET PRIBLIVENNYJ ALGORITM S POLINOMIALXNOJ SLOVNOSTX@dOKAZATELXSTWO rASSMOTRIM SLEDU@]IJ ALGORITM. pUSTX DANGRAF G = (V; E ). bUDEM FORMIROWATX WER[INOE POKRYTIE A. wOZXMEML@BOE REBRO e1 = (v1; v2 ) I WKL@^IM v1 I v2 W A. wYBROSIM IZ GRAFA GWER[INY v1 I v2 I WSE REBRA, KOTORYE IMI POKRYWA@TSQ. w POLU^ENNOMGRAFE G1 OPQTX WOZXMEM L@BOE REBRO e2 = (v3; v4); DOBAWIM v3 I v4W A I UDALIM IZ G1 WER[IN v3 I v4 I WSE POKRYWAEMYE IMI REBRA.pROCESS ZAKON^IM, KOGDA BUDUT UDALENY WSE REBRA. lEGKO PONQTX,^TO \TOT ALGORITM MOVNO REALIZOWATX S POLINOMIALXNOJ SLOVNOSTX@.tAKVE PO POSTROENI@ O^EWIDNO, ^TO POLU^ENNOE MNOVESTWO WER[IN APOKRYWAET WSE REBRA.

pUSTX W PROCESSE ALGORITMA WYBIRALISX REBRAe1; e2; : : : ; ek . tOGDA jAj = 2k. s DRUGOJ STORONY REBRA e1; e2; : : : ; ek NEIME@T OB]IH WER[IN I, SLEDOWATELXNO, L@BOE WER[INNOE POKRYTIEDOLVNO SODERVATX NE MENEE k WER[IN (^TOBY POKRYTX e1; e2; : : : ; ek ).tAKIM OBRAZOM FOPT > k I FALG = jAj > 2FOPT. tEOREMA DOKAZANA.wOZNIKAET WOPROS, A NELXZQ LI DLQ ZADA^I mwp POSTROITX NEPRIBLIVENNYJ, A TO^NYJ ALGORITM S POLINOMIALXNOJ SLOVNOSTX@.wY[E BYLA DOKAZANA NP -POLNOTA ZADA^I O WER[INNOM POKRYTII (wp),GDE PO ZADANNOMU GRAFU G I ^ISLU k TREBUETSQ WYQSNITX, ESTX LI WGRAFE G WER[INNOE POKRYTIE MO]NOSTI NE BOLEE k.tEOREMA. eSLI DLQ ZADA^I mwp SU]ESTWUET ALGORITM S POLINOMIALXNOJ SLOVNOSTX@ TO I DLQ ZADA^I wp SU]ESTWUET ALGORITMS POLINOMIALXNOJ SLOVNOSTX@dOKAZATELXSTWO pUSTX ALGORITM H RE[AET ZADA^U mwp ZAPOLINOMIALXNOE WREMQ I PUSTX W ZADA^E wp ZADANY GRAF G I ^ISLOk.

pRIMENQEM K GRAFU G ALGORITM H I POLU^AEM m | MINIMALXNU@MO]NOSTX WER[INNOGO POKRYTIQ W G. eSLI m 6 k, TO OTWET W ZADA^Ewp "DA", INA^E OTWET "NET". pOLU^AEM POLINOMIALXNYJ ALGORITM DLQZADA^I wp.zAME^ANIE. eSLI DLQ ZADA^I wp SU]ESTWUET ALGORITM H S POLINOMIALXNOJ SLOVNOSTX@ I W GRAFE G n WER[IN, TO, PRIMENQQ ALGORITMH K PARAM (G; 0); (G; 1); : : : ; (G; n ; 1), MOVNO ZA POLINOMIALXNOE WREMQOPREDELITX MO]NOSTX MINIMALXNOGO WER[INNOGO POKRYTIQ, ODNAKO NEQSNO, KAK NAJTI SAMO MINIMALXNOE WER[INNOE POKRYTIE.oPREDELENIE. zADA^U OPTIMIZACII BUDEM NAZYWATXNP -TRUDNOJ, ESLI IZ SU]ESTWOWANIQ ALGORITMA POLINOMIALXNOJ1--..-,..67SLOVNOSTI DLQ NEE SLEDUET SU]ESTWOWANIE ALGORITMA POLINOMIALXNOJSLOVNOSTI DLQ NEKOTOROJ NP -POLNOJ ZADA^I (I,SLEDOWATELXNO, DLQWSEH ZADA^ IZ NP ).sLEDSTWIE.

zADA^A mwp QWLQETSQ NP TRUDNOJsLEDSTWIE. eSLI P =6 NP TO DLQ ZADA^I mwp NE SU]ESTWUETALGORITMA S POLINOMIALXNOJ SLOVNOSTX@-,.68.zADA^A KOMMIWOQVERAwY[E MY POLU^ILI USLOWNYJ REZULXTAT O TRUDNOSTI NAHOVDENIQTO^NOGO RE[ENIQ ZADA^I mwp. zDESX MY POKAVEM, ^TO TAKIE USLOWNYEOTRICATELXNYE REZULXTATY MOVNO POLU^ATX I DLQ NAHOVDENIQ PRIBLIVENNYH RE[ENIJ.nAPOMNIM, ^TO CIKL W GRAFE NAZYWAETSQ GAMILXTONOWYM, ESLI ONPROHODIT ^EREZ KAVDU@ WER[INU ROWNO 1 RAZ.

wY[E BYLO POKAZANO, ^TOZADA^A O SU]ESTWOWANII W GRAFE GAMILXTONOWA CIKLA (gc) QWLQETSQNP -POLNOJ.zADA^A KOMMIWOQVERA (zk).wHOD POLNYJ GRAF Kn, W KOTOROM KAVDOMU REBRU e = (vi ; vj )SOPOSTAWLEN WES d(e) = d(vi ; vj ) > 0. pRI \TOM BUDEM S^ITATX, ^TO WSEd(e)| CELYE ^ISLA I DLINA WHODA WKL@^AET W SEBQ SUMMARNU@ DLINUDWOI^NOGO PREDSTAWLENIQ WSEH d(e).tREBUETSQ NAJTI GAMILXTONOW CIKL W Kn S MINIMALXNOJ SUMMOJWESOW REBER.tEOREMA.