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

NOE ZNA^ENIE ARGUMENTA, A TAKVE PRIMENQQ K NIM OPERACII SLOVENIQ, UMNOVENIQ, DIFFERENCIROWANIQ I INTEGRIROWANIQ.

X

2k + 3

pRIMER 4. nAJTI SUMMU

S =

1

.

k=0

(k + 1)2k

1

1

k

rE[ENIE. rAZLOVIM S NA DWE SUMMY: S1

= 2

X

2

= 4 I

k=0

1

1

S2 =

X

. sUMMU

S2 MOVNO NAJTI S POMO]X@ INTEGRI-

(k

+ 1)2k

k=0

ROWANIQ FORMULY DLQ

A(t)

W PRIMERE 1 W PREDELAH OT 0 DO 1=2 ,

1

1

X

POLU^IM

(k + 1)2k+1 = ln 2 . uMNOVIW OBE ^ASTI \TOGO RAWENST-

k=0

WA NA 2, NAJDEM, ^TO S2 = ln 4 .

oTWET. S = 4 + ln 4 .

x9. lINEJNYE ODNORODNYE REKURRENTNOSTI

oPREDELENIE 1. pOSLEDOWATELXNOSTX (un)1

ZADANA LINEJ-

n=0

NYM ODNORODNYM REKURRENTNYM SOOTNO[ENIEM PORQDKA k , ESLI

IZWESTNY NA^ALXNYE ZNA^ENIQ u0; u1 ; : : : ; uk;1 ,

(1)

A DLQ n > k

un = a1un

;

1 + a2 un

;

2 + : : : + ak un

;

k ,

(2)

GDE a1; a2; : : : ; ak

= 0 .

| IZWESTNYE KO\FFICIENTY, PRI^EM ak

6

pRIMER 1. pOSLEDOWATELXNOSTX fIBONA^^I ZADAETSQ TAK:

u0 = u1

= 1 , un = un

;

1 + un

;

2 , DLQ

n > 2 . nESKOLXKO PERWYH

1; 1; 2; 3;

5; 8; 13; 21 .

^LENOW \TOJ POSLEDOWATELXNOSTI SLEDU@]IE:

tEOREMA O REKURRENTNOSTI. pUSTX POSLEDOWATELXNOSTX (un)1

n=0

ZADANA REKURRENTNYM SOOTNO[ENIEM (2), TOGDA FORMULA OB]EGO

^LENA \TOJ POSLEDOWATELXNOSTI TAKOWA:

un

= P1(n)tn + P2(n)tn + : : : + Ps

(n)tn ,

1

2

s

GDE t1; t2 ; : : : ; ts

| KORNI HARAKTERISTI^ESKOGO URAWNENIQ

f(t) = tk ; a1tk;1 ; a2tk;2

;

: : : ; ak = 0 ,

A Pi(n)

| MNOGO^LENY STEPENI ki

;

1 ,

GDE

ki | KRATNOSTX ti

W KA^ESTWE KORNQ HARAKTERISTI^ESKOGO URAWNENIQ,

i

= 1; 2; : : : ; s ,

PRI^EM k1 + k2 + : : : + ks = k . kO\FFICIENTY \TIH MNOGO^LENOW OPREDELQ@TSQ IZ NA^ALXNYH USLOWIJ (1).

51

dOKAZATELXSTWO. eSLI A(t) = P1 untn , TO

n=0

1 n = ( ) ; ; ; ; k;1 ,

X unt A t u0 u1t : : : uk;1t

n=k

1 n = ( ( ) ; ; ; ; k;2) ,

X un;1t t A t u0 u1t : : : uk;2t

n=k

.

.

1 .

X un;ktn = tk A(t) .

n=k

uMNOVIM OBE ^ASTI RAWENSTWA (2) NA tn I PROSUMMIRUEM OT

n = k DO 1 . s U^ETOM PRIWEDENNYH WY[E RAWENSTW, POLU^IM, ^TO

(1

; a1t

; a2t2

; : : : ; aktk)A(t) = Qk;1(t) ,

(3)

GDE Qk

;

1

{ NEKOTORYJ MNOGO^LEN STEPENI k

1 .

k1

;k2

ks

TOGDA

pO USLOWI@ TEOREMY

f

(t) = (t

;t1)

(t

: : :

(t;ts)

,

;t2)

1 a1t

a2t2

: : :

aktk = tkf(

1

) =

;

;

;

;

t

1

1

= tk(

1

; t1)k1 (

; t2)k2 : : : (

; ts)ks =

t

t

t

= (1

; t1t)k1 (1

; t2t)k2 : : : (1 ; tst)ks .

iZ FORMULY (3) WYRAZIM A(t) :

A(t) =

; t1t)k1 (1

Qk;1(t)

; tst)ks

.

(1

; t2t)k2 : : : (1

rAZLOVIW \TU RACIONALXNU@ DROBX W SUMMU PROSTEJ[IH DROBEJ,

POLU^IM

,

^TO

s

ki

s

ki

1

A(t) =

aij

=

aij Cn

(tit)n .

(1

tit)j

j

i=1 j

=1

;

i=1 j=1 n=0

(

)

XX

XXX

pOMENQW MESTAMI ZNAKI SUMMIROWANIQ,

POLU^IM

A(t) = 1 untn ==

1

s

ki

aij Cn

tn

tn .

(j) i

n=0

n=0

i=1 j=1

X

X XX

iZ \TOGO RAWENSTWA WYTEKAET,

^TO

s

ki

s

un = i=1 j=1 aijC(nj) tin = i=1 Pi(n)tin ,

ki

ki

P P

P

GDE KO\FFICIENT

Pi(n) =

aijCn

=

aij (n+1)(n+2):::(n+j;1) QW-

j=1

(j)

j=1

(j

;

1)!

P

P

52

LQETSQ MNOGO^LENOM STEPENI ki ; 1 . tEOREMA DOKAZANA.

pRIMER 2. nAJTI OB]U@ FORMULU DLQ POSLEDOWATELXNOSTI fIBONA^^I.

rE[ENIE. pRIMENIM TEOREMU 1. wNA^ALE SOSTAWIM HARAKTERIS-

TI^ESKOE URAWNENIE

t

2

t

1 = 0 I NAJDEM EGO KORNI t1

=

1+p5

I

; ;

2

1

p5

t2

=

;

, KOTORYE IME@T KRATNOSTI k1 = k2 = 1 . zNA^IT, FORMU-

2

LA DLQ un IMEET WID un = Atn +Btn

. iSPOLXZUQ NA^ALXNYE DANNYE

1

2

1+p5

p5

1

u0

= u1 = 1 , OPREDELQEM KONSTANTY A =

2p5

I

B =

;

;

;

S

U^ETOM \TOGO POLU^AEM OTWET

2p5

0

1 + p

!

n+1

p

!

n+1

1.

1

5

1

5

un =

;

;2

p

2

5

pRIMER 3. nAJTI@FORMULY DLQ POSLEDOWATELXNOSTEJA

an

I bn ,

ESLI a0 =

;

1 , b0 =

;

1

I

an+1 = 9an ; 12bn;

(4)

bn+1 = 3an ; 3bn:

(5)

rE[ENIE. iZ URAWNENIQ

(4) WYRAVAEM

bn I PODSTAWLQEM W URAW-

bn =

1

(9an

an+1);

(6)

NENIE (5):

12

3

1

(9an+1

; a;n+2) = 3an

;

(9an ; an+1):

(7)

12

12

iZ (7) POSLE PREOBRAZOWANIJ POLU^AEM an+2

; 6an+1 + 9an = 0:

sOSTAWLQEM HARAKTERISTI^ESKOE URAWNENIE:

t2

;

6t + 9 = 0 =

2

|TO URAWNENIE IMEET KORENX

)

(t

;

3) = 0 .

t1 = 3 ,

EGO KRATNOSTX

n

= (An + B)3

n

k1

= 2 , TOGDA an = P1

(n)t

. dLQ NAHOVDENIQ A I

1

B , NAPI[EM POLU^ENNU@ FORMULU DLQ n = 0 I n = 1 , ESLI U^ESTX,

^TO a0 = ;1 , A a10

= 9a0 ; 12b0

= 3 , TO POLU^AETSQ SISTEMA:

(A 0 + B)3

=

;1; =

A = 2;

(A + B)31 = 3;

)

B = ;1:

tAKIM OBRAZOM, an = (2n ;

1)3n . pODSTAWLQQ

an W (6), NAJDEM

bn =

1

(9(2n

;

1)3n

;

(2n + 1)3n+1) = (n

;

1)3n .

n

n

12

oTWET

, bn = (n ; 1)3 .

. an = (2n ;

1)3

53

g l a w a 4 grafy

x1. pONQTIE GRAFA. mATRICA SMEVNOSTI I EE SWOJSTWA

oPREDELENIE 1. gRAFOM G NAZYWAETSQ PARA (X;;) , W KOTOROJ

X = fx1 ; x2; : : : ; xng { MNOVESTWO WER[IN, A ; = (g1; g2 ; : : : ; gm) {

NABOR REBER GRAFA, PRI^EM KAVDOE REBRO gi = (xk; xl) | NEUPORQDO^ENNAQ PARA WER[IN, NAZYWAEMYH KONCAMI REBRA gi . oDNO I TO VE REBRO MOVET WHODITX W NABOR ; NESKOLXKO RAZ, T.E. DOPUSKA@TSQ KRATNYE REBRA.

rEBRO WIDA (xk; xk) NAZYWAETSQ PETLEJ. gRAF BEZ PETELX I KRATNYH REBER NAZYWAETSQ PROSTYM.

	pRIMER	1. nA RIS. 21 PRIWEDE-			x2		b	x1 b
NA GEOMETRI^ESKAQ REALIZACIQ GRAFA
G(X; ;) , GDE X = fx1; x2 ; x3; x4g , A					x3			x4
						b rIS. 21b
; = ((x1; x1); (x1; x2) ? 2; (x2; x3)) .
	oPREDELENIE 2. oRIENTIROWANNYM GRAFOM						;!	NAZYWAETSQ PA-
							G
RA	(X; ;) ,	W KOTOROJ	X = fx1 ; x2	; : : : ; xng		{	MNOVESTWO WER[IN
GRAFA, A ;		= (g1 ; g2; : : : ; gm) { NABOR DUG,				PRI^EM KAVDAQ DUGA
gi =< xk; xl > | UPORQDO^ENNAQ PARA WER[IN, xk { NA^ALO, A xl									{
KONEC DUGI gi . oDNA I TA VE DUGA MOVET WSTRE^ATXSQ W NABORE									;
NESKOLXKO RAZ.

w DANNOM POSOBII BUDUT RASSMATRIWATXSQ TOLXKO NEORIENTIROWANNYE GRAFY. mNOGIE SWOJSTWA NEORIENTIROWANNYH GRAFOW PERENOSQTSQ NA ORIENTIROWANNYJ SLU^AJ. wMESTE S TEM, ORIENTIROWANNYE GRAFY OBLADA@T CELYM RQDOM WAVNYH HARAKTERISTIK, SWOJSTWENNYH TOLXKO IM, POZNAKOMITXSQ SO SWOJSTWAMI ORIENTIROWANNYH GRAFOW MOVNO W PRIWEDENNOJ LITERATURE.

54

GRAFA RAWNA UDWOENNOMU ^ISLU EGO REBER, T.E.

deg xi

= 2m .

oPREDELENIE 3. sTEPENX@ WER[INY x GRAFA G(X; ;) NAZYWAETSQ KOLI^ESTWO REBER IZ ; , IME@]IH x SWOIM KONCOM, PRI \TOM PETLQ U^ITYWAETSQ DWAVDY. oBOZNA^AETSQ STEPENX TAK: deg x .

eSLI deg x = 0 , TO WER[INA x NAZYWAETSQ IZOLIROWANNOJ; ESLI deg x = 1 , TO x | TUPIKOWAQ (KONCEWAQ, WISQ^AQ) WER[INA.

wER[INY xk I xl | SMEVNYE, ESLI REBRO (xk; xl) 2 ; , REBRA NAZYWA@TSQ SMEVNYMI, ESLI ONI IME@T OB]U@ WER[INU.

tEOREMA "O RUKOPOVATIQH". sUMMA STEPENEJ WSEH WER[IN

n

iP=1

dOKAZATELXSTWO. pRI SUMMIROWANII STEPENEJ WSEH WER[IN L@- BOE REBRO U^ITYWAETSQ W KAVDOM IZ SWOIH DWUH KONCOW, PO\TOMU POLU^AETSQ UDWOENNOE ^ISLO REBER.

eSTX RAZNYE SPOSOBY PREDSTAWLENIQ GRAFOW W |wm. eSLI GRAF IMEET NEBOLX[OE ^ISLO REBER, TO UDOBNO ZADATX GRAF S POMO]X@ SPISKOW SMEVNYH WER[IN: DLQ KAVDOJ WER[INY x UKAZYWA@T WSE WER[INY, SMEVNYE S x . tAKVE, MOVNO ZADAWATX GRAF S POMO]X@ MATRICY SMEVNOSTI.

oPREDELENIE 4. mATRICEJ SMEVNOSTI GRAFA G NAZYWAETSQ MATRICA A = (aij) RAZMERA n n , W KOTOROJ \LEMENT aij RAWEN KOLI^ESTWU REBER, SOEDINQ@]IH WER[INY xi I xj . pETLI, PRI \TOM, U^ITYWA@TSQ DWAVDY.

sWOJSTWO 1. mATRICA SMEVNOSTI QWLQETSQ SIMMETRI^NOJ, T.E.

AT = A .

sWOJSTWO 2. sUMMA \LEMENTOW i -TOJ STROKI MATRICY RAWNQETSQ deg xi .

sWOJSTWO 3. sUMMA WSEH \LEMENTOW MATRICY SMEVNOSTI RAWNA UDWOENNOMU ^ISLU REBER GRAFA.

x2. pODGRAF. ~ASTI^NYJ, NULEWOJ, POLNYJ, DOPOLNITELXNYJ GRAF. sOEDINENIE GRAFOW

oPREDELENIE 1. gRAF G0(X0;;0) NAZYWAETSQ PODGRAFOM GRAFA

G(X; ;) , ESLI X0 X , A ;0 ; .

oPREDELENIE 2. gRAF, POLU^AEMYJ IZ G(X;;) UDALENIEM NEKOTORYH REBER BEZ IZMENENIQ MNOVESTWA WER[IN X , NAZYWAETSQ

55

n WER-

^ASTI^NYM DLQ GRAFA G .

oPREDELENIE 3. gRAF, WSE n WER[IN KOTOROGO QWLQ@TSQ IZOLIROWANNYMI, NAZYWAETSQ NULEWYM I OBOZNA^AETSQ On .

o^EWIDNO, ^TO NULEWOJ GRAF QWLQETSQ ^ASTI^NYM DLQ L@BOGO GRAFA S TEM VE MNOVESTWOM WER[IN.

oPREDELENIE 4. pROSTOJ GRAF, L@BYE DWE WER[INY KOTOROGO QWLQ@TSQ SMEVNYMI, NAZYWAETSQ POLNYM. pOLNYJ GRAF S [INAMI OBOZNA^AETSQ Kn ILI Fn .

nA RIS. 22 DANY IZOBRAVENIQ GRAFOW K2 , K3 , K4 , K5 . w MATRICE SMEVNOSTI POLNOGO GRAFA WSE \LEMENTY RAWNY 1, KROME \LEMENTOW, RASPOLOVENNYH NA GLAWNOJ DIAGONALI I RAWNYH 0. o^EWIDNO, ^TO L@BOJ PROSTOJ GRAF QWLQETSQ ^ASTI^NYM DLQ POLNOGO GRAFA S TEM VE MNOVESTWOM WER[IN.

	c	c	c		c
				c	c
c	c c	c c	c	c	c
	rIS. 22

oPREDELENIE 5. dOPOLNITELXNYM K PROSTOMU GRAFU Q(X; ;)
NAZYWAETSQ PROSTOJ GRAF Q(X;;) TAKOJ, ^TO ; \ ; = ? , A GRAF
G(X; ; [ ;) { POLNYJ.
tAKIM OBRAZOM, DOPOLNITELXNYJ GRAF G IMEET TE REBRA IZ POL-
NOGO GRAFA, KOTORYH NET W GRAFE G .
oPREDELENIE 6. sOEDINENIEM NEPERESEKA@]IHSQ GRAFOW G(X; ;)
I G0(X0; ;0) , X \ X0		= ? , NAZYWAETSQ GRAF, OBOZNA^AEMYJ G + G0
I RAWNYJ	(X [ X0; ;	[ ;0 [ f(x; x0)j x 2 X; x0 2 X0g) .

nA RIS. 23 IZOBRAVENY GRAFY G , G0 I RQDOM PRIWEDENO IZOBRAVENIE GRAFA G + G0 .

		m0	n
	sOEDINENIE	O	+ O00 OBOZNA^AETSQ ^EREZ	Km;n , WER[INY IZ
O0	BUDEM USLOWNO NAZYWATX "DOMIKAMI", A IZ			O00 { "KOLODCAMI";
m				n

NA RIS. 24 DANO IZOBRAVENIE GRAFA K3;3 .

56

G	c	c	c	c	c	c	x1 bx2 bx3		b
G0		c	c		c	c	y1 by2	by3	b
			rIS. 23				rIS. 24

x3. iZOMORFIZM GRAFOW. rEALIZACIQ GRAFOW W R3

oPREDELENIE 1. gRAF G(X; ;) NAZYWAETSQ IZOMORFNYM GRA-
FU G0(X0; ;0) , OBOZNA^AETSQ G ' G0 , ESLI SU]ESTWUET BIEKTIWNOE
OTOBRAVENIE f : X ! X0 TAKOE, ^TO a(xi; xj) =		a(f(xi); f(xj)) ,
T.E. KOLI^ESTWO REBER, SOEDINQ@]IH L@BYE WER[INY			xi	I xj W
GRAFE G , RAWNO KOLI^ESTWU REBER, SOEDINQ@]IH SOOTWETSTWU@]IE
WER[INY W GRAFE G0 .
pRIMER 1. gRAF, IZOBRAVENNYJ NA RIS.		z5	z4
24 IZOMORFEN GRAFU, IZOBRAVENIE KOTORO-
			b	b
GO DANO NA RIS. 25. bIEKTIWNOE OTOBRAVE-
	z6	b		z3 b
NIE f MOVNO ZADATX, NAPRIMER, TAKIM OB-
RAZOM: f(x1) = z1 , f(x2) = z3 , f(x3) = z5 ,		z1	z2	b
f(x4) = z2 , f(x5) = z4 , f(x6) = z6 .		rIS. b25
pRIMER 2. dOKAZATX, ^TO GRAFY G1 I	G2 NA RISUNKE 26 NE
IZOMORFNY.

rE[ENIE. dLQ NEIZOMORFNOSTI GRAFOW DOSTATO^NO UKAZATX HARAKTERISTIKU, PO KOTOROJ ONI OTLI^A@TSQ DRUG OT DRUGA. w DANNOM SLU^AE GRAF G1 IMEET CIKL, SOSTOQ]IJ TOLXKO IZ WER[IN STEPENI 3, A GRAF G2 TAKOGO CIKLA NE IMEET. zNA^IT, \TI GRAFY NE IZOMORFNY.

oPREDELENIE 2. gOWORQT, ^TO GRAF G DOPUSKAET REALIZACI@ W PROSTRANSTWE Rn , ESLI EGO WER[INAM MOVNO SOPOSTAWITX TO^KI IZ Rn , A REBRAM SOPOSTAWITX NEPRERYWNYE KRIWYE, SOEDINQ@]IE SOOTWETSTWU@]IE TO^KI, TAK ^TOBY \TI KRIWYE NE IMELI WNUTRENNIH TO^EK PERESE^ENIQ S DRUGIMI KRIWYMI. rEALIZACIEJ GRAFA W Rn NAZYWAETSQ IZOBRAVENIE, POLU^ENNOE PRI \TOM SOPOSTAWLENII.

57

pRIMER 3. nA RIS. 22 DANY REALIZACII GRAFOW K2 I K3 NA PLOSKOSTI R2 , A IZOBRAVENIQ K4 I K5 NE QWLQ@TSQ REALIZACIQMI. tEOREMA 1. l@BOJ GRAF MOVNO REALIZOWATX W TREHMERNOM PRO-

STRANSTWE R3 .

dOKAZATELXSTWO. pUSTX DAN GRAF G(X; ;) , X = fx1; x2; : : : ; xng , A ; = (g1; g2; : : : ; gm) . wOZXMEM W PROSTRANSTWE PRQMU@ l I WYBEREM NA NEJ TO^KI x01; x02; : : : ; x0n , KOTORYE SOOTWETSTWU@T WER[INAM

x1; x2; : : : ; xn , SM. RIS. 27.

~EREZ PRQMU@ l PROWEDEM m RAZLI^NYH POLUPLOSKOSTEJ I OBO-

ZNA^IM IH 1; 2; : : : ; m . eSLI REBRO gk = (xi; xj) , GDE i =6 j , TO EMU SOPOSTAWIM POLUOKRUVNOSTX, KOTORAQ LEVIT W POLUPLOSKOSTI

k I OPIRAETSQ NA TO^KI x0i I x0j . eSLI REBRO gk = (xi; xi) QWLQETSQ PETLEJ, TO EMU SOPOSTAWIM OKRUVNOSTX, KOTORAQ LEVIT W POLUPLOSKOSTI k I KASAETSQ PRQMOJ l W TO^KE x0i . tAK PRODELAEM DLQ WSEH k = 1; 2; : : : ; m I W REZULXTATE POLU^IM REALIZACI@ GRAFA G W TREHMERNOM PROSTRANSTWE. tEOREMA DOKAZANA.

l

b

b

b

b

b

b

Gb

b

a

2

a j

G1

a

b b

b

b b

b

a

b

b

rIS. 26

rIS. 27

x4. pLOSKIE I PLANARNYE GRAFY

oPREDELENIE 1. gRAF, DOPUSKA@]IJ REALIZACI@ NA PLOSKOSTI, NAZYWAETSQ PLANARNYM, A EGO REALIZACI@ NA PLOSKOSTI NAZYWA@T PLOSKIM GRAFOM.

pRIMER 1. gRAF K4 QWLQETSQ PLANARNYM, EGO PLOSKU@ REALIZACI@ MOVNO POLU^ITX, ESLI ODNU IZ DIAGONALEJ KWADRATA NA RIS. 22 PROWESTI WNE \TOGO KWADRATA.

tEOREMA 1. gRAFY K3;3 I K5 NE QWLQ@TSQ PLANARNYMI. dOKAZATELXSTWO PROWEDEM OT PROTIWNOGO. pUSTX K3;3 , SM. RIS.

25, QWLQETSQ PLANARNYM, TOGDA EGO MOVNO REALIZOWATX W WIDE PLOSKOGO GRAFA G . pUSTX, PRI \TOM, WER[INAM zi SOOTWETSTWU@T TO^-

58

K3;3

KI vi , i = 1;2; : : : ; 6 . pOSKOLXKU W GRAFE K3;3 IMEETSQ ZAMKNUTYJ

CIKL z1 ! z2 ! : : : ! z6 ! z1 , TO I W PLOSKOM GRAFE G BUDET ZAMKNUTAQ NEPRERYWNAQ KRIWAQ L , SOSTOQ]AQ IZ REBER, SOEDINQ@]IH

POSLEDOWATELXNO TO^KI v1; v2; : : : ; v6; v1 . |TA ZAMKNUTAQ KRIWAQ DELIT PLOSKOSTX NA DWE ^ASTI: WNUTRENN@@ I WNE[N@@. pUSTX REBRO

(v1; v4)

RAcPOLOVENO WO WNUTRENNEJ ^ASTI, SM. RIS. 28, TOGDA REBRO

(v2; v5)

DOLVNO PROHODITX WNE OBLASTI,

OGRANI^ENNOJ L . nO,

TOG-

DA TO^KI v3 I v6

OKAZYWA@TQ W RAZNYH ^ASTQH, NA KOTORYE DELIT

PLOSKOSTX ZAMNKUTAQ LINIQ

v5

! v4

! v1

! v2 ! v5 I, PO\TOMU

NELXZQ PROWESTI REBRO (v3 ; v6) BEZ PERESE^ENIJ S DRUGIMI REBRAMI.

aNALOGI^NO RAZBIRAETSQ SLU^AJ, KOGDA REBRO (v1; v4)

RASPOLOVENO

WNE OBLASTI, OGRANI^ENNOJ L .

v5

x

b

a

a

v4

b

v3

r

G0 b

a

G1 a

a

G2 a

v6

b

b

b

1

a a

a

b

r

a

a

v1 vb2

b

b

r

a

a

a

rIS. 28

rIS. 29

rIS. 30

nEPLANARNOSTX GRAFA K5 USTANAWLIWAETSQ NIVE.

zAME^ANIE. iMEET MESTO TEOREMA kURATOWSKOGO { pONTRQ-

GINA, KOTORAQ GLASIT, ^TO GRAF G PLANAREN TOGDA I TOLXKO TOGDA, KOGDA ON NE IMEET PODGRAFOW, STQGIWAEMYH K ILI K5 . pOD STQGIWANIEM GRAFA PONIMAETSQ UDALENIE WER[IN y STEPENI 2 S ZAMENOJ REBER (x; y) I (y; z) ODNIM REBROM (x; z) .

pRIMER 2. uSTANOWITX NEPLANARNOSTX GRAFA G1 , IZOBRAVENNOGO NA RIS. 30.

rE[ENIE. gRAF G1 IMEET PODGRAF G01 , IZOBRAVENNYJ NA RIS. 29. |TOT GRAF G01 STQGIWAETSQ K GRAFU K3;3 : NA RISUNKE "DOMIKI" NARISOWANY ZAPOLNENNYMI KRUVKAMI, A "KOLODCY" { PUSTYMI. sTQGIWANIE PROISHODIT UDALENIEM WER[INY x STEPENI 2 S SOOTWETSTWU@]EJ ZAMENOJ DWUH WYHODQ]IH IZ NEE REBER ODNIM REBROM. pO TEOREME kURATOWSKOGO { pONTRQGINA GRAF G1 NE QWLQETSQ PLANARNYM, T.K. ON IMEET PODGRAF, STQGIWAEMYJ K K3;3 .

59

WER[IN v0

x5. cEPI, CIKLY, SWQZNOSTX

oPREDELENIE 1. cEPX@ (MAR[RUTOM) W GRAFE G(X; ;) NAZYWAETSQ POSLEDOWATELXNOSTX EGO REBER (v0; v1); (v1; v2); : : : ; (vl;1; vl) ; WER[INY v0 I vl QWLQ@TSQ KONCAMI CEPI, DLINOJ CEPI NAZYWAETSQ ^ISLO l , RAWNOE KOLI^ESTWU REBER W \TOJ CEPI.

oTDELXNU@ WER[INU GRAFA UDOBNO S^ITATX CEPX@ NULEWOJ DLINY. cEPX NAZYWAETSQ ZAMKNUTOJ, ESLI v0 = vl . cEPX ^ASTO OBOZNA-

^A@T TAK: v0 ! v1 ! : : : ! vl .

oPREDELENIE 2. cEPX v0 ! v1 ! : : : ! vl NAZYWAETSQ \LEMENTARNOJ, ESLI WSE EE REBRA I WER[INY RAZLI^NY, KROME, MOVET BYTX, I vl , ZAMKNUTAQ \LEMENTARNAQ CEPX NAZYWAETSQ CIKLOM. tEOREMA O WYDELENII \LEMENTARNOJ CEPI. iZ L@BOJ CEPI,

SOEDINQ@]EJ WER[INY v0 I vl , MOVNO UDALENIEM NEKOTORYH REBER,

POLU^ITX \LEMENTARNU@ CEPX,			SOEDINQ@]U@ v0 I vl .
dOKAZATELXSTWO. pUSTX DANA CEPX v0 ! v1 ! : : : ! vl . eSLI
v0 = vl , TO WER[INA v0	QWLQETSQ ISKOMOJ \LEMENTARNOJ CEPX@ (NU-
LEWOJ DLINY). eSLI v0	= vl , TO RAZBEREM DWA SLU^AQ.
	6
1. eSLI WSE WER[INY v0; v1; : : : ; vl RAZLI^NY, TOGDA W DANNOJ
CEPI NET ODINAKOWYH REBER I ONA \LEMENTARNA.
2. eSLI SREDI v0 ; v1; : : : ; vl			IME@TSQ WER[INY vi = vj , i < j ,
TO UDALQEM REBRA vi ! vi+1		!	: : : ! vj I POLU^AEM BOLEE KOROTKU@
CEPX v0 ! : : : vi ! vj	+1 : : :	! vl . |TU OPERACI@ POWTORQEM POKA
W CEPI BUDUT OSTAWATXSQ ODINAKOWYE WER[INY I W ITOGE PRIDEM K

SLU^A@ 1, KOGDA POLU^ITSQ CEPX S RAZLI^NYMI WER[INAMI, KOTORAQ I BUDET \LEMENTARNOJ. tEOREMA DOKAZANA.

oPREDELENIE 3. gRAF G(X; ;) NAZYWAETSQ SWQZNYM, ESLI L@- BYE DWE EGO WER[INY x I y MOVNO SOEDINITX CEPX@ IZ REBER, PRINADLEVA]IH ; .

oPREDELENIE 4. gRAF G IMEET k KOMPONENT SWQZNOSTI, ESLI ON SOSTOIT IZ k NEPERESEKA@]IHSQ SWQZNYH GRAFOW G1; G2; : : : ; Gk , KAVDYJ IZ NIH NAZYWAETSQ KOMPONENTOJ SWQZNOSTI GRAFA G.

pRIMER 1. gRAF, IZOBRAVENNYJ NA RIS. 30, IMEET DWE KOMPONENTY SWQZNOSTI G1 I G2 .

rEBRO GRAFA NAZYWAETSQ CIKLI^ESKIM, ESLI ONO WHODIT W KAKOJNIBUDX CIKL. rEBRO, NE PRINADLEVA]EE NIKAKOMU CIKLU, NAZYWAET-

60