Дискретная математика Насоров А.З., Насыров З.Х. 2009
.pdfoPREDELENIE 3. sTEPENX@ WER[INY x GRAFA G(X;;) NAZY- WAETSQ 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
P deg xi = 2m.
i=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 RAWNQET-
SQ deg xi .
sWOJSTWO 3. sUMMA WSEH \LEMENTOW MATRICY SMEVNOSTI RAWNA UDWOENNOMU ^ISLU REBER GRAFA.
x 2. pODGRAF. ~ASTI^NYJ, NULEWOJ, POLNYJ, DOPOLNITELXNYJ GRAF. sOEDINENIE GRAFOW
oPREDELENIE 1. gRAF G0(X0; ;0) NAZYWAETSQ PODGRAFOM GRA-
FA G(X; ;), ESLI X0 X , A ;0 ;.
oPREDELENIE 2. gRAF, POLU^AEMYJ IZ G(X; ;) UDALENIEM NE- KOTORYH REBER BEZ IZMENENIQ MNOVESTWA WER[IN
^ASTI^NYM DLQ GRAFA G.
31
oPREDELENIE 3. gRAF, WSE n WER[IN KOTOROGO QWLQ@TSQ IZO- LIROWANNYMI, 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 KOTORO- GO QWLQ@TSQ SMEVNYMI, NAZYWAETSQ POLNYM. pOLNYJ GRAF S n WER[INAMI OBOZNA^AETSQ Kn ILI Fn .
nA RIS. 13 DANY IZOBRAVENIQ GRAFOW K2 , K3 , K4 , K5 . w MAT- RICE SMEVNOSTI POLNOGO GRAFA WSE \LEMENTY RAWNY 1, KROME \LE- MENTOW, RASPOLOVENNYH NA GLAWNOJ DIAGONALI I RAWNYH 0. o^E- WIDNO, ^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. 13 |
|
|
|
|
|
||
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 |
|||||||||||||
POLNOGO GRAFA, KOTORYH NET W GRAFE G. |
|
|
|
|
|
|||||||||
oPREDELENIE 6. sOEDINENIEM GRAFOW G(X;;) I G0(X0; ;0), |
||||||||||||||
GDE 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. 14 |
IZOBRAVENY GRAFY |
G, G0 I RQDOM PRIWEDENO IZOB- |
||||||||||||
RAVENIE GRAFA G + G0 . |
|
|
|
|
|
|
|
|
|
|
|
|||
G |
c |
c |
c |
|
c |
c |
c |
|
x1 bx2 bx3 |
b |
||||
G0 |
c |
c |
|
|
|
c |
|
c |
|
y1 |
by2 |
by3 |
b |
|
|
|
rIS. 14 |
|
|
|
|
|
|
|
|
rIS. 15 |
|
||
sOEDINENIE O |
+ O00 |
OBOZNA^AETSQ ^EREZ Km;n , WER[INY IZ |
||||||||||||
|
|
m0 |
n |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
32 |
|
|
|
|
|
|
|
O0 |
BUDEM USLOWNO NAZYWATX "DOMIKAMI", A IZ O00 { "KOLODCAMI"; |
m |
n |
NA RIS. 15 DANO IZOBRAVENIE GRAFA K3;3 . |
|
x 3. 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. 15 IZOMORFEN GRAFU, IZOBRAVENIE KOTOROGO DANO NA RIS. 16. bIEKTIWNOE OTOBRAVENIE
f MOVNO ZADATX, |
NAPRIMER, TAKIM OBRA- |
ZOM: f(x1) = z1 , |
f(x2) = z3 , f(x3) = z5 , |
f(x4) = z2 , f(x5) = z4 , f(x6) = z6 . pRIMER 2. dOKAZATX, ^TO GRAFY G1 I G2
MORFNY.
|
z5 |
z4 |
|
|
z6 |
b |
b |
bz3 |
b |
|
z1 |
zb2 |
b |
|
|
rIS. 16 |
|
|
NA RIS. 17 NE IZO-
rE[ENIE. dLQ NEIZOMORFNOSTI GRAFOW DOSTATO^NO UKAZATX HA- RAKTERISTIKU, PO KOTOROJ ONI OTLI^A@TSQ DRUG OT DRUGA. w DAN- NOM 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 WNUTREN- NIH TO^EK PERESE^ENIQ S DRUGIMI KRIWYMI. rEALIZACIEJ GRAFA W Rn NAZYWAETSQ IZOBRAVENIE, POLU^ENNOE PRI \TOM SOPOSTAWLENII.
pRIMER 3. nA RIS. 13 DANY REALIZACII GRAFOW K2 I K3 NA PLOSKOSTI R2 , A IZOBRAVENIQ K4 I K5 NE QWLQ@TSQ REALIZACIQ- MI.
tEOREMA 1. l@BOJ GRAF MOVNO REALIZOWATX W TREHMERNOM PROSTRANSTWE R3 .
dOKAZATELXSTWO. pUSTX DAN GRAF G(X; ;), X = fx1 ; x2; : : : ; xng, A ; = (g1; g2 ; : : : ; gm). wOZXMEM W PROSTRANSTWE PRQMU@ l I WYBE-
33
REM NA NEJ TO^KI x01; x02; : : : ; x0n , KOTORYE SOOTWETSTWU@T WER[I-
NAM x1; x2; : : : ; xn (SM. RIS. 18).
~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) QW- LQETSQ PETLEJ, TO EMU SOPOSTAWIM OKRUVNOSTX, KOTORAQ LEVIT W POLUPLOSKOSTI k I KASAETSQ PRQMOJ l W TO^KE x0i . tAK PRODELA-
EM 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 |
|
|
|
aj |
|
||||
|
|
G1 |
|
|
|
|
|
|
|
a |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
b b |
b |
b |
b b |
b b |
|
|
|
a |
||||
|
|
|||||||||||
|
|
rIS. 17 |
|
|
|
|
|
|
rIS. 18 |
x 4. pLOSKIE I PLANARNYE GRAFY
oPREDELENIE 1. gRAF, DOPUSKA@]IJ REALIZACI@ NA PLOSKOS- TI, NAZYWAETSQ PLANARNYM, A EGO REALIZACI@ NA PLOSKOSTI NAZY- WA@T PLOSKIM GRAFOM.
pRIMER 1. gRAF K4 QWLQETSQ PLANARNYM, EGO PLOSKU@ REALI- ZACI@ MOVNO POLU^ITX, ESLI ODNU IZ DIAGONALEJ KWADRATA NA RIS. 13 PROWESTI WNE \TOGO KWADRATA.
tEOREMA 1. gRAFY K3;3 I K5 NE QWLQ@TSQ PLANARNYMI. dOKAZATELXSTWO PROWEDEM OT PROTIWNOGO. pUSTX GRAF K3;3 (SM.
RIS. 16), QWLQETSQ PLANARNYM, TOGDA EGO MOVNO REALIZOWATX W WI- DE PLOSKOGO GRAFA G. pUSTX PRI \TOM WER[INAM zi SOOTWETSTWU@T TO^KI vi , i = 1; 2; : : : ; 6. pOSKOLXKU W GRAFE K3;3 IMEETSQ ZAMKNU- TYJ 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 KRI- WAQ DELIT PLOSKOSTX NA DWE ^ASTI: WNUTRENN@@ I WNE[N@@. pUSTX REBRO (v1; v4) RAcPOLOVENO WO WNUTRENNEJ ^ASTI (SM. RIS. 19), TOG- DA REBRO (v2; v5) DOLVNO PROHODITX WNE OBLASTI, OGRANI^ENNOJ L.
34
w \TOM SLU^AE TO^KI v3 I v6 OKAZYWA@TQ W RAZNYH ^ASTQH, NA KO- TORYE DELIT PLOSKOSTX ZAMKNUTAQ LINIQ v5 ! v4 ! v1 ! v2 ! v5 , I PO\TOMU NELXZQ PROWESTI REBRO (v3; v6) BEZ PERESE^ENIJ S DRUGI- MI 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 a |
|||
|
|
|
|
|
|
|
|
b |
|
|
|
r |
a a |
|
a |
||||
|
v1 vb2 |
|
b |
|
b |
|
r |
a |
|||||||||||
|
|
|
|
|
|||||||||||||||
|
|
rIS. 19 |
|
|
rIS. 20 |
|
|
|
rIS. 21 |
|
|
nEPLANARNOSTX GRAFA K5 USTANAWLIWAETSQ NIVE.
zAME^ANIE. iMEET MESTO TEOREMA kURATOWSKOGO { pONT-
RQGINA, KOTORAQ GLASIT, ^TO GRAF G PLANAREN TOGDA I TOLXKO TOGDA, KOGDA ON NE IMEET PODGRAFOW, STQGIWAEMYH K K3;3 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 , IZOBRAVEN- NOGO NA RIS. 21.
rE[ENIE. gRAF G1 IMEET PODGRAF G01 , IZOBRAVENNYJ NA RIS. 20. |TOT GRAF G01 STQGIWAETSQ K GRAFU K3;3 : NA RISUNKE "DOMI- KI" NARISOWANY ZAPOLNENNYMI KRUVKAMI, A "KOLODCY" { PUSTY- MI. 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 LQETSQ PLANARNYM, T.K. ON IMEET PODGRAF, STQGIWAEMYJ K
x 5. cEPI, CIKLY, SWQZNOSTX
oPREDELENIE 1. cEPX@ (MAR[RUTOM) W GRAFE G(X; ;) NAZY- WAETSQ 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.
35
oTDELXNU@ WER[INU GRAFA UDOBNO S^ITATX CEPX@ NULEWOJ DLI- NY. cEPX NAZYWAETSQ ZAMKNUTOJ, ESLI v0 = vl . cEPX ^ASTO OBOZNA- ^A@T TAK: v0 ! v1 ! : : : ! vl .
oPREDELENIE 2. cEPX v0 ! v1 ! : : : ! vl
MENTARNOJ, ESLI WSE EE REBRA I WER[INY RAZLI^NY, KROME, MOVET BYTX, WER[IN v0 I vl , ZAMKNUTAQ \LEMENTARNAQ CEPX NAZYWAETSQ CIKLOM.
tEOREMA O WYDELENII \LEMENTARNOJ CEPI. iZ L@BOJ CE-
PI, 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@ (NULEWOJ DLINY). eSLI v0 =6 vl , TO RAZBEREM DWA SLU^AQ.
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 ! ! : : : ! vj I POLU^AEM BOLEE KO- ROTKU@ CEPX v0 ! : : : vi ! vj+1 : : : ! vl . |TU OPERACI@ POWTORQEM POKA W CEPI BUDUT OSTAWATXSQ ODINAKOWYE WER[INY I W ITOGE PRI- DEM 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. 21, IMEET DWE KOMPO- NENTY SWQZNOSTI G1 I G2 .
rEBRO GRAFA NAZYWAETSQ CIKLI^ESKIM, ESLI ONO WHODIT W KAKOJ- NIBUDX CIKL. rEBRO, NE PRINADLEVA]EE NIKAKOMU CIKLU, NAZYWA- ETSQ PERE[EJKOM (MOSTOM).
sWOJSTWO 1. pRI UDALENII CIKLI^ESKOGO REBRA GRAFA G PO- LU^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.
36
sWOJSTWO 2. w SWQZNOM GRAFE S n WER[INAMI I m REBRAMI WYPOLNENO NERAWENSTWO m > n ; 1.
dOKAZATELXSTWO. pRIMENIM METOD INDUKCII PO ^ISLU REBER. 1. bAZA INDUKCII. eSLI m = 0, TO n = 1 WWIDU SWQZNOSTI
GRAFA I NERAWENSTWO m > n ; 1 WERNO.
2. iNDUKCIONNOE PREDPOLOVENIE. pUSTX NERAWENSTWO SPRAWED- LIWO 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.
x 6. tEOREMA |JLERA O PLOSKIH GRAFAH
oPREDELENIE 1. pLOSKIJ GRAF RAZBIWAET PLOSKOSTX NA NE- SKOLXKO ^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.
3.rASSMOTRIM PLOSKIJ SWQZNYJ GRAF G S m REBRAMI I UDA- LIM IZ NEGO NEKOTOROE REBRO g. eSLI g { CIKLI^ESKOE REBRO, TO POLU^ITSQ PLOSKIJ SWQZNYJ GRAF G0 , DLQ KOTOROGO PO INDUKCI- ONNOMU 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
37
SWQZNYH GRAFA G0 I G00 , DLQ KOTORYH PO INDUKCIONNOMU PREDPO- LOVENI@ 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.
x 7. 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 MNO- GOUGOLXNIKA, 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 WY- POLNENO 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 KRAJ- NEJ MERE TREMQ REBRAMI, T.K. G0 QWLQETSQ PROSTYM S KOLI^ESTWOM WER[IN n > 3. oTS@DA SLEDUET, ^TO KOLI^ESTWO REBER
TWORQET USLOWI@ m > 32 l. iSPOLXZUQ RAWENSTWO |JLERA, POLU^AEM
m + 2 = n + l 6 n + 23 m =) m 6 3n ; 6.
pRIMER 1. gRAF K5 NE QWLQETSQ PLANARNYM, T.K. DLQ NEGO NE- RAWENSTWO m 6 3n ; 6 NE WYPOLNENO.
sLEDSTWIE 3. w L@BOM PLOSKOM SWQZNOM PROSTOM GRAFE NAJ- DETSQ 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 deg xi > 6n =) m > 3n. pOSLEDNEE NERAWEN-
i=1
38
STWO PROTIWORE^IT SLEDSTWI@ 2, ^TO I DOKAZYWAET SU]ESTWOWANIE WER[INY, STEPENX KOTOROJ NE PREWOSHODIT 5.
sLEDSTWIE 4. eSLI PLOSKIJ GRAF G IMEET k KOMPONENT SWQZ- NOSTI, TO l + n = m + k + 1.
dOKAZATELXSTWO. dLQ KAVDOJ KOMPONENTY SWQZNOSTI Gi WERNA FORMULA li + ni = mi + 2. sLADYWAQ PO^LENNO \TI RAWENSTWA I U^ITYWAQ, ^TO Pni = n, Pmi = m, A Pli = l + k ; 1, T.K. 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.
x 8. |JLEROWY GRAFY. zADA^A O KENIGSBERGSKIH MOSTAH
cEPX NAZYWAETSQ PROSTOJ, ESLI WSE EE REBRA RAZLI^NY. oPREDELENIE 1. sWQZNYJ GRAF G NAZYWAETSQ \JLEROWYM, ES-
LI SU]ESTWUET PROSTAQ ZAMKNUTAQ CEPX, SODERVA]AQ WSE REBRA GRAFA G; TAKAQ CEPX NAZYWAETSQ \JLEROWOJ.
tEOREMA OB \JLEROWOM GRAFE. sWQZNYJ GRAF QWLQETSQ \J-
LEROWYM TOGDA I TOLXKO TOGDA, KOGDA WSE EGO WER[INY IME@T ^ET- NU@ STEPENX.
dOKAZATELXSTWO. eSLI GRAF G { \JLEROW, TO PRI KAVDOM PRO- HOVDENII \JLEROWOJ CEPI ^EREZ DANNU@ WER[INU
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 ^ET- NYMI WER[INAMI I S ^ISLOM REBER MENX[IM m.
3.rASSMOTRIM SWQZNYJ GRAF G c m REBRAMI, IME@]IJ TOLX- KO ^ETNYE WER[INY. sTARTUEM IZ L@BOJ WER[INY x I BUDEM ID- TI 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
39
IMETX NESKOLXKO KOMPONENT SWQZNOSTI, NO KAVDAQ TAKAQ KOMPO- NENTA 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[I- NY ^ETNOJ STEPENI, TO POSTROITX EGO \JLEROWU CEPX MOVNO SOBL@- DAQ DWA PRAWILA:
1)STARTUEM IZ PROIZWOLXNOJ WER[INY GRAFA I IDEM PO REB- RAM, 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. 23 |
|
|
|
|
||
rIS. 22 |
|
|
|
zADA^A O KENIGSBERGSKIH MOSTAH. gOROD kENIGSBERG RAS-
POLAGAETSQ NA OBOIH BEREGAH A I B REKI pREGOLI. bEREGA SO- EDINQ@TSQ MOSTAMI S OSTROWAMI C I D, KOTORYE MEVDU SOBOJ TOVE SOEDINENY MOSTOM. nA RIS. 22 SHEMA MOSTOW PREDSTAWLENA TAK, KAK ONA WYGLQDELA WO WREMENA |JLERA, A SOOTWETSTWU@]IJ GRAF IZOBRAVEN NA RIS. 23. zADA^A SOSTOQLA W TOM, ^TOBY PROJ- TI PO KAVDOMU MOSTU ODIN RAZ I WERNUTXSQ W ISHODNU@ TO^KU. pOSKOLXKU SOOTWETSTWU@]IJ GRAF NE IMEET WER[IN ^ETNOJ STE- PENI, TO \TA ZADA^A NE MOVET BYTX RE[ENA. oBOSNOWANIEM ZADA^I O KENIGSBERGSKIH MOSTAH lEONARD |JLER POLOVIL NA^ALO TEORII GRAFOW.
x 9. dEREWXQ. cIKLOMATI^ESKOE ^ISLO GRAFA
oPREDELENIE 1. sWQZNYJ GRAF NAZYWAETSQ DEREWOM, ESLI ON NE IMEET CIKLOW. gRAF NAZYWAETSQ LESOM, ESLI KAVDAQ EGO KOMPO-
40