DISKR_fzo 2009
.pdfNENTA 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 ROW-
NO 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 NAZYWA- ETSQ ^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. eS-
POLU^AETSQ IZ GRAFA G UDALENIEM REBRA, TO (G0) = (G) PRI UDALENII PERE[EJKA I (G0) = (G) ; 1 PRI UDALENII CIK- LI^ESKOGO REBRA.
dOKAZATELXSTWO. eSLI GRAF G0 POLU^AETSQ IZ GRAFA G UDA- LENIEM PERE[EJKA, TO m0 = m ; 1, n0 = n, A KOLI^ESTWO KOM- PONENT SWQZNOSTI UWELI^IWAETSQ NA 1, T.E. k0 = k + 1. zNA^IT,
(G0) = m0 ; n0 + k0 = m ; 1 + n + k + 1 = (G). pRI UDALE-
NII CIKLI^ESKOGO REBRA POLU^AEM m0 = m ; 1, n0 = n I k0 = k;
SLEDOWATELXNO, (G0) = m0 ; n0 + k0 = m ; 1 + n + k = (G) ; 1.
41
eSLI WZQTX PROIZWOLXNYJ GRAF G I POSLEDOWATELXNO UDALQTX CIKLI^ESKIE REBRA, TO W ITOGE POLU^ITSQ LES T , NAZYWAEMYJ OS- TOWOM (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.
x 10. hROMATI^ESKOE ^ISLO GRAFA
oPREDELENIE 1. gOWORQT, ^TO GRAF RASKRA[IWAETSQ k KRAS- KAMI, 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. W NEM IME- ETSQ WER[INA, SMEVNAQ SAMOJ SEBE. nALI^IE KRATNYH REBER O^E- WIDNO NE WLIQET NA RASKRA[IWAEMOSTX GRAFA. u^ITYWAQ \TI DWA OBSTOQTELXSTWA, MY BUDEM RASSMATRIWATX W \TOM PARAGRAFE TOLX- KO PROSTYE GRAFY.
oPREDELENIE 2. hROMATI^ESKIM ^ISLOM GRAFA G NAZYWAETSQ NAIMENX[EE ^ISLO KRASOK, KOTORYMI EGO MOVNO RASKRASITX. |TO ^ISLO OBOZNA^AETSQ ^EREZ (G).
pRIMER 1. (On) = 1, POSKOLXKU W \TOM GRAFE NET SMEVNYH WER[IN.
pRIMER 2. (Kn) = n, T.K. W POLNOM GRAFE L@BYE DWE WER[INY SMEVNY.
pRIMER 3. (Km;n) = 2, WWIDU TOGO, ^TO WER[INY IZ Om MOV- NO 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 PODMNO- VESTWA K0 I K1 . wO MNOVESTWO K0 OTNESEM WSE WER[INY, KOTO- RYE SOEDINQ@TSQ S x0 \LEMENTARNOJ CEPX@ ^ETNOJ DLINY, A K1 BUDET MNOVESTWOM WSEH WER[IN, KOTORYE SOEDINQ@TSQ S x0 \LE- MENTARNYMI CEPQMI 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
42
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 ISPOLXZOWATX DLQ RASKRA[IWANIQ GRAFA G2 .
tEOREMA 1. hROMATI^ESKOE ^ISLO L@BOGO PROSTOGO PLANARNO- GO 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 PREDPOLO- VENI@. 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 DOKA- ZANA.
zAME^ANIE. mOVNO USILITX REZULXTAT TEOREMY 1 I DOKAZATX, ^TO (G) 6 4 DLQ L@BOGO PROSTOGO PLANARNOGO GRAFA G.
43
metodi~eskie ukazaniq po re{eni` zada~
zADA^A 1
nAJTI MNOGO^LEN vEGALKINA, REALIZU@]IJ BULEWU FUNKCI@ f(a; b; c; d) = (3 ; 8; 12; 15), ZADANNU@ STOLBCOM ZNA^ENIJ W STAN- DARTNOJ TABLICE ISTINNOSTI.
rE[ENIE
sTANDARTNAQ TABLICA ISTINNOSTI \TOJ FUNKCII (SM. TABL. 9)
IMEET 16 STRO^EK. dLQ NAHOVDENIQ MNOGO- |
|
|
tABLICA 9 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
^LENA vEGALKINA NAPI[EM FORMULU (3) NA |
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
a |
b |
c |
d |
f |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
S. 8, ISPOLXZUQ TOLXKO TE STRO^KI, NA KOTO- |
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
0 |
0 |
0 |
0 |
0 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
RYH FUNKCIQ f QWLQETSQ ISTINNOJ. w RE- |
0 |
0 |
0 |
1 |
0 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
ZULXTATE POLU^ITSQ FORMULA f(a; b; c; d) = |
0 |
0 |
1 |
0 |
0 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
bcd |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
a |
|
|
|
|
abc d ab cd abc d abcd ab cd |
0 |
0 |
1 |
1 |
1 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
d abcd. dALEE, UPROSTIM \TU FORMU- |
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||
abc |
|
0 |
1 |
0 |
0 |
1 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||
LU, ISPOLXZUQ SWOJSTWA xy xz = x(y z) |
0 |
1 |
0 |
1 |
1 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
I x |
x |
|
= 1. sDELAEM SLEDU@]IE PREOBRAZO- |
0 |
1 |
1 |
0 |
1 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||
WANIQ: |
|
|
|
|
|
|
|
f(a; b; c; d) = |
|
|
bcd |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
a |
ab c( d d) |
0 |
1 |
1 |
1 |
1 |
||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||
abc( d |
d) a cd( b b) abcd = abcd ab |
c |
1 |
0 |
0 |
0 |
1 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||
abc a |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||
cd |
|
abcd = a bcd |
ab( c c) a c d |
1 |
0 |
0 |
1 |
0 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
abcd = = a bcd |
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||
ab a c d abcd. dALEE, ZA- |
1 |
0 |
1 |
0 |
0 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
MENQEM OTRICANIQ PEREMENNYH PO FORMULE |
1 |
0 |
1 |
1 |
0 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
= x |
1, RASKRYWAEM POLU^IW[IESQ SKOB- |
1 |
1 |
0 |
0 |
1 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||
x |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
KI I PRIWODIM PODOBNYE ^LENY PO FORMULE |
1 |
1 |
0 |
1 |
0 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
x x = 0: f(a; b; c; d) = (a 1)(b 1)cd |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
1 |
1 |
1 |
0 |
0 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
(a 1)b a(c 1)(d 1) abcd = abcd acd |
1 |
1 |
1 |
1 |
1 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
bcd cd ab b acd ac ad a abcd = = bcd ab ac ad cd a b.
oTWET: f(a; b; c; d) = bcd ab ac ad cd a b.
44
zADA^A 2
dLQ BULEWOJ FUNKCII g(a; b; c) = (a b)(b ! (a c)) _ a ! c SOSTAWITX TABLICU ISTINNOSTI, S POMO]X@ \TOJ TABLICY NAJTI MINIMALXNU@ dnf I POSTROITX KONTAKTNU@ SHEMU NA OSNOWE \TOJ MINIMALXNOJ dnf.
A = a b, B = a c, C = b ! B , D = A C , E = c, F = a ! E , G = F I,
NAKONEC, g(a; b; c) = D_G. sOSTAWIM TABLICU ISTINNOSTI DLQ WSEH \TIH PODFORMUL (SM. TABL. 10), ISPOLXZUQ OPREDELENIQ LOGI^ESKIH OPERACIJ.
tABLICA 10
|
|
|
A |
B |
C |
D |
E |
F |
G |
g |
||
|
a b |
a c |
b ! B |
A C |
|
|
|
a ! E |
F |
D _ G |
||
a b c |
|
c |
||||||||||
|
|
|
|
|
|
|
||||||
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
|
1 |
0 |
1 |
|
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
|
1 |
0 |
1 |
|
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
|
1 |
0 |
0 |
|
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
|
1 |
0 |
0 |
|
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
|
1 |
0 |
0 |
|
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
|
0 |
1 |
1 |
|
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
|
1 |
0 |
1 |
|
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
|
0 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
wREZULXTATE IMEEM STOLBEC ZNA^ENIJ g(a; b; c) = (0;1; 5; 6; 7) =
=(1100 0111)T .
pEREHODIM K NAHOVDENI@ MINIMALXNOJ dnf. wNA^ALE NAJDEM WSE PROSTYE KON_@NKTY FUNKCII g, PRIMENQQ PRAWILO SKLEIWA-
NIQ AB _ A B = A.
nABORY 0; 1; 5;6; 7, NA KOTORYH g RAWNA 1, ZAPI[EM, SORTI- RUQ IH W GRUPPY PO KOLI^ESTWU EDINIC, I NAHODIM WSE WARIAN- TY DLQ PRIMENENIQ PRAWILA SKLEIWANIQ (SKLEIWA@]IESQ STRO^KI NAHODQTSQ W SOSEDNIH GRUPPAH). w REZULXTATE SKLEIWANIEM KON_-
@NKTOW (0) I (1), (1) I (5), (5) I (7), (6) I (7) POLU^IM ZAMENQ@- ]IE IH KON_@NKTY (0; 1) = (00;), (1; 5) = (;01), (5; 7) =(1{1), (6; 7) = (11;). kON_@NKTY (0), (1), (5), (6) I (7) W REZULXTATE SKLEIWANIQ PROPALI. w ITOGE, OSTALISX ^ETYRE KON_@NKTA: (00;),
45
(;01), (1{1) I (11;). pRAWILO SKLEIWANIQ PRIMENITX K NIM NEWOZ- MOVNO I W REZULXTATE POLU^ILASX SOKRA]ENNAQ dnf: g(a; b; c) =
= (00;) _ (;01)_(1{1)_(11;) =
(0) |
000 |
|
(0,1) |
00{ |
|
|
|
||||
(1) |
001 |
||||
(1,5) |
{01 |
||||
|
|
||||
(5) |
101 |
||||
|
|
|
|||
(5,7) |
1{1 |
||||
(6) |
110 |
||||
(6,7) |
11{ |
||||
(7) |
111 |
||||
|
|
|
|||
a b _ bc _ ac _ ab.
tABLICA 11
|
0 |
0 |
1 |
1 |
1 |
|
0 |
0 |
0 |
1 |
1 |
|
0 |
1 |
1 |
1 |
0 |
00{ |
1 |
1 |
|
|
|
|
|
|
|
|
|
1{1 |
|
|
1 |
1 |
|
|
|
|
|
|
|
11{ |
|
|
|
1 |
1 |
|
|
|
|
|
|
{01 |
|
1 |
1 |
|
|
|
|
|
|
|
|
pO TABLICE ISTINNOSTI DLQ PROSTYH KON_@NKTOW WIDNO (SM. TABL. 11), ^TO KON_@NKTY a b I ab NELXZQ UDALITX, A IZ DWUH OSTAW[IHSQ KON_@NKTOW MOVNO ODNOGO UDALITX, T.E. g(a; b; c) IME- ET DWE MINIMALXNYE dnf: g(a; b; c) = a b _ bc _ab = a b _ ac_ ab. dLQ POSTROENIQ KONTAKTNOJ SHEMY, FUNKCIEJ PROWODIMOSTI
KOTOROJ QWLQETSQ g(a; b; c), WOZXMEM ODNU IZ MINIMALXNYH
dnf, NAPRIMER, g(a; b; c) = |
a |
b _ ac _ ab. |
+ |
|
|
|
|
|
|
|
|
||
|
|
|
r |
|
|
r |
|||||||
eSLI PO \TOJ dnf POSTROITX SHEMU, TO ONA |
|
|
|
|
a |
|
|||||||
|
|
b |
|
||||||||||
BUDET SOSTOQTX IZ 6 KONTAKTOW, ESLI VE \TU |
|
|
|
|
|
|
|
||||||
|
|
|
|
rb |
|
|
r |
||||||
dnf PREDWARITELXNO PREOBRAZOWATX TAK: |
|
|
|
|
|
c |
|||||||
|
|
a |
|
||||||||||
f(a; b; c) = |
|
b _ a(c _ b), TO MOVNO POSTRO- |
; |
|
|
|
|
|
|
|
|
||
a |
|
|
|
|
|
|
|
|
|||||
|
|
|
rISr . 24 r |
|
r |
||||||||
ITX SHEMU IZ 5 KONTAKTOW, IZOBRAVENNU@ |
|
|
|
|
|
||||||||
NA RIS. 24.
zADA^A 3
dOKAZATX RAWENSTWO (A n B)4( A [ C) = B , C { PROIZWOLXNYE MNOVESTWA.
rE[ENIE dLQ DOKAZATELXSTWA PRIMENIM METOD
KRUGOW |JLERA (SM. RIS. 25). iZOBRAZIM DANNYE MNOVESTWA KRUGAMI TAK, ^TOBY ONI RAZBIWALI PLOSKOSTX NA 8 ^ASTEJ. iZ \TO- GO RISUNKA WIDNO, ^TO A n B = M4 [ M5 ,
A [ C = M0 [ M1 [ M2 [ M3 [ M5 [ M7 I
TOGDA MNOVESTWO W LEWOJ ^ASTI RAWENSTWA
46
A \ (B4C), GDE A,
AB
M6
M4 M2
M7
M5 M3
M1
CM0
rIS. 25
WY^ISLQETSQ TAK: LP = (M4[M5)4(M0[M1[M2[M3[M5[M7) =
= M0 [ M1 [ M2 [ M3 [ M4 [ M7).
dALEE, IZ RISUNKA WIDNO, ^TO B4C = M1 [ M2 [ M5 [ M6 ,
A \ (B4C) = (M4 [ M5 [ M6 [ M7) \ (M1 [ M2 [ M5 [ M6) = = M5 [M6 . tOGDA RP = M5 [ M6 = M0 [M1 [M2 [M3 [M4 [M7 .
mY WIDIM, ^TO OBA MNOVESTWA SOSTOQT IZ ODNIH I TEH VE ^ASTEJ, \TO I DOKAZYWAET IH RAWENSTWO.
zADA^A 4
|
|
pUSTX DANY BINARNYE OTNO[ENIQ R1 |
A P I R2 |
B |
P , |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
GDE A = |
|
f |
a; b; c |
g |
, B = |
|
f |
x; y; z |
g |
, |
P = |
f |
p; q; r; t |
|
. nAJTI KOMPOZICI@ |
|
|||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
R; |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
g |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
, |
|||||||||||||||
OTNO[ENIJ R1 |
|
|
|
|
, ESLI |
R1 |
= |
f |
(a; q); (b; p); (b; q); (b; r); (c; r); (c; t) |
g |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(z; t)g. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
R2 = f(y; p); (y; q); (y; r); (y; t); (z; r); |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
rE[ENIE |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
pOSKOLXKU |
|
|
|
|
|
|
POLU^AETSQ IZ DEKARTOWA PROIZWEDENIQ A P |
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
R1 |
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||
UDALENIEM WSEH PAR, WHODQ]IH W R1 , TO |
R1 = (A |
|
|
P ) |
|
R1 = |
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||
= |
f |
(a; p);(a; r);(a; t); (b; t); (c; p); |
(c; q) |
g |
. oTNO[ENIE R;1nPOLU^AET- |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|||
SQ IZ R2 |
PERESTANOWKOJ KOORDINAT WSEH PAR, SOSTAWLQ@]IH OTNO- |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
[ENIE R2 ; T.E. R;1 |
= |
|
f |
(p; y); (q; y); (r; y); (t; y); (r; z);(t; z) |
g |
. kOM- |
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
POZICIQ |
|
|
|
|
|
|
|
|
R; |
12 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(c; y) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
|
|
R1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||
|
|
|
= |
f |
(a; y); (a; z); (b; y); (b; z); |
g |
. oB_QSNQETSQ |
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
A (p; y) |
|
|
R; |
1 |
, |
|
|||||||||||||||
OTWET SLEDU@]IM OBRAZOM. pOSKOLXKU (a; p) |
2 |
R1 , |
2 |
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
TO (a; y) |
|
|
|
R1 |
|
|
|
|
R; |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
||||||||||||||||
2 |
|
|
|
|
. oSTALXNYE PARY POLU^A@TSQ ANALOGI^NO. |
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
1 |
= |
|
|
(a; y); (a; z); (b; y); (b; z); (c; y) |
|
. |
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||
|
|
oTWET: |
|
R1 |
|
R; |
|
|
f |
g |
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
zADA^A 5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
wY^ISLITX ZNA^ENIE P7 |
|
; |
4 |
|
P (3; 2; 2) + A3 |
; |
A6 |
|
|
|
|
5 |
|
C2 |
|
; |
C3 . |
|
|||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6 |
(4) ; |
|
7 |
|
(8) |
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
rE[ENIE |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
wY^ISLQEM ZNA^ENIQ PERESTANOWOK, RAZME]ENIJ I SO^ETANIJ |
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
PO FORMULAM, KOTORYE BYLI POLU^ENY W TRETXEJ GLAWE: |
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||
P7 = 7! = 1 2 3 |
4 5 |
6 7 = 5040; |
P(3; 2; 2) = |
|
(3 + 2 + 2)! |
|
|
= 210; |
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
3! |
|
2! |
|
2! |
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||
A3 |
= |
|
|
6! |
|
|
|
|
= 120; |
|
|
|
A6 |
|
= 46 |
= 4096; |
C2 |
|
= |
|
|
|
|
7! |
|
|
|
|
|
= 210, |
|
||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||
|
6 |
|
|
(6 |
|
; |
3)! |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(4) |
|
|
|
|
|
|
|
|
|
|
|
|
7 |
|
|
|
2! (7 ; 2)! |
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
C |
3 |
|
= (8 + 3 |
; 1)! |
|
|
= 120. pODSTAWLQEM POLU^ENNYE ZNA^ENIQ W |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||
(8) |
|
|
(8 |
; 1)! |
|
3! |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
|
6 |
|
|
|
|
|
|
|
2 |
|
|
|
|
3 |
|
|
|
|
|||||||||||||||
DANNOE WYRAVENIE |
|
|
|
|
|
P7 |
; |
4 |
P (3; 3; 2) + A6 ; A(4) ; 5 C7 ; C(8) = |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
: |
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||
= 5040 ; 4 210 + 120 ; 4096 |
; 5 21 ; 120 = |
;1. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
47 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
oTWET: P7 ; 4 P (3; 2; 2) + A36 ; A6(4) ; 5 C72 ; C(8)3 = ;1.
zADA^A 6
nAJTI OB]IE FORMULY DLQ POSLEDOWATELXNOSTEJ an I bn , ESLI
a0 = 5, b0 = 2 I |
an+1 = 6an ; 8bn; |
(1) |
||||||
|
|
|
|
|
bn+1 = 2an ; 4bn: |
(2) |
||
|
|
|
|
|
rE[ENIE |
|
||
iZ URAWNENIQ (1) WYRAVAEM bn I PODSTAWLQEM W URAWNENIE (2): |
||||||||
bn = |
1 |
(6an |
an+1); |
(3) |
||||
|
||||||||
8 |
|
|
4 |
|
|
|||
|
1 |
(6an+1 ; a;n+2) = 2an ; |
(6an ; an+1): |
(4) |
||||
8 |
8 |
|||||||
iZ (4) POSLE PREOBRAZOWANIJ POLU^AEM: an+2 ;2an+1 ;8an = 0: |TO REKURRENTNOE URAWNENIE QWLQETSQ LINEJNYM I ODNOROD-
NYM, PO\TOMU MOVNO PRIMENITX TEOREMU 1 (SM. S. 27).
1.sOSTAWLQEM HARAKTERISTI^ESKOE URAWNENIE t2 ; 2t ; 8 = 0, KOTOROE IMEET KORNI t1 = 4 I t2 = ;2. kRATNOSTI k1 I k2 \TIH KORNEJ RAWNY 1, POSKOLXKU t2 ; 2t ; 8 = (t ; 4)1 (t + 2)1 .
2.fORMULA OB]EGO ^LENA DLQ an PO TEOREME 1 WYGLQDIT TAK:
an = P1(n)tn1 + P2(n)tn2 ; STEPENI MNOGO^LENOW P1(n) I P2(n) NA 1 MENX[E KRATNOSTEJ k1 I k2 . oTS@DA SLEDUET, ^TO \TI MNOGO-
^LENY QWLQ@TSQ KONSTANTAMI, OBOZNA^IM IH ^EREZ A I B. tAKIM
OBRAZOM, an = A 4n + B (;2)n .
3. dLQ NAHOVDENIQ A I B NAPI[EM POLU^ENNU@ FORMULU DLQ
n = 0 I n = 1, ESLI U^ESTX, ^TO a0 = 5, A a1 = 6a0 ; 8b0 = 14, TO POLU^AETSQ SISTEMA
A + B = 5; |
|
|
|
|
A = 4; |
|
|
|
|
|
|
|
||||
4 A ; 2 |
B = 14; |
=) |
B = 1: |
|
|
|
|
|
|
|
||||||
4. tAKIM OBRAZOM, an = 4 4n + (;2)n . pODSTAWLQQ an W (3), |
||||||||||||||||
1 |
|
6(4 4n +(;2)n);(4 4n+1 |
+(;2)n+1 |
|
= 4n +(;2)n . |
|||||||||||
NAJDEM bn = 8 |
||||||||||||||||
|
|
|||||||||||||||
oTWET: an = 4 4 |
n |
+ (;2) |
n |
, bn = 4 |
n |
+ (;2) |
n |
. |
|
|
|
|||||
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
zADA^A 7 |
|
|
|
|
|
|
|
||||
rE[ITX REKURRENTNOSTX an+2 + 10an+1 + 25an = 36, |
(1) |
|||||||||||||||
PRI USLOWII, ^TO a0 = 0, a1 = ;4. |
|
|
|
|
|
|
|
|
||||||||
48
rE[ENIE
uRAWNENIE (1) NE QWLQETSQ ODNORODNYM, T.K. EGO PRAWAQ ^ASTX RAWNA 36. ~TOBY IZBAWITXSQ OT NEODNORODNOSTI, ZAPI[EM (1), ZA-
MENIW n NA n + 1: an+3 + 10an+2 + 25an+1 = 36. |
(2) |
dALEE, IZ (2) PO^LENNO OTNIMEM (1) I POLU^IM |
|
an+3 + 9an+2 + 15an+1 ; 25an = 0. rEKURRENTNOSTX STALA ODNORODNOJ I EE MOVNO RE[ATX PO OB-
]EJ SHEME, SOGLASNO TEOREME 1.
1. sOSTAWLQEM I RE[AEM HARAKTERISTI^ESKOE URAWNENIE |
|
|
|||||||||||
3 2 |
; |
25 = 0 = |
t1 = 1; t2 = |
; |
5; k1 = 1; k2 = 2. |
|
|
||||||
|
|
) |
|
|
|
+ C)(;5) |
n |
|
|
|
|
||
2. pI[EM OB]U@ FORMULU an = A + (Bn |
|
. |
|
|
|
||||||||
3. zNA^ENIQ A, B I C NAHODIM, RE[AQ SISTEMU |
|
|
|
|
|
||||||||
a0 = A + C = 0; |
|
|
|
|
|
|
=) |
8 |
A = 1; |
|
|||
8 a1 = A ; 5B ; |
5C = ;4; |
|
|
|
|
|
B = 2 |
|
|||||
< a2 = A + 50B + 25C = 36 |
; |
10a1 |
; |
25a0 = 76: |
< |
C = |
; |
1: |
|||||
|
|
|
|
|
|
|
: |
|
|
||||
: oTWET: an = 1 + (2n ; 1)(;5)n . |
|
|
|
|
|
|
|
||||||
zADA^A 8
nAJTI MATRICU SMEVNOSTI DLQ GRAFA G(X; ;), GDE NABOR REBER
; = ((x1; x2) ? 2; (x1; x3) ? 2; (x1; x4) ? 3; (x2; x3); (x3; x4); (x2; x2))
I MNOVESTWO WER[IN X = fx1; x2; x3; x4g. rE[ENIE
nARISUEM DANNYJ GRAF G (SM. RIS. 26).
|
|
|
|
|
|
|
x3 |
|
A = 0 |
0 2 2 3 |
1 |
|
|
|
|
|
|
|
|
|
|||
x2 |
|
|
b |
|
|
b |
|||||
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
2 2 1 0 |
||
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
B |
2 1 0 1 |
C |
|
|
|
|
|
|
|
|
|
@ |
3 0 1 0 |
A |
x1 |
|
|
b |
|
x4 |
brIS. 26 |
|||||
|
|
|
|
|
|
|
|||||
eGO MATRICA SMEVNOSTI QWLQETSQ KWADRATNOJ RAZMERA n n, GDE n { KOLI^ESTWO WER[IN GRAFA; W NA[EM SLU^AE n = 4. |LE- MENTAMI \TOJ MATRICY QWLQ@TSQ ^ISLA aij , POKAZYWA@]IE KO- LI^ESTWO REBER, SOEDINQ@]IH WER[INY xi I xj . nAPRIMER, DLQ
DANNOGO GRAFA a14 = 3, a23 = 1, a24
U^ITYWAETSQ W DWOJNOM KOLI^ESTWE, PO\TOMU a22 = 2. mATRI- CA SMEVNOSTI NEORIENTIROWANNOGO GRAFA QWLQETSQ SIMMETRI^NOJ,
49
T.E. 8i; j (aij = aji). u^ITYWAQ WSE \TI SOOBRAVENIQ I POLU^AEM MATRICU A DLQ DANNOGO GRAFA
zADA^A 9
dLQ GRAFA G = O3 + K3 NAJTI CIKLOMATI^ESKOE I HROMATI- ^ESKOE ^ISLA.
|
|
|
rE[ENIE |
|
|
|
|
||||
gRAFY O3 , K3 |
I G = O3 + K3 |
IZOBRAVENY NA RIS. 27. |
|
||||||||
|
b |
|
|
b |
|
|
x1 P |
y1 |
|
|
|
|
|
Q |
|
x2 P |
b |
by2 |
|
||||
|
|
|
|
|
|
|
P |
Q |
|
|
|
b |
|
|
Q |
b |
|
S |
PPQ |
|
b |
||
|
|
|
|
|
|
bPS |
|
|
|||
|
|
|
|
|
|
|
PPS |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
O3 b |
|
K3b |
|
|
xO3 3 + Kby33 |
b |
|
||||
rIS. 27
nAPOMINAEM, ^TO CIKLOMATI^ESKOE ^ISLO GRAFA WY^ISLQETSQ PO FORMULE (G) = m ; n + k. w NA[EM SLU^AE GRAF IMEET KOLI^ESTWO REBER m = 12, KOLI^ESTWO WER[IN n = 6 I KOLI^ESTWO KOMPONENT SWQZNOSTI k = 1. sLEDOWATELXNO, (G) = 12;6+1 = 7. hROMATI^ESKIM ^ISLOM GRAFA G NAZYWAETSQ NAIMENX[EE ^ISLO KRASOK, KOTORYMI MOVNO RASKRASITX EGO WER[INY TAK, ^TOBY SMEVNYE WER[INY BYLI RASKRA[ENY W RAZNYE CWETA. w NA[EM SLU^AE DLQ WER[IN y1; y2; y3 TREBU@TSQ TRI RAZNYE KRASKI, T.K. ONI WSE POPARNO SMEVNYE, A WER[INY x1; x2; x3 MOVNO POKRASITX
^ETWERTOJ KRASKOJ. tAKIM OBRAZOM, (G) = 4. oTWET: (G) = 7, (G) = 4.
50