Дискретная математика

SQ PERE[EJKOM (MOSTOM).

sWOJSTWO 1. pRI UDALENII CIKLI^ESKOGO REBRA GRAFA G POLU- ^AETSQ GRAF G0 S TEM VE KOLI^ESTWOM KOMPONENT SWQZNOSTI, ^TO I GRAF G , A PRI UDALENII PERE[EJKA KOLI^ESTWO KOMPONENT SWQZNOSTI WOZRASTAET NA EDINICU.

sWOJSTWO 2. w SWQZNOM GRAFE S n WER[INAMI I m REBRAMI WYPOLNENO NERAWENSTWO m > n ; 1 .

dOKAZATELXSTWO. pRIMENIM METOD INDUKCII PO ^ISLU REBER m .

1.bAZA INDUKCII. eSLI m = 0 , TO n = 1 WWIDU SWQZNOSTI GRAFA I NERAWENSTWO m > n ; 1 WERNO.

2.iNDUKCIONNOE PREDPOLOVENIE. pUSTX NERAWENSTWO SPRAWEDLIWO DLQ SWQZNYH GRAFOW S ^ISLOM REBER m0 < m .

3.{AG INDUKCII. rASSMOTRIM SWQZNYJ GRAF G S m REBRAMI.

uDALIM IZ GRAFA G L@BOE REBRO g I RASSMOTRIM	2 SLU^AQ. eSLI
g { CIKLI^ESKOE REBRO, TO POLU^ITSQ SWQZNYJ GRAF	G0 , U KOTOROGO

m0	= m	;	1 I n0 = n . pO INDUKCIONNOMU PREDPOLOVENI@ IMEEM
m0	> n0	;	1 = m	;	1 > n	;	1 = m > n = m > n		;	1 .
			)				)	)
eSLI g {			PERE[EEK,	TO POLU^ATSQ DWA SWQZNYH GRAFA G0 I					G00 ,

DLQ NIH PO PREDPOLOVENI@ WYPOLNQ@TSQ NERAWENSTWA m0 > n0 ; 1 I m00 > n00 ; 1 . sLOVIM IH PO^LENNO: m0 + m00 > n0 + n00 ; 2 =) m ; 1 > n ; 2 =) m > n ; 1 . {AG INDUKCII PROWEDEN I SWOJSTWO 2 DOKAZANO.

sLEDSTWIE. eSLI GRAF SOSTOIT IZ k KOMPONENT SWQZNOSTI, TO

m > n ; k .

x6. tEOREMA |JLERA O PLOSKIH GRAFAH

oPREDELENIE 1. pLOSKIJ GRAF RAZBIWAET PLOSKOSTX NA NESKOLXKO ^ASTEJ, NAZYWAEMYH GRANQMI \TOGO GRAFA.

tEOREMA |JLERA O PLOSKIH GRAFAH. eSLI PLOSKIJ SWQZNYJ GRAF IMEET l GRANEJ, n WER[IN I m REBER, TO l + n = m + 2 .

dOKAZATELXSTWO PROWEDEM INDUKCIEJ PO ^ISLU REBER m .

1. eSLI m = 0 , TO n = 1 , l = 1 I FORMULA l + n = m+ 2 WERNA. 2. pUSTX \TA FORMULA WERNA DLQ WSEH PLOSKIH SWQZNYH GRAFOW S

^ISLOM REBER MENX[IM, ^EM m .

61

3. rASSMOTRIM PLOSKIJ SWQZNYJ GRAF G S m REBRAMI I UDALIM IZ NEGO NEKOTOROE REBRO g . eSLI g { CIKLI^ESKOE REBRO, TO POLU- ^ITSQ PLOSKIJ SWQZNYJ GRAF G0 , DLQ KOTOROGO PO INDUKCIONNOMU PREDPOLOVENI@ IMEET MESTO RAWENSTWO l0 + n0 = m0 + 2 . pOSKOLXKU l0 = l;1 , n0 = n , m0 = m;1 , TO OTS@DA SLEDUET, ^TO l+n = m+2 . eSLI REBRO g { PERE[EEK, TO POLU^ATSQ DWA PLOSKIH SWQZNYH GRAFA G0 I G00 , DLQ KOTORYH PO INDUKCIONNOMU PREDPOLOVENI@ MOVNO NAPISATX, ^TO l0+n0 = m0 +2 I l00 +n00 = m00+2 . sKLADYWAQ \TI RAWENSTWA I ZAME^AQ, ^TO l0 + l00 = l+ 1 , n0 + n00 = n , m0 + m00 = m;1 , MY SNOWA POLU^AEM RAWENSTWO l + n = m + 2 . tEOREMA DOKAZANA.

x7. sLEDSTWIQ IZ TEOREMY |JLERA O PLOSKIH GRAFAH

sLEDSTWIE 1. dLQ L@BOGO WYPUKLOGO MNOGOGRANNIKA IMEET MESTO FORMULA |JLERA l + n = m + 2 , GDE l , n I m { KOLI^ESTWO GRANEJ, WER[IN I REBER \TOGO MNOGOGRANNIKA.

dOKAZATELXSTWO. wNA^ALE WOZXMEM WNUTRI MNOGOGRANNIKA TO^- KU O I SPROECIRUEM POWERHNOSTX \TOGO MNOGOGRANNIKA IZ TO^KI O (CENTRALXNAQ PROEKCIQ) NA NEKOTORU@ SFERU S CENTROM W TO^KE O . dALEE, WYBEREM NA SFERE TO^KU N (SEWERNYJ POL@S), NE LEVA]U@ NI NA ODNOM REBRE POLU^IW[EGOSQ SFERI^ESKOGO MNOGOUGOLXNIKA, PROWEDEM ^EREZ TO^KU S (@VNYJ POL@S) PLOSKOSTX, KASATELXNU@ K SFERE I SOWER[IM CENTRALXNU@ PROEKCI@ SFERI^ESKOGO MNOGOUGOLXNIKA IZ TO^KI N NA KASATELXNU@ PLOSKOSTX. w REZULXTATE MY POLU^IM NA \TOJ PLOSKOSTI SWQZNYJ GRAF, DLQ KOTOROGO WERNA FORMULA l + n = m + 2 .

sLEDSTWIE 2. dLQ PROSTOGO PLANARNOGO SWQZNOGO GRAFA G WYPOLNENO NERAWENSTWO m 6 3n ; 6 , ESLI n > 3 .

dOKAZATELXSTWO. pOSKOLXKU G PLANAREN, TO ON REALIZUETSQ W WIDE PLOSKOGO GRAFA G0 . wSE GRANI GRAFA G0 OGRANI^ENY PO KRAJNEJ MERE TREMQ REBRAMI, TAK KAK G0 QWLQETSQ PROSTYM S KOLI- ^ESTWOM WER[IN n > 3 . oTS@DA SLEDUET, ^TO KOLI^ESTWO REBER G0

UDOWLETWORQET USLOWI@ m > 32 l . iSPOLXZUQ RAWENSTWO |JLERA, PO-

LU^AEM m + 2 = n + l 6 n + 23 m =) m 6 3n ; 6 .

pRIMER 1. gRAF K5 NE QWLQETSQ PLANARNYM, T.K. DLQ NEGO NERAWENSTWO m 6 3n ; 6 NE WYPOLNENO.

62

li + ni

2, ^TO I DOKAZYWAET SU]ESTWOWANIE WER-

deg xi > 6n =)

m > 3n . pOSLEDNEE NERAWENSTWO

sLEDSTWIE 3. w L@BOM PLOSKOM SWQZNOM PROSTOM GRAFE NAJDETSQ WER[INA, STEPENI NE PREWOSHODQ]EJ 5.

dOKAZATELXSTWO PROWEDEM OT PROTIWNOGO. pUSTX deg xi > 6 DLQ

WSEH i = 1; 2; : : : ; n . sKLADYWAQ PO^LENNO \TI NERAWENSTWA, POLU-

n

^IM, ^TO 2m = P

i=1

PROTIWORE^IT SLEDSTWI@

[INY, STEPENX KOTOROJ NE PREWOSHODIT 5.

sLEDSTWIE 4. eSLI PLOSKIJ GRAF G IMEET k KOMPONENT SWQZNOSTI, TO l + n = m + k + 1 .

dOKAZATELXSTWO. dLQ KAVDOJ KOMPONENTY SWQZNOSTI Gi WERNA FORMULA = mi + 2 . sLADYWAQ PO^LENNO \TI RAWENSTWA I U^ITYWAQ, ^TO Pni = n , Pmi = m , A Pli = l + k ; 1 , TAK KAK BESKONE^NAQ GRANX S^ITAETSQ W KAVDOJ IZ k KOMPONENT, W TO WREMQ KAK W GRAFE G TOLXKO ODIN RAZ, POLU^AEM: l+k;1+n = m+2k =) l + n = m + k + 1 .

x8. |JLEROWY GRAFY. zADA^A O KENIGSBERGSKIH MOSTAH

cEPX NAZYWAETSQ PROSTOJ, ESLI WSE EE REBRA RAZLI^NY. oPREDELENIE 1. sWQZNYJ GRAF G NAZYWAETSQ \JLEROWYM, ESLI

SU]ESTWUET PROSTAQ ZAMKNUTAQ CEPX, SODERVA]AQ WSE REBRA GRAFA G ; TAKAQ CEPX NAZYWAETSQ \JLEROWOJ.

tEOREMA OB \JLEROWOM GRAFE. sWQZNYJ GRAF QWLQETSQ \JLE-

ROWYM TOGDA I TOLXKO TOGDA, KOGDA WSE EGO WER[INY IME@T ^ETNU@ STEPENX.

dOKAZATELXSTWO. eSLI GRAF G { \JLEROW, TO PRI KAVDOM PROHOVDENII \JLEROWOJ CEPI ^EREZ DANNU@ WER[INU x U^ASTWU@T DWA REBRA, PO\TOMU deg x { ^ETNOE ^ISLO.

nAOBOROT, PUSTX G IMEET TOLXKO ^ETNYE WER[INY. iNDUKCIEJ PO ^ISLU REBER m DOKAVEM, ^TO GRAF IMEET \JLEROWU CEPX.

1.eSLI m = 1 , TO \TO REBRO QWLQETSQ PETLEJ, KOTORAQ I BUDET \JLEROWOJ CEPX@.

2.pUSTX SU]ESTWUET \JLEROWA CEPX DLQ SWQZNYH GRAFOW S ^ETNYMI WER[INAMI I S ^ISLOM REBER MENX[IM m .

63

3. rASSMOTRIM SWQZNYJ GRAF G c m REBRAMI, IME@]IJ TOLXKO ^ETNYE WER[INY. sTARTUEM IZ L@BOJ WER[INY x I BUDEM IDTI PO REBRAM, UDALQQ PROJDENNYE REBRA. pOSKOLXKU WSE WER[INY GRAFA BYLI ^ETNYMI, TO MY W KONCE KONCOW WERNEMSQ W WER[INU x . gRAF G0 , KOTORYJ OSTALSQ NEPROJDENNYM POSLE \TOGO, MOVET IMETX NESKOLXKO KOMPONENT SWQZNOSTI, NO KAVDAQ TAKAQ KOMPONENTA SODERVIT TOLXKO ^ETNYE WER[INY I, SLEDOWATELXNO, IMEET \JLEROWU CEPX. dALEE, PROJDEM PO PERWONA^ALXNOMU MAR[RUTU E]E RAZ, DOBAWLQQ PO PUTI \JLEROWY CEPI KOMPONENT SWQZNOSTI GRAFA G0 I POLU^IM \JLEROWU CEPX WSEGO GRAFA G . tEOREMA DOKAZANA.

aLGORITM fLERI. eSLI SWQZNYJ GRAF IMEET TOLXKO WER[INY ^ETNOJ STEPENI, TO POSTROITX EGO \JLEROWU CEPX MOVNO SOBL@DAQ DWA PRAWILA.

1)sTARTUEM IZ PROIZWOLXNOJ WER[INY GRAFA I IDEM PO REBRAM, WKL@^AQ \TI REBRA W \JLEROWU CEPX I UDALQQ IH IZ GRAFA.

2)wYBIRAEM W O^EREDNOJ WER[INE PUTX PO PERE[EJKU TOLXKO, KOGDA NET PUTI PO CIKLU.

A		A	b
C	D	C	b	D b
B		B	brIS. 32
rIS. 31

zADA^A O KENIGSBERGSKIH MOSTAH. gOROD kENIGSBERG RASPO-

LAGAETSQ NA OBOIH BEREGAH A I B REKI pREGOLI. bEREGA SOEDINQ@TSQ MOSTAMI S OSTROWAMI C I D , KOTORYE MEVDU SOBOJ TOVE SOEDINENY MOSTOM. nA RIS. 31 SHEMA MOSTOW PREDSTAWLENA TAK, KAK ONA WYGLQDELA WO WREMENA |JLERA, A SOOTWETSTWU@]IJ GRAF IZOBRAVEN NA RIS. 32. zADA^A SOSTOQLA W TOM, ^TOBY PROJTI PO KAVDOMU MOSTU ODIN RAZ I WERNUTXSQ W ISHODNU@ TO^KU. pOSKOLXKU SOOTWETSTWU@]IJ GRAF WOOB]E NE IMEET WER[IN ^ETNOJ STEPENI, TO \TA ZADA^A NE MOVET BYTX RE[ENA. oBOSNOWANIEM ZADA^I O KENIGSBERGSKIH MOSTAH lEONARD |JLER POLOVIL NA^ALO TEORII GRAFOW.

64

x9. dEREWXQ. cIKLOMATI^ESKOE ^ISLO GRAFA

oPREDELENIE 1. sWQZNYJ GRAF NAZYWAETSQ DEREWOM, ESLI ON NE IMEET CIKLOW. gRAF NAZYWAETSQ LESOM, ESLI KAVDAQ EGO KOMPONENTA SWQZNOSTI QWLQETSQ DEREWOM.

sWOJSTWO 1. eSLI T | DEREWO, TO m = n ; 1 , GDE m | KOLI- ^ESTWO EGO REBER, A n | ^ISLO EGO WER[IN.

dOKAZATELXSTWO PROWEDEM INDUKCIEJ PO ^ISLU REBER m . 1. eSLI m = 0 , TO n = 1 I FORMULA m = n ; 1 WERNA.

2. pUSTX \TA FORMULA WERNA DLQ DEREWXEW S KOLI^ESTWOM REBER MENX[IM, ^EM m .

3. rASSMOTRIM DEREWO T S m REBRAMI I UDALIM IZ NEGO REBRO g . pOSKOLXKU g { PERE[EEK, TO POLU^ATSQ DWA DEREWA T1 I T2 , DLQ KOTORYH WYPOLNENY RAWENSTWA m1 = n1 ; 1 I m2 = n2 ; 1 . u^ITYWAQ, ^TO m1 +m2 = m;1 I n1 +n2 = n , MY POLU^IM ISKOMOE RAWENSTWO m = n ; 1 DLQ DEREWA T .

sLEDSTWIE. eSLI T | LES IZ k DEREWXEW, TO m = n ; k . sWOJSTWO 2. l@BYE DWE WER[INY DEREWA MOVNO SOEDINITX ROWNO

ODNOJ \LEMENTARNOJ CEPX@.

sWOJSTWO 3. eSLI K REBRAM DEREWA DOBAWITX E]E ODNO REBRO (BEZ DOBAWLENIQ NOWYH WER[IN), TO POQWITSQ CIKL, T.K. NARU[ITSQ RAWENSTWO m = n ; 1 .

~ASTO W DEREWE WYDELQ@T ODNU IZ WER[IN, KOTORU@ NAZYWA@T KORNEM DEREWA I WSE REBRA ORIENTIRU@T W NAPRAWLENII OT \TOGO KORNQ, TAKOE ORIENTIROWANNOE DEREWO NAZYWAETSQ KORNEWYM.

oPREDELENIE 2. cIKLOMATI^ESKIM ^ISLOM GRAFA G NAZYWAETSQ ^ISLO (G) = m ; n + k , GDE m | KOLI^ESTWO REBER, n | KOLI^ESTWO WER[IN, A k | ^ISLO KOMPONENT SWQZNOSTI GRAFA G . pRIMER 1. eSLI T | LES, TO (T) = 0 , POSKOLXKU DLQ LESA

m = n ; k .

tEOREMA O MONOTONNOSTI CIKLOMATI^ESKOGO ^ISLA. eSLI

G0 POLU^AETSQ IZ GRAFA G UDALENIEM PERE[EJKA, TO (G0) = (G) ; A ESLI UDALQETSQ CIKLI^ESKOE REBRO, TO (G0) = (G) ; 1 .

dOKAZATELXSTWO. eSLI GRAF G0 POLU^AETSQ IZ GRAFA G UDALENIEM PERE[EJKA, TO m0 = m ; 1 , n0 = n , A KOLI^ESTWO KOMPONENT SWQZNOSTI UWELI^IWAETSQ NA 1, T.E. k0 = k + 1 . zNA^IT,

65

(On) = 1 , POSKOLXKU W \TOM GRAFE NET SMEVNYH

(Kn) = n , T.K. W POLNOM GRAFE L@BYE DWE WER[INY

(G0) = m0 ; n0 + k0 = m ; 1 + n + k + 1 = (G) . pRI UDALENII CIKLI^ESKOGO REBRA POLU^AEM m0 = m ; 1 , n0 = n I k0 = k ; SLEDO-

WATELXNO, (G0) = m0 ; n0 + k0 = m ; 1 + n + k = (G) ; 1 .

eSLI WZQTX PROIZWOLXNYJ GRAF G I POSLEDOWATELXNO UDALQTX CIKLI^ESKIE REBRA, TO W ITOGE POLU^ITSQ LES T , NAZYWAEMYJ OSTOWOM (SKELETOM) GRAFA G . pOSKOLXKU (T ) RAWNO 0, TO (G) OZNA- ^AET KOLI^ESTWO CIKLI^ESKIH REBER, KOTORYH NADO UDALITX IZ G , ^TOBY ON PREWRATILSQ W SKELET.

x10. hROMATI^ESKOE ^ISLO GRAFA

oPREDELENIE 1. gOWORQT, ^TO GRAF RASKRA[IWAETSQ k KRASKAMI, ESLI KAVDOJ WER[INE GRAFA MOVNO PRIPISATX ODNU IZ k KRASOK TAK, ^TOBY SMEVNYE WER[INY BYLI RASKRA[ENY W RAZNYE CWETA.

zAME^ANIE. gRAF S PETLQMI RASKRASITX NELXZQ, T.K. IME@TSQ WER[INY, SMEVNYE SAMOJ SEBE. nALI^IE KRATNYH REBER, O^EWIDNO, NE WLIQET NA RASKRA[IWAEMOSTX GRAFA. u^ITYWAQ \TI DWA OBSTOQTELXSTWA MY BUDEM RASSMATRIWATX W \TOM PARAGRAFE TOLXKO PROSTYE GRAFY.

oPREDELENIE 2. hROMATI^ESKIM ^ISLOM GRAFA G , OBOZNA^AETSQ (G) , NAZYWAETSQ NAIMENX[EE ^ISLO KRASOK, KOTORYMI EGO MOVNO RASKRASITX.

pRIMER 1. WER[IN.

pRIMER 2. SMEVNY.

pRIMER 3. (Km;n) = 2 , WWIDU TOGO, ^TO WER[INY IZ Om MOVNO RASKRASITX ODNIM CWETOM, A IZ On | DRUGIM.

sWOJSTWO 1. eSLI T | DEREWO, IME@]EE BOLEE ODNOJ WER[INY,

TO (T ) = 2 .

dOKAZATELXSTWO. zAFIKSIRUEM NEKOTORU@ WER[INU x0 DANNOGO DEREWA T I RAZOBXEM MNOVESTWO WSEH EGO WER[IN NA DWA PODMNOVESTWA K0 I K1 . wO MNOVESTWO K0 OTNESEM WSE WER[INY, KOTORYE SOEDINQ@TSQ S x0 \LEMENTARNOJ CEPX@ ^ETNOJ DLINY, A K1 BUDET MNOVESTWOM WSEH WER[IN, KOTORYE SOEDINQ@TSQ S x0 \LEMENTARNOJ

66

: : : (x ; n + 1) .

CEPX@ NE^ETNOJ DLINY. lEGKO WIDETX, ^TO SMEVNYE WER[INY POPADA@T W RAZNYE KLASSY I, PO\TOMU, MOVNO RASKRASITX WER[INY IZ K0 ODNIM CWETOM, A IZ K1 { DRUGIM.

sWOJSTWO 2. eSLI (G1) = p , (G2) = q , TO (G1 + G2) = p+ q . dOKAZATELXSTWO OSNOWANO NA TOM, ^TO PRI SOEDINENII DWUH GRAFOW G1 I G2 KAVDAQ WER[INA GRAFA G1 STANOWITSQ SMEVNOJ S KAVDOJ WER[INOJ GRAFA G2 , PO\TOMU KRASKI GRAFA G1 NELXZQ IS-

POLXZOWATX DLQ RASKRA[IWANIQ GRAFA G2 .

tEOREMA 1. hROMATI^ESKOE ^ISLO L@BOGO PROSTOGO PLANARNOGO GRAFA G NE PREWOSHODIT [ESTI.

dOKAZATELXSTWO PROWEDEM INDUKCIEJ PO ^ISLU WER[IN n .

1.eSLI n = 1 , TO (G) = 1 6 6 .

2.pUSTX (G) 6 6 DLQ WSEH PLANARNYH GRAFOW S ^ISLOM WER[IN MENX[IM, ^EM n .

3.rASSMOTRIM PROSTOJ PLANARNYJ GRAF G S n WER[INAMI. pO SLEDSTWI@ 3 IZ TEOREMY |JLERA O PLOSKIH GRAFAH SLEDUET, ^TO G IMEET WER[INU x TAKU@, ^TO deg x 6 5 . uDALIM \TU WER[INU

WMESTE S WHODQ]IMI W NEE REBRAMI. pOLU^ENNYJ GRAF G0 MOVNO RASKRASITX q KRASKAMI, GDE q 6 6 PO INDUKCIONNOMU PREDPOLOVENI@. pOSKOLXKU WER[INA x QWLQETSQ SMEVNOJ NE BOLEE, ^EM S 5 WER[INAMI, TO \TU WER[INU x MOVNO PRAWILXNO RASKRASITX W ODIN IZ 6 CWETOW. oTS@DA SLEDUET, ^TO (G) 6 6 . tEOREMA DOKAZANA.

zAME^ANIE. mOVNO USILITX REZULXTAT TEOREMY 1 I DOKAZATX, ^TO (G) 6 4 DLQ L@BOGO PROSTOGO PLANARNOGO GRAFA G .

x11. hROMATI^ESKIJ MNOGO^LEN

oPREDELENIE 1. hROMATI^ESKIM MNOGO^LENOM GRAFA G NAZYWAETSQ KOLI^ESTWO SPOSOBOW RASKRASKI G S POMO]X@ x KRASOK, OBOZNA^AEMOE (G; x) .

pRIMER 1. nAJTI (Kn; x) .

rE[ENIE. pOSKOLXKU W POLNOM GRAFE Kn WSE WER[INY POPARNO SMEVNYE, TO PRI POSLEDOWATELXNOM RASKRA[IWANII WER[IN \TOGO GRAFA NADO KAVDU@ SLEDU@]U@ WER[INU KRASITX NOWYM CWETOM. oTS@DA WYTEKAET, ^TO (Kn; x) = x(x ; 1)

67

G , IZOBRA-

tEOREMA O HROMATI^ESKOM MNOGO^LENE. pUSTX GRAF

G1 POLU^AETSQ IZ GRAFA G OTOVDESTWLENIEM DWUH EGO NESMEVNYH WER-

[IN u I v , A G2 | PROWEDENIEM W GRAFE G REBRA (u; v) , TOGDA

(G; x) = (G1 ; x) + (G2; x) .

dOKAZATELXSTWO. rASKRASKI GRAFA G RAZOBXEM NA DWA KLASSA. w PERWYJ KLASS OTNESEM TE RASKRASKI GRAFA G, PRI KOTORYH WER- [INY u I v RASKRA[ENY W ODINAKOWYE CWETA, KOLI^ESTWO TAKIH RASKRASOK RAWNO O^EWIDNO (G1; x) . wO WTOROM KLASSE BUDUT TAKIE RASKRASKI, PRI KOTORYH u I v IME@T ODINAKOWYJ CWET, KOLI^ESTWO TAKIH RASKRASOK RAWNO (G2; x) . oTS@DA WYTEKAET, ^TO(G; x) = (G1 ; x) + (G2; x) . tEOREMA DOKAZANA.

pRIMER 2. nAJTI HROMATI^ESKIJ MNOGO^LEN GRAFA VENNOGO NA RIS.33.

rE[ENIE. iZ GRAFA G OTOVDESTWLENIEM OTME^ENNYH WER[IN u I v POLU^IM GRAF G1 , A PROWEDENIEM REBRA (u; v) { GRAF G2 . aNALOGI^NO, IZ GRAFA G1 POLU^IM GRAFY K2 I K3 , IZ G2 { GRAFY

K3 I G3 . nAKONEC, IZ GRAFA G3 POLU^IM K3

I K4 .

u b

v v

u

u

b

b

b

b

b

b

b

b

b

b

b

b

Gb

u

v

v b

K4b

b G1b b

G2b

b

K2b

b

K3b

b

G3b

rIS. 33

pO TEOREME O HROMATI^ESKOM MNOGO^LENE, IMEEM:

(G; x) = (G1; x) + (G2; x) , (G1; x) = (K2; x) + (K3; x) ,(G2; x) = (K3; x) + (G3; x) , (G3; x) = (K3; x) + (K4; x) .

sLOVIW PO^LENNO \TI ^ETYRE RAWENSTWA, POLU^AEM

(G; x) = (K2; x) + 3 (K3; x) + (K4; x) .

pODSTAWLQQ HROMATI^ESKIE MNOGO^LENY DLQ POLNYH GRAFOW K2 ,

K3 I K4 PO FORMULE IZ PRIMERA 1, NAHODIM OKON^ATELXNO

(G; x) = x(x;1)+3x(x;1)(x;2)+x(x;1)(x;2)(x;3) = x(x;1)3 .

x12. oBHOD GRAFA W GLUBINU

dLQ OBHODA GRAFA G(X; ;) W GLUBINU OBRAZU@T MNOVESTWO A NERASSMOTRENNYH WER[IN, MNOVESTWO B RASSMOTRENNYH WER[IN I

68

b b

STEK S AKTIWNYH WER[IN. nA STARTE A = X , B = ? , S = ? . aLGORITM OBHODA PREDPOLAGAET WYPOLNENIE SLEDU@]IH [AGOW.

1) eSLI S = ? , A =6 ? , TO WYBIRAEM PROIZWOLXNU@ WER[INU x 2 A I IZMENQEM A := A n fxg , S := S [ fxg . |TOT [AG WYPOLNQETSQ W NA^ALE OBHODA KAVDOJ KOMPONENTY SWQZNOSTI GRAFA G .

2) eSLI S =6 ? I x | WER[INA STEKA, TO NAHODIM WER[INU y 2 A TAKU@, ^TO (x; y) 2 ; I IZMENQEM A := A n fyg , S := S [ fyg | [AG UGLUBLENIQ; ESLI VE TAKOJ WER[INY y NET, TO IZMENQEM

S := S n fxg

, B := B

[ fxg

| [AG WOZWRATA.

3) eSLI

S = ? I

A = ? , TO, W \TOM SLU^AE,

B = X I OBHOD

GRAFA ZAWER[EN.

x13. oBHOD GRAFA W [IRINU

dLQ OBHODA GRAFA G(X; ;)

W [IRINU OBRAZU@T MNOVESTWO A

NERASSMOTRENNYH WER[IN,

MNOVESTWO B RASSMOTRENNYH WER[IN I

O^EREDX T AKTIWNYH WER[IN. nA STARTE A = X ,

B = ? , T = ? .

aLGORITM OBHODA PREDPOLAGAET WYPOLNENIE SLEDU@]IH [AGOW.

1) eSLI

T = ? , A = ? , TO WYBIRAEM PROIZWOLXNU@ WER[INU

6

, T := T [ fxg . |TOT [AG WYPOLNQ-

x 2 A I IZMENQEM A := A n fxg

ETSQ W NA^ALE OBHODA KAVDOJ KOMPONENTY SWQZNOSTI GRAFA G .

2) eSLI T = ?

I

x | PERWAQ WER[INA O^EREDI T , TO NAHODIM

WER[INU y 2

6

TAKU@, ^TO (x; y) 2 ; I IZMENQEM A := A n fyg ,

A

T := T [ fyg

| [AG RAS[IRENIQ; ESLI VE TAKOJ WER[INY y

NET,

TO IZMENQEM

T := T n fxg , B := B [ fxg | KONEC RAS[IRENIQ IZ

WER[INY x .

3) eSLI T = ? I

A = ? , TO, W \TOM SLU^AE,

B = X I OBHOD

GRAFA ZAWER[EN.

pRIWEDEM DRUGOJ WARIANT ALGORITMA OBHODA GRAFA W [IRINU,

PRI KOTOROM WMESTO O^EREDI T

BUDEM OBRAZOWYWATX KONE^NU@ PO-

SLEDOWATELXNOSTX

Xi

MNOVESTW WER[IN, RASSMATRIWAEMYH NA O^E-

REDNOM [AGE RAS[IRENIQ.

nA STARTE RABOTY ALGORITMA A = X , B = ? , i = 0 , Xi

= ? .

dALEE WYPOLNQ@TSQ SLEDU@]IE PUNKTY.

1)

eSLI

A =

?

,

Xi =

?

,

TO WYBIRAEM PROIZWOLXNO

x

A

I

POLAGAEM A :=6A

x , i := i + 1 , Xi :=

x ,

B := B 2Xi I

n f g

f g

[

69

Xi+1 = ? . |TOT [AG WYPOLNQETSQ W NA^ALE OBHODA KAVDOJ KOMPONENTY SWQZNOSTI GRAFA G .

2)

eSLI

A =

?

,

Xi =

?

,

TO NAHODIM

y

2

A ,

DLQ KOTOROGO

6

6

(x; y) 2 ;

SU]ESTWUET

x 2

Xi

TAKOJ,

^TO

I WYPOLNQEM KOMANDY

Xi+1 := Xi+1 [ fyg ,

A := A n fyg ; ESLI VE TAKOJ WER[INY

y NE

SU]ESTWUET, TO ZAWER[AEM FORMIROWANIE Xi+1 KOMANDAMI

B :=

B[ Xi+1 , i := i + 1 I Xi+1 = ? .

3)eSLI A = ? , TO B = X I OBHOD GRAFA ZAWER[EN.

x14. zADA^A O KRAT^AJ[IH PUTQH W GRAFE

zADA^A O KRAT^AJ[IH PUTQH W GRAFE. gRAF G(X; ;) NAZY-

WAETSQ WZWE[ENNYM, ESLI KAVDOMU EGO REBRU (xi; xj) PRISWOENO ^ISLO l(xi; xj) , KOTOROE MY BUDEM S^ITATX DLINOJ \TOGO REBRA. zADA^A O KRAT^AJ[IH PUTQH SOSTOIT W TOM, ^TOBY NAJTI CEPX NAIMENX[EJ DLINY, SOEDINQ@]U@ DWE DANNYE WER[INY a I b SWQZNOGO GRAFA. aLGORITM RE[ENIQ \TOJ ZADA^I PREDPOLAGAET WYPOLNENIQ SLEDU@- ]IH [AGOW.

1)kAVDOJ WER[INE x PRISWOIM NA^ALXNU@ METKU m(x) PO PRA-

WILU: m(a) = 0 , m(x) = 1 , PRI x =6 a .

2)iZMENENIE METOK. pOKA SU]ESTWUET REBRO (x; y) TAKOE, ^TO

m(y) > m(x) + l(x; y) , WYPOLNQETSQ m(y) := m(x) + l(x; y) .

pO HODU RABOTY PUNKTA 2) m(x) < 1 RAWNA DLINE NEKOTOROJ CEPI, SOEDINQ@]EJ WER[INU x S WER[INOJ a , A PO OKON^ANI@ RABOTY [AGOW 1) I 2) m(x) RAWNA DLINE KRAT^AJ[EJ CEPI, SOEDINQ@]EJ WER[INY x I a .

pOSTROENIE KRAT^AJ[EJ CEPI b = x0 ! x1 ! : : : ! xn = a SOSTOIT W NAHOVDENII SLEDU@]EJ POSLE xi WER[INY xi+1 PO FOR-

MULE m(xi+1) = m(xi) ; l(xi; xi+1) , DLQ i = 0; 1; : : : ; n ; 1 , POKA NE

POLU^IM xn = a .

70