DISKREČIOJI MATEMATIKA (2 semestras)
KOMBINATORIKOS IR GRAFU‘ TEORIJOS PRADMENYS

PROGRAMA

I. KOMBINATORIKA
1. Matematinės indukcijos ir Dirichlė principai
2. Dauginimo taisyklė. ,,Skaičiuok dukart” principas
3. Gretiniai, kėliniai ir deriniai
4. Kartotiniai gretiniai
5. Binominiu‘ koeficientu‘ tapatybės
6. Rėčio principas
7. Netvarku‘ uždavinys
8. Siurjekciju‘ skaičius
9. Stirlingo skaičiai
10. Skirtumo operatorius
11. Laipsninė generuojanti funkcija
12. Katalano skaičiai
13. Eksponentinė generuojanti funkcija
14. Rekurentieji sa‘ryšiai. Fibonačio skaičiai
15. Bendra rekurenčiu‘ju‘ sa‘ryšiu‘ teorija
16. Sudėtiniu‘ funkciju‘ Tayloro koeficientai
17. Grandininės trupmenos
II. GRAFU‘ TEORIJA
1.
2.
3.
4.
5.
6.
7.
8.
9.

Pagrindinės sa‘vokos
Miškas ir medžiai
Viena optimizavimo problema
Grafo parametru‘ ryšiai
Grafo planarumas
Grafo viršūniu‘ spalvinimo problema
Medžiu‘ skaičius. Priūferio kodas
Numeruotu‘ grafu‘ eksponentinės generuojančios funkcijos
Grafu‘ teorijos ir algebros sa‘ryšiai
1

LITERATŪRA
1. E. Manstavičius, Kombinatorikos ir grafu‘ teorijos pradmenys, Interneto svetainė:
vu/maf/ttsk/manstavicius/.
2. M. Bloznelis, Kombinatorikos paskaitu‘ ciklas, Vilniaus universiteto leidykla, 1996.
3. P. Tannenbaumas, R. Arnoldas, Kelionės ‘i šiuolaikine‘ matematika‘ , TEV, Vilnius,
1995.
4. P.J. Cameron, Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, 1996.
5. M. Aigner, G.M. Ziegler, Proofs from THE BOOK, Springer, 2001.
6. R. Wilson, Introduction to Graph Theory, Longman, 1985 (yra vertimas i‘ rusu‘ k.).
7. B. Bollobás, Graph Theory, Springer, 1979.
8. L. Volkmann, Fundamente der Graphentheorie. Springer, 1996.
9. V.N. Sačkov, ‘Ivadas ‘i kombinatorinius diskrečios matematikos metodus, Nauka,
Maskva, 1982 (rusu‘ k.).
10. G.P. Gavrilov, A.A. Sapoženko, Diskrečiosios matematikos uždavinynas, M., Nauka, 1977 (rusu‘ k.).
I. KOMBINATORIKA
1. Matematinės indukcijos ir Dirichlė principai
Sunkiausia apibrėžti kombinatorikos tyrimu‘ objekta‘. Kombinatorikai reiktu‘ priskirti uždavinius, nagrinėjančius struktūras, t.y. aibes su kažkokiais vidiniais ryšiais. Dažnai pačiu‘
struktūru‘ egzistavimas būna problematiškas. Jei jos egzistuoja, tada ieškoma, kiek ju‘
yra iš viso. Kombinatorikai tradiciškai priskiriami i‘vairūs algebriniai sa‘ryšiai, formulės,
kuriose nenaudojamos tolydžiosios matematikos priemonės – išvestinės, integralai. Kombinatorika yra labiau linkusi siūlyti specifiniu‘ matematikos uždaviniu‘ sprendimo būdus,
nei savintis pačius tyrimo objektus. Ji siūlo principus, metodus, be kuriu‘ neišsiverčia
šiuolaikinė matematika ar informatika. Iš kombinatorikos išsikristalizavo atskiros šakos
ir tapo diskrečiosios matematikos disciplinomis. Taip atsitiko su grafu‘ teorija, kodavimo
teorija.
Matematika ir juo labiau informatika nemėgsta dviprasmybiu‘, negriežtu‘ teiginiu‘.
Tad ir šiame kurse formaliai i‘rodinėsime sudėtingesnius ar paprastesnius teiginius. Be
išsamesniu‘ komentaru‘ remsimės matematinės logikos kurse sužinotais dalykais bei dėsniais.
Štai pora pavyzdžiu‘:
Neprieštaringumo dėsnis. Du vienas kitam priešingi teiginiai p ir p̄ vienu metu
negali būti teisingi (p ∧ p̄ = 0).
Trečiojo negalimo dėsnis. Iš dvieju‘ priešingu‘ teiginiu‘ p ir p̄ vienas visada yra
teisingas (p ∧ p̄ = 1).
Didele‘ kurso dali‘ skirsime tam tikru‘ aibiu‘ elementu‘ skaičiui nustatyti. Siekdami universalumo, neišvengsime pasakymu‘: ,,su visais natūraliaisiais skaičiais n teisinga...“, todėl
2

svarbu prisiminti matematinės indukcijos principus. Jie kyla iš paties natūraliu‘ju‘ skaičiu‘
aibės aksiominio apibrėžimo. Vokiečiu‘ matematikui L.Kronekeriui (L.Kronecker, 1823–
1891) priskiriamas toks pasakymas: ,,Dievas sukūrė skaičius, visa kita yra žmogaus darbas”. Manoma, kad omenyje buvo turėti natūralieji skaičiai. Bet ir juos apibrėžiant žmogus
i‘vedė tvarka‘. Štai bene populiariausios G.Peano (Giuseppe Peano, 1858–1932) aksiomos:
Apibrėžimas. Natūraliaisiais skaičiais vadiname netuščios aibės N elementus, jeigu
tarp kai kuriu‘ iš ju‘ egzistuoja sa‘ ryšis ,,a0 eina po a“, tenkinantis aksiomas:
1) egzistuoja elementas (vadinamas vienetu), neinantis po jokio kito elemento;
2) po kiekvieno elemento eina tik vienas elementas;
3) kiekvienas elementas eina ne daugiau kaip po vieno elemento;
4) aibės N poaibis M sutampa su pačia aibe N, jei jis turi tokias savybes:
a) 1 ∈ M,
b) jeigu elementas a priklauso M, tai ir po a einantis elementas a0 taip
pat
priklauso aibei M.
Aibės N elementus 1, 10 , (10 )0 ..., dabar vadinkime skaičiais ir naujai pažymėkime 1, 2,
3,... Paskutinė aksioma vadinama indukcijos aksioma, pirma‘kart 1988 metais ja‘ kartu
su kitomis aibės N aksiomomis suformulavo vokiečiu‘ matematikas R. Dedekindas (R.
Dedekind, 1831–1916), nors pati‘ principa‘ jau naudojo B. Paskalis (B. Pascal, 1623–1662).
Mūsu‘ kurse indukcijos principas dažniausiai bus naudojamas tokia forma:
Tegu p(n) – kažkoks teiginys apie natūralu‘ ji‘ skaičiu‘ n. Tarkime, kad p(1) yra teisingas, ir iš prielaidos, kad p(n) yra teisingas, sugebame išvesti, kad p(n0 ) irgi yra teisingas.
Darome išvada‘ : teiginys p(n) yra teisingas visiems n ∈ N.
Žvilgtelėkime, kaip aksiomiškai apibrėžtoje aibėje N galėtume apibrėžti sudėties operacija‘. Apibrėžkime
a + 1 = a0 ;
toliau, tare‘, kad a + n žinoma, apibrėžiame
a + (n + 1) = a + n0 := (a + n)0 .
Skaičiu‘ aibė M = {n} tenkina abu 4) aksiomos reikalavimus, todėl iš jos išplaukia, kad M
sutampa su natūraliu‘ju‘ skaičiu‘ aibe. Kitaip tariant, a + n apibrėžta su visais n. Panašiai
apibrėžiant daugyba‘ pradedama nuo
a · 1 = a,

b0 · a = a · b + a.

Te‘siant gaunama algebrinė struktūra N, t.y. aibė su joje apibrėžtomis algebrinėmis
operacijomis. Aksiomos, žinoma, užsimiršta ir natūraliuosius skaičius naudojame, kaip
,,Dievo duotus”.
Pastebėkime, kad N yra sutvarkytoji aibė: a < b apibrėžiama kaip ,,∃d ∈ N toks, kad
a + d = b“.
Galimos ir kitos aksiomu‘ sistemos. Kai kuriose iš ju‘ randame toki‘ teigini‘.
3

Archimedo aksioma. Bet kuriai natūraliu‘ ju‘ skaičiu‘ porai a, b galima rasti toki‘
natūralu‘ ji‘ skaičiu‘ n, kad an > b.
Šis teiginys išplaukia iš Peano aksiomu‘, todėl ji‘ reiktu‘ vadinti teorema, tačiau taip ir
liko istoriškai susikloste‘s pavadinimas. Panašiai prigijo ir toks teiginys.
Mažiausiojo elemento principas. Kiekvienas netuščias natūraliu‘ ju‘ skaičiu‘ aibės
poaibis turi mažiausia‘ elementa‘ .
Plačiau apsistokime ties labai akivaizdžiu ”dėžučiu‘” arba Dirichlė (P.G.L. Dirichlet,
1805–1859) suformuluotu teiginiu.
Dirichlė principas. Jei m rutuliu‘ yra sudėti ‘i n < m dėžiu‘ , tai bent vienoje dėžėje
yra 2 ar daugiau rutuliu‘ .
Nevisada šio principo pritaikymas yra toks akivaizdus. Palyginkime du elementariosios skaičiu‘ teorijos teiginius.
1 pvz. Bet kokiame (n + 1)-o elemento poaibyje, išrinktame iš {1, 2, . . . , 2n} yra bent
du tarpusavyje pirminiai skaičiai.
I‘ sitikinkite savarankiškai.
2 pvz. Bet kokiame (n + 1)-o elemento poaibyje, išrinktame iš {1, 2, . . . , 2n} yra bent
du vienas kita‘ dalijantys skaičiai.
Irodymas. Jei A yra išrinktasis poaibis, turintis (n + 1)-a‘ elementa‘. Kiekviena‘ a ∈ A
‘
galime išreikšti a = 2k b su k ≥ 0 ir nelyginiu skaičiumi b. Todėl b ∈ {1, 3, . . . , 2n − 1}. Yra
tik n galimybiu‘ šiai nelyginei skaičiaus a daliai. Vadinasi, pagal Dirichlė principa‘ bent du
aibės A skaičiai turės ta‘ pačia‘ nelygine‘ dali‘. Kadangi vienas iš skaičiu‘ 2s b ir 2k b su k, s ≥ 0
dalija kita‘, mūsu‘ tvirtinimas yra i‘rodytas.
Matematikoje dažnai sutinkami ir kitokie šio teiginio variantai. Dažniausiai jis formuluojamas baigtiniu‘ aibiu‘ atvaizdžiams. I‘ sivaizduokite atvaizdi‘, rutuliui priskirianti‘ dėžute‘,
i‘ kuria‘ jis i‘dedamas, ir performuluokite Dirichlė principa‘! Mes ji‘ net šiek tiek sustiprinsime.
Tegu |M | žymi baigtinės aibės M elementu‘ skaičiu‘ (dažnai naudojamas ir žymuo
#M ). Jei f : M → N - atvaizdis, ir a ∈ N , tai jo pirmvaizdžiu‘ aibe‘ pažymėkime f −1 (a).
Kitaip tariant,
f −1 (a) = {b ∈ M : f (b) = a}.
Iš atvaizdžio apibrėžimo turime, kad f −1 (a) ∩ f −1 (a0 ) = ∅, jei a 6= a0 . Be to,
[
M=
f −1 (a)
a

ir
(1)

|M | =

X

|f −1 (a)|.

a

1 teorema. Tarkime, kad M, N dvi aibės, |M | = m > n = |N | ir f : M → N atvaizdis. Tada egzistuoja a ∈ N toks, kad
(2)

|f −1 (a)| ≥ dm/ne.
4

Čia due = min{k ∈ N : k ≥ u} - mažiausias sveikasis skaičius, nemažesnis už u.
Irodymas. Nagrinėjamu atveju iš dėžučiu‘ principo išplauktu‘ tik nelygybė |f −1 (a)| ≥ 2.
Pastebėkime, kad prielaida, jog |f −1 (a)| < m/n kiekvienam a ∈ N ir (1) lygybė
negalima dėl šios prieštaros:
‘

m=

X

|f −1 (a)| <

a

Taigi bent vienam a turi būti |f −1 (a)| ≥
teorema i‘rodyta.

m
n.

m
n = m.
n

Kadangi |f −1 (a)| - natūralusis skaičius,

Dažna programavimo užduotis reikalauja iš baigtinės realiu‘ju‘ skaičiu‘ sekos išrinkti
monotoniška‘ poseki‘. Kaip galėtume i‘vertinti tokiu‘ posekiu‘ ilgi‘?
2 teorema. Tegu m, n ∈ N ir a1 , a2 , . . . , amn+1 bet kokia skirtingu‘ realiu‘ ju‘ skaičiu‘
seka iš (mn + 1)-o elemento. Joje egzistuoja monotoniškai didėjantis (n + 1)-o elemento
posekis arba monotoniškai mažėjantis (m + 1)-o elemento posekis. Galimi ir abu variantai.
Irodymas. Dabar Dirichlė principo taikymo galimybė vargu ar i‘žiūrima. Reikia i‘rodyti
posekiu‘
ai1 < ai2 < · · · < ain+1 ,
1 ≤ i1 < i2 < · · · < in+1 ≤ mn + 1
‘

arba
aj1 > aj2 > · · · > ajm+1 ,

1 ≤ j1 < j2 < · · · < jm+1 ≤ mn + 1

egzistavima‘. Imkime bet kuri‘ sekos elementa‘ ai , 1 ≤ i ≤ mn + 1. Tegu ti - ilgiausio
didėjančio posekio, prasidedančio ai , ilgis. Jei kažkokiam ti ≥ n + 1, teorema i‘rodyta.
Tegu dabar ti ≤ n visiems i. Atvaizdžiui f : ai 7→ ti , vaizduojančiam aibe‘ M :=
{a1 , a2 , . . . , amn+1 } aibėje N := {1, 2, . . . , n}, galime pritaikyti 1 teorema‘. Šiuo atveju iš
(2) lygybės gauname, kad egsistuoja s ∈ N toks, kad f (ai ) = s dėl
»

¼
mn + 1
=m+1
n

skaičiu‘ ai . Nekeisdami ju‘ išsidėstymo tvarkos sekoje, sužymėkime
aj1 , aj2 , . . . , ajm+1 ,

1 ≤ j1 < j2 < · · · < jm+1 ≤ mn + 1.

Imkime du gretimus šio posekio narius ajk ir ajk+1 . Jei kažkokiai porai ajk < ajk+1 ,
tai pradėdami ajk -uoju ir prijungdami didėjanti‘ poseki‘, prasidedanti‘ nuo ajk+1 ir turinti‘
s nariu‘, gautume didėjanti‘ poseki‘, prasidedanti‘ ajk , jau iš (s + 1)-o elemento. Bet tai
prieštara. Vadinasi, ajk > ajk+1 su bet kokais 1 ≤ k ≤ m + 1. Taigi, išrinkome (m + 1)-o
elemento mažėjanti‘ poseki‘.
Teorema i‘rodyta.
5

2. Dauginimo taisyklė. ,,Skaičiuok dukart” principas
Aibe‘ A = {a1 , . . . , an } vadinsime n aibe. Tad |A| = n yra jos galia. Toliau nagrinėsime,
kokiais būdais nustatomas i‘vairiu‘ baigtiniu‘ aibiu‘ elementu‘ skaičius. Ka‘ tas reiškia matematine kalba? Vienam elementui priskiriame skaičiu‘ 1 (prirašome numeri‘ ar indeksa‘), kitam
– 2 ir taip toliau te‘sdami aibėje A apibrėžiame abipus vienareikšme‘ (bijektyvia‘) funkcija‘
f : A → N su savybe |f (A)| = |A|. Didžiausias numeris yra ieškomoji aibės galia. Iš čia
išplaukia svarbus
Bijektyviu‘ aibiu‘ galios principas. Jei A ir B yra baigtinės aibės ir galime apibrėžti
bijekcija‘ f : A → B, tai ju‘ galios sutampa, t.y. |A| = |B|.
Praktiškai tai reiškia, kad skaičiuojant sudėtingai apibrėžtos A aibės elementus, yra
tikslinga paieškoti bijektyvios jai paprastesnės aibės (kodu‘ aibės).
Atkreipkime dar dėmesi‘ i‘ tai, kad terminus aibė, poaibis vartojame, kai ju‘ elementai
yra skirtingi, kitais atvejais – pora, rinkinys, sistema, visuma.
Aibės elementus dažnai yra patogu vadinti abėcėle, iš ju‘ sudarytus sutvarkytuosius
rinkinius – žodžiais. Pabrėždami ilgi‘, žodi‘ (ai1 , . . . , aik ) vadinsime k žodžiu. Jei A =
{a1 , . . . , an } ir B = {b1 , . . . , bm } yra dvi aibės, tai aibė
A × B = {(ai , bj ) : ai ∈ A, bj ∈ B, 1 ≤ i ≤ n, 1 ≤ j ≤ m}
vadinama ju‘ Dekarto ( René Descartes, 1596–1650) sandauga. Tai sutvarkytu‘ ju‘ poru‘ aibė.
1 teorema. |A × B| = |A| |B|.
.Tarkime, kad A yra n aibė, o B – m aibė. Su fiksuotu elementu ai iš poru‘ (ai , bj )
galime sudaryti m poaibi‘, kai j = 1, . . . , m. Dabar keiskime ai , imdami i = 1, . . . , n.
Gausime n poru‘ m poaibiu‘. Todėl |A × B| = nm. /
Taikydami matematine‘ indukcija‘, apibendrinkite ši‘ teigini‘ bet kurio skaičiaus aibiu‘
Dekarto sandaugai: |A1 × · · · × As | = |A1 | × · · · × |As |, s ≥ 1.
2 teorema. Jei abėcėlė A turi n raidžiu‘ , tai galime sudaryti nk žodžiu‘ , kuriu‘ ilgis
yra k.
.Pastebėkime, kad k žodžiu‘ aibė sutampa su Dekarto sandauga A × · · · × A, turinčia
k daugikliu‘. Todėl teiginys išplaukia iš 1 teoremos apibendrinimo. /
3 teorema. Aibės A = {a1 , . . . , an } poaibiu‘ , ‘iskaitant ir tuščia‘ ji‘ , skaičius lygus 2n .
.Nagrinėkime visu‘ poaibiu‘ aibės atvaizdi‘ aibėje, sudarytoje iš n žodžiu‘ su ,,raidėmis“
0, 1. Šis atvaizdis apibrėžtas taip:
A ⊃ P = {ai1 , . . . , aik } 7→ (0 . . . , 0, 1, 0 . . . , 0, 1, 0, . . . 0);
čia ,,raidė“ 1 i‘rašyta is -oje pozicijoje pabrėžiant, kad is -asis aibės A elementas patenka i‘
poaibi‘ P . Atvaizdis yra bijekcija. Pagal 2 teorema‘ šiu‘ žodžiu‘ aibės galia lygi 2n ir sutampa
su k poaibiu‘ aibės galia. /
4 teorema. Jei X = {x1 , . . . , xn } ir Y = {y1 , . . . , ym }, tai funkciju‘ f : X → Y aibės
galia lygi mn .
6

.Kiekviena‘ funkcija‘ f : X → Y galime vienareikšmiškai išreikšti vektoriumi
(f (x1 ), . . . , f (xn )). Kadangi dabar ,,raidė“ f (xj ), 1 ≤ j ≤ n, imama iš abėcėlės Y ,
turinčios m raidžiu‘, teoremos teiginys išplaukia iš 2 teoremos. /
Šioje teoremoje išvesta formulė paaiškina dažnai naudojama‘ žymeni‘
{f : X → Y } =: Y X .
Diskrečioje matematikoje kaip ir gyvenime yra labai naudingas ,, skaičiuok dukart”
principas: tos pačios aibės elementus perskaičiuok dukart. Geriau tai atlik skirtingais
būdais. Šia‘ idėja‘ formalizuokime.
Tegu A ir B yra dvi aibės, o S ⊂ A × B – poaibis. Jis vadinamas sa‘ ryšiu. Jei a ∈ A,
b ∈ b ir (a, b) ∈ S, tai sakoma, kad a ir b susieti sa‘ryšiu S. Moksliškiau kalbant, sakytume:
yra incidentūs S. Tegu ra yra skaičius tokiu‘ b ∈ B, kad (a, b) ∈ S ir qb – skaičius tokiu‘
a ∈ A, kad (a, b) ∈ S. Mūsu‘ aptariamasis principas turi tokia‘ formalia‘ išraiška‘:
X

(1)

X

ra = |S| =

a∈A

1=

X

qb .

b∈B

(a,b)∈S

Čia vidinė dvilypė suma yra išreikšta kartotinėmis sumomis su skirtinga sumavimo tvarka
ir nieko i‘rodinėti nereikia.
Vėl panagrinėkime pora‘ paprastu‘ pavyzdžiu‘.
1 pavyzdys. Tegu A = {1, . . . n} = B, o S = {(m, d) : d|m}, čia d|m reiškia ”d
dalija m”. Formulė (2.1) dabar atrodytu‘ taip:
XX

X

1=

m≤n d|m

1=

d,m≤n
d|m

X

X

d≤n

m≤n
m≡0(modd)

1.

Jei d(m) žymėtu‘ skaičiaus m natūraliu‘ju‘ dalikliu‘ skaičiu‘, o [u] – realaus skaičiaus sveika‘ja‘
dali‘, tai iš čia išvestume formule‘
X
m≤n

d(m) =

µX ¶
X1
=n
+O
1 = n log n + O(n).
d
d

X £n¤
d≤n

d≤n

d≤n

Skaitytojui, žinančiam pora‘ pradiniu‘ grafu‘ teorijos sa‘voku‘, pateiksime viena‘ pavyzdi‘.
2 pavyzdys. Nagrinėkime grafa‘ G = (V, E) su viršūnėmis v ∈ V ir briaunomis e ∈ E.
Tegu S = {(v, e) : v incidenti briaunai e}. Tada
δ(v) =

X

1

−

e
e inc. v

7

viršūnės laipsnis,

o

X

1 = 2,

v
v inc. e

nes tik dvi viršūnės yra incidenčios briaunai. Todėl (1) i‘rodo Eulerio ”delnu‘ paspaudimo”
lema‘:
X
X
δ(v) = 2
1 = 2|E|.
v∈V

e∈E

,, Skaičiuok dukart” principas yra labai patogus išvedant lygybes, juo vėliau dažnai
naudosimės.
3. Gretiniai, kėliniai ir deriniai
Abėcėlės A = {a1 , . . . , an } skirtingu‘ raidžiu‘ žodžius vadinsime gretiniais iš n elementu‘. Jei
tokio žodžio ilgis yra k, tai ji‘ vadinsime k gretiniu. Ju‘ skaičiu‘ pažymėkime Akn .
1 teorema. Akn = n(n − 1)(n − 2) · · · (n − k + 1).
I‘ rodymas akivaizdus.
Gretinius iš n elementu‘ po n vadinsime kėliniais.
Išvada. Iš viso yra n! kėliniu‘ iš n aibės elementu‘.
Raidžiu‘ tvarka k žodyje yra svarbi. Iš visu‘ k! žodžiu‘, sudarytu‘ iš tu‘ pačiu‘ raidžiu‘,
gautume ta‘ pati‘ k nesutvarkyta‘ ji‘ skirtingu‘ raidžiu‘ rinkini‘ (poaibi‘), vadinama‘ deriniu.
2 teorema. Deriniu‘ iš n po k skaičius lygus
Cnk =

Akn
n!
=
.
k!
k!(n − k)!

.I‘ rodymas išplaukia iš 1 teoremos ir kėliniu‘ skaičiaus formulės./
Deriniu‘ skaičius Cnk nurodo, kiek k poaibiu‘ galime išrinkti iš n aibės. Kadangi k =
0, 1, . . . , n, tai pagal 2.3 teorema‘ gauname tapatybe‘
(1)

Cn0 + Cn1 + · · · + Cnn = 2n .

Čia n bet koks natūralusis skaičius.
Išvedant (1) lygybe‘, buvo panaudotas labai universalus principas: skaičiuojant kažkokios baigtinės aibės galia‘ keliais būdais rezultatas yra tas pats. Ji‘ sutiksite ir ateityje.
Mokslinėje literatūroje vartojami ir tokie deriniu‘ iš n po k žymemys:
µ ¶ µ
¶
n
n
=
.
k
k, n − k
Pastara‘ji‘ lengviau apibendrinti.
8

Uždavinys. Kiek skirtingu‘ pirkiniu‘ iš k prekiu‘ sudarytume, jei galėtume rinktis iš n
prekiu‘ rūšiu‘ be apribojimu‘?
Sprendimas. Sunumeruokime visas n prekiu‘ rūšis ir sudarykime pirkinio koda‘: rašykime tiek vienetu‘, kiek imame pirmos rūšies prekiu‘, dėkime vertikalu‘ brūkšni‘ ir te‘skime ši‘
procesa‘. Baigsime paraše‘ tiek vienetu‘, kiek imsime n-os rūšies prekiu‘. Taigi kodas atrodys
maždaug šitaip:
11||111| . . . |1 .
Matome, kad šiame pirkinyje yra dvi pirmos rūšies prekės, 2-os rūšies prekiu‘ nebuvo imta.
Koda‘ sudarys k vienetu‘ ir n − 1 vertikalus brūkšnys. Jis vienareikšmiškai nusako pirkini‘.
Todėl pirkiniu‘ galėsime sudaryti tiek, kiek bus tokiu‘ kodu‘. Kodai yra n − 1 + k žodžiai,
turintys viena‘ apribojima‘ – vienetu‘ skaičiu‘, lygu‘ k. Kadangi vienetu‘ padėtis kode vienk
areikšmiškai ji‘ nusako, o tokiu‘ padėčiu‘ galime išrinkti Cn+k−1
būdais, tai šis binominis
koeficientas ir yra uždavinio atsakymas.
Paimtas iš n aibės k elementu‘ rinkinys su galimais pasikartojimais vadinamas kartotiniu šios aibės k deriniu. Ju‘ skaičius
µ
¶
n+k−1
k
k
Hn = Cn+k−1 =
.
k
Pastebėkime, kad spre‘sdami pirkiniu‘ uždavini‘, suradome lygties
x1 + · · · + xn = k
sprendiniu‘ sveikais neneigiamais skaičiais kieki‘. Jis irgi lygus Hnk .
Apibendrindami jau turima‘ medžiaga‘, sudarome k raidžiu‘ išrinkimo iš n abėcėlės
skaičiu‘ lentele‘:
Sutvarkytieji rinkiniai (žodžiai)
Skirtingi
Galimi pasikartojimai

gretiniai, Akn
k žodžiai, nk

Nesutvarkytieji rinkiniai
deriniai, Cnk
k
kartotiniai derin., Cn+k−1
.

Šioje lentelėje ,,netilpo” dar vieno tipo rinkiniu̧ suskaičiavimo formulė.
4. Kartotiniai gretiniai
Apibendrinkime Niutono binomo formule‘

n µ ¶
X
n p n−p
(a + b) =
a b
,
p
p=0
n

keldami k nežinomu‘ju‘ suma‘ n ≥ 2 laipsniu. Tegu
¶
Xµ
n
n
(1)
(x1 + · · · + xk ) =
xp11 · · · xpkk .
p1 , . . . , pk
p̄
9

Čia sumuojama pagal visus vektorius p̄ = (p1 , . . . , pk ) su sveikomis neneigiamomis koordinatėmis, tenkinančiomis sa‘lyga‘ p1 + · · · + pk = n. (1) formulėje apibrėžtus
¡n¢ ¡koeficientus
¢
n
vadinkime polinominiais koeficientais. Kai k = 2, turime susitarti, kad p = p,n−p
.
Teorema. Polinominiu‘ koeficientu‘ formulė yra
¶
µ
n
n!
=
.
p1 , . . . , pk
p1 ! · · · pk !
.Dauginkime panariui n nežinomu‘ju‘ sumu‘, imdami xi1 iš pirmosios sumos, xi2 iš
antrosios sumos ir t.t., xin iš n-osios sumos ir sudėkime visas sandaugas
(2)

xi1 · · · xin .

Kadangi ij ∈ {1, . . . , k}, 1 ≤ j ≤ n, tai turėsime k n sandaugu‘ (visus n žodžius iš k raidžiu‘
x1 , . . . , xk ). Sudedant (2) sandaugas, reikia sutraukti panašius narius. Jie bus to paties
pavidalo, t.y.
xp11 · · · xpkk ,

(3)

nusakomo vektoriumi p̄. Kiek tokiu‘ panašiu
¡‘ nnariu
¢ ‘ kaip (3)? ¡Raidė
¢ x1 (2) sandaugoje galėjo
n−p1
užimti p1 poziciju‘ iš n galimu‘, t.y. buvo p1 būdu‘, x2 – p2 būdu‘ ir t.t. Te‘sdami ši‘
procesa‘, gautume
µ ¶ µ
¶ µ
¶
n
n − p1
n − p1 − p2 − · · · − pk−1
n!
·
···
=
.
p1
p2
pk
p1 ! . . . pk !
Čia pasinaudojome binominio koeficiento formule. /
Iš abėcėlės {x1 , . . . , xk } sudarykime n žodžius, kuriuose xj pasirodytu‘ pj , 1 ≤ j ≤ k,
kartu‘. Jie vadinami kartotiniais gretiniais. Ju‘ kieki‘ skaičiavome i‘rodydami teorema‘. Iš
tiesu‘ (2) žodžiu‘, užrašytu‘ dar ir (3) būdu, skaičius buvo polinominis koeficientas.
Uždavinys. Keliais būdais galime suskirstyti n aibe‘ i‘ k nesikertančiu‘ poaibiu‘, jei
reikalaujame, kad i‘ j-a‘ja‘ pakliūtu‘ pj elementu‘? Čia p1 + · · · + pk = n, pj ≥ 0, 1 ≤ j ≤ k.
Sprendimas. Pritaikykite teoremos i‘rodyme naudotus samprotavimus. /
Atkreipkime dėmesi‘ i‘ šia‘ (1) lygybės išvada‘:
n

k =

Xµ
p̄

¶
n
,
p1 , . . . , pk

gaunama‘ i‘statant xj ≡ 1. Čia, kaip ir anksčiau sumuojama pagal visus vektorius p̄ =
(p1 , . . . , pk ) su neneigiamomis komponentėmis, tenkinančius sa‘lyga‘ p1 + · · · + pk = n.
10

5. Binominiu‘ koeficientu‘ tapatybės
Patogu išplėsti binominio koeficiento apibrėžima‘:
µ ¶ ½ z(z−1)...(z−k+1)
z
, kai
k!
=
k
0,
kai k < 0.
1 teorema.

¶
µ ¶ µ
n
n
=
,
k
n−k

z ∈ C, k ∈ N ∪ {0},

0 ≤ k ≤ n.

2 teorema.
Hnk

µ
¶
µ ¶
n+k−1
k −n
=
= (−1)
,
k
k

0 ≤ k ≤ n.

3 teorema.
µ ¶µ ¶ µ ¶µ
¶
n
k
n
n−m
=
,
k
m
m k−m

0 ≤ m ≤ k ≤ n.

.Visi šie teiginiai patikrinami panaudojant binominio koeficiento formule‘. Pvz., 3
teoremos atveju, kairioji pusė lygi
k!
n!
1
(n − m)!
n!
·
=
·
·
=
k!(n − k)! m!(k − m)!
(n − k)! m!(k − m)! (n − m)!
µ ¶µ
¶
n!
(n − m)!
n
n−m
=
·
=
.
m!(n − m)! (k − m)!((n − m) − (k − m))!
m k−m
/
4 teorema (Paskalio tapatybė).
µ ¶ µ
¶ µ
¶
n
n−1
n−1
=
+
,
k
k−1
k

0 ≤ k ≤ n,

µ
¶
n−1
= 0.
n

.Fiksuokime abėcėlės A viena‘ elementa‘, sakykim, a1 ir visus k derinius suskirstykim
i‘ dvi klases: vienos klasės deriniuose tegu bus a1 , kitos - ne. Pastebėkime, kad išvedamos
formulės dešinioji pusė - tu‘ klasiu‘ deriniu‘ skaičiu‘ suma. Turime gauti visus k derinius iš n
elementu‘. /
5 teorema.
¶ µ
¶
n µ
X
r+k
r+n+1
=
.
k
n
k=0

.Pritaikykite matematine‘ indukcija‘ ir Paskalio tapatybe‘. /
11

6 teorema (Ortogonalumo sa‘ryšis) Tegu δmn - Kronekerio simbolis, t.y. δnn = 1
ir δmn = 0, kai m 6= n. Jei m ≤ n, tai
Snm :=

n
X
k=m

µ ¶µ ¶
n
k
(−1)
= (−1)m δmn .
k
m
k

.Pagal 3 teorema‘
Snm =

n
X
k=m

µ ¶µ
¶ µ ¶X
µ
¶
n
n
n−m
n
k n−m
(−1)
=
(−1)
.
m k−m
m
k−m
k

k=m

Pakeiskime sumavimo indeksa‘ k − m = j ir gausime
Snm

µ ¶ n−m
µ
¶
µ ¶
n X
j+m n − m
m n
=
(−1)
= (−1)
(1 − 1)n−m = 0,
m j=0
j
m

jei m 6= n./
7 teorema (Apgre‘žimo sa‘ryšis) Tegu ak , bk , 0 ≤ k ≤ n - dvi skaičiu‘ sekos. Iš
vienos iš šiu‘ lygybiu‘
µ ¶
n
X
k n
bn =
(−1)
ak ,
k
k=0

an =

n
X
k=0

µ ¶
n
(−1)
bk
k
k

išplaukia antroji.
.Jei teisinga pirmoji lygybė, tai i‘statydami patikriname antra‘ja‘. Skaičiuojame keisdami sumavimo tvarka‘
µ ¶
µ ¶
µ ¶µ X
k
n
X
n
m k
k n
(−1)
am =
(−1)
bk =
(−1)
m
k
k
m=0
k=0
k=0
µ ¶µ ¶
n
n
X
X
k
m
k n
=
(−1) am
(−1)
= an δnn = an .
k
m
m=0
n
X

k

k=m

Paskutiniame žingsnyje pritaikėme ortogonalumo sa‘ryši‘ (6 teorema‘). /
8 teorema (Harmoniniu‘ skaičiu‘ savybė).
µ ¶
n
X
1
1
k+1 n 1
1 + + ··· + =
(−1)
.
2
n
k k
k=1

12

.Dešiniojoje lygybės pusėje esančiam binominiam koeficientui pritaikykime Paskalio
lygybe‘. Gauname
(1)

µ ¶
µµ
¶ µ
¶¶
n
n 1 X
n−1
n−1
1
k+1
(−1)
(−1)
hn : =
=
+
=
k k
k
k−1
k
k=1
k=1
µ
¶
µ
¶
n
X
n+1 n − 1 1
k+1 n − 1 1
= hn−1 + (−1)
+
(−1)
.
n
n
k−1 k
n
X

k+1

k=1

Antrasis dėmuo lygus nuliui, skaičiuojame trečia‘ji‘. Jis lygus
n
X

(−1)

k=1

k+1

µ ¶
n
1X
1
1
(n − 1)!
k n
=−
(−1)
= − [(1 − 1)n − 1] = .
k!(n − k)!
n
k
n
n
k=1

I‘ state‘ i‘ (1) lygybe‘ gauname rekurentu‘ji‘ sa‘ryši‘
hn = hn−1 +

1
.
n

Kadangi f1 = 1, pagal matematinės indukcijos principa‘ iš jo išplaukia
hn = 1 +

1 1
1
+ + ··· + .
2 3
n
/

Išvada.

n
X

(−1)

k=1

k+1

µ ¶
n
1
hk = .
k
n

.Papildykite sumas nuliniais dėmenimis (h0 = 0) ir pritaikykite apgre‘žimo formule‘. /
6. Rėčio principas
Skaičiuosime skaičiu‘ elementu‘, patenkančiu‘ i‘ keletos gal būt persikertančiu‘ aibiu‘
sa‘junga‘. Apibendrinsime nesunkiai suvokiamas formules
|A ∪ B| = |A| + |B| − |A ∩ B|
ir
(1)

|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.

Jiems išvesti pakanka grafinės iliustracijos.
Panagrinėkime pavyzdi‘, pateikta‘ M.Bloznelio knygutėje, pakeisdami skaičius.
13

Uždavinys. Kiek sveiku‘ ju‘ sprendiniu‘ (sutvarkytu‘ ju‘ trejetu‘ (x01 , x02 , x03 ), yi ≥ 0, i =
1, 2, 3 ), tenkinančiu‘ sa‘ lygas
−4 ≤ x1 ≤ 2;

0 < x2 ≤ 8;

4 ≤ x3 ≤ 5,

turi lygtis
(2)

x1 + x2 + x3 = 10 ?

Sprendimas. Kadangi esame nagrinėje‘ panašiu‘ lygčiu‘ sveiku‘ju‘ neneigiamu‘ sprendiniu‘
skaičiu‘, todėl pakeičiame nežinomuosius
x1 + 4 = y1 ,

x2 − 1 = y2 ,

x3 − 4 = y3 ,

ir gauname lygti‘
(3)

y1 + y2 + y3 = 9.

Jos sprendiniu‘, tenkinančiu‘ sa‘lygas
(4)

0 ≤ y1 ≤ 6;

0 ≤ y2 ≤ 7;

0 ≤ y3 ≤ 1,

bus tiek pat kiek pradinio uždavinio sprendiniu‘. Jei nebūtu‘ (4) apribojimu‘, (3) lygtis
turėtu‘
µ ¶ µ ¶
11
11
9
H3 =
=
= 55
9
2
sveikuosius neneigiamus sprendinius. Taigi reikia ,,atsijoti“ sprendinius, netenkinančius
(4) sa‘lygu‘. Raide U pažymėkime (3) lygties sprendiniu‘ aibe‘, A1 – jos poaibi‘, netenkinanti‘
sa‘lygos 0 ≤ y1 ≤ 6, A2 – poaibi‘, netenkinanti‘ sa‘lygos 0 ≤ y2 ≤ 7, ir A3 – poaibi‘,
netenkinanti‘ sa‘lygos 0 ≤ y3 ≤ 1. Aibiu‘ sa‘jungos S := A1 ∪ A2 ∪ A3 elementus ir reikia
išsijoti iš U . Likusios aibės U \ S elementai tenkina visas (4) sa‘lygas.
Randame sankirtu‘ galias:
|A1 ∩ A2 | = 0;
|A1 ∩ A3 | = 1,
nes yra vienas sprendinys (7,0,2);
|A2 ∩ A3 | = 0.
Panašiai |A1 ∩ A2 ∩ A3 | = 0.
Po pakeitimo
y1 − 7 = z1 , y2 = z2 , y3 = z3
14

|A1 | lygus lygties z1 + z2 + z3 = 2 sveiku‘ju‘ neneigiamu‘ sprendiniu‘ skaičiui, t.y. |A1 | =
H32 = 6; panašiai, |A2 | = H31 = 3 ir
|A3 | =

H37

µ ¶ µ ¶
9
9
=
=
= 36.
7
2

I‘ statydami gautuosius skaičius i‘ (1) formule‘, gauname
|U | − |S| = 55 − (6 + 3 + 36 − 1) = 11
uždavinio sprendiniu‘. /
Trumpesnis kelias: ieškodami (3) lygties sveiku‘ju‘ neneigiamu‘ sprendiniu‘, sudėkime
tiek vienetu‘, kiek ju‘ yra
X
X
1=
1.
0≤y1 ≤6
0≤y2 ≤7
8≤y1 +y2 ≤9

(y1 ,y2 ,y3 )
(3),(4)

I‘ žiūrėkime šios sumos geometrine‘ prasme‘. Tai plokštumos tašku‘, kuriu‘ koordinatės tenkina
nurodytas sa‘lygas, skaičius. Brėžinyje gausime tam tikra‘ sriti‘. Joje, i‘skaitant ir kontūra‘,
”telpa” 11 tašku‘ su sveikomis koordinatėmis. /
Gri‘žkime prie teoriniu‘ dalyku‘ ir raskime elementu‘ skaičiu‘ sa‘jungoje
A1 ∪ · · · ∪ An .
Pažymėkime
a(i) = |Ai |,

a(i, j) = |Ai ∩ Aj |,

...

,

a(i1 , . . . , ik ) = |Ai1 ∩ · · · ∩ Aik |.

Čia 1 ≤ i < j, i1 < · · · < ik , 1 ≤ k ≤ n. Viso yra Cn2 galimybiu‘ parinkti nesutvarkyta‘ja‘
skirtingu‘ indeksu‘ pora‘ (i, j), panašiai, – Cnk galimybiu‘ parinkti k skirtingu‘ indeksu‘. Trumpumo dėlei apibrėžkime sumas
S1 =

n
X

a(i),

i=1

S2 =

X

a(i, j),

...

1≤i<j≤n

,

Sk =

X

a(i1 , . . . , ik ).

1≤i1 <i2 <···<ik ≤n

čia 1 ≤ k ≤ n. Pabrėžiame, kad Sk sumoje sumuojama pagal visus galimus indeksu‘ k
poaibius iš pirmu‘ju‘ n natūraliu‘ju‘ skaičiu‘.
1 teorema.
|A1 ∪ · · · ∪ An | = S1 − S2 + S3 + · · · + (−1)n+1 Sn .
15

.Pažymėkime U = A1 ∪ · · · ∪ An . Fukcija‘ IA : U → {0, 1} vadinsime poaibio A ⊂ U
indikatoriumi, jeigu IA (x) = 1 tada ir tik tada, kai x ∈ A. Vadinasi,
X

|A| =

IA (x).

x∈U

Todėl
a(i) =

X

IAi (x),

x∈U

a(i1 , . . . , ik ) =

X

a(i, j) =

X

IAi ∩Aj (x), . . . ,

x∈U

IAi1 ∩···∩Aik (x),

1 ≤ i < j, i1 < · · · < ik .

x∈U

Vadinasi,

X

Sk =

X

IAi1 ∩···∩Aik (x),

1 ≤ k ≤ n.

1≤i1 <i2 <···<ik ≤n x∈U

Pažymėkime

X

Zk (x) =

IAi1 ∩···∩Aik (x).

1≤i1 <i2 <···<ik ≤n

Sukeite‘ sumavimo tvarka‘, šiu‘ žymėjimu‘ dėka gauname
n+1

S1 − S2 + S3 + · · · + (−1)

Sn =

n
XX

(−1)k+1 Zk (x).

x∈U k=1

Reikia i‘sitikinti, jog ši suma lygi
|U | =

X

IU (x)

x∈U

arba i‘rodyti dėmenu‘ lygybe‘
(5)

1 = IU (x) =

n
X

(−1)k+1 Zk (x),

k=1

su kiekvienu x ∈ U .
Tarkime,
x ∈ A1 , . . . , Am ,

bet

x 6∈ Am+1 , . . . , An

su kažkokiu 1 ≤ m ≤ n. Šiam x gauname
n
X

(−1)k+1 Zk (x) = Z1 (x) − Z2 (x) + · · · + (−1)m+1 Zm (x).

k=1

16

Sumoje Zk (x) yra sudedami 1 ir 0. Vienetu‘ skaičius lygus kiekiui tu‘ sankirtu‘
Ai1 ∩ · · · ∩ Aik ,
kurias sudaro aibės iš rinkinio {A1 , . . . , Am }. Tokiu‘ sankirtu‘ yra Cnk . Vadinasi,
µ ¶
m
Zk (x) =
,
k
o
n
X

k+1

(−1)

k=1

µ ¶
µ ¶ µ ¶
m
m
m+1 m
=
Zk (x) =
−
+ · · · + (−1)
m
1
2

µ ¶
m
=
− (1 − 1)m = 1
0

su kiekvienu 1 ≤ m ≤ n. Gave‘ (5) lygybe‘, baigiame 1 teoremos i‘rodyma‘.bll
Panaudoje‘ užsieninėje literatūroje dažnai naudojamus žymenis, gauname sekanti‘ i‘jungimo ir išjungimo principa‘.
2 teorema. Tarkime, kad A1 , . . . , An – aibės X poaibiai, X∅ := X,
XJ := ∩i∈J Ai .
Aibės X elementu‘ , nepriklausančiu‘ jokiai iš aibiu‘ Ai , skaičius lygus
X

(−1)|J| |XJ |.

J⊂{1,...,n}

.Jei Āi := X \ Ai , tai nagrinėjamas skaičius lygus
|Ā1 ∩ · · · ∩ Ān | = |X \ (A1 ∪ · · · ∪ An )| = |X| − |A1 ∪ · · · ∪ An |.
Toliau pakanka pritaikyti 1 teorema‘. /

17

7. Netvarku‘ uždavinys
Kiek yra n eilės keitiniu‘, kuriuose bet koks 1 ≤ i ≤ n pakeičiamas j 6= i, 1 ≤ j ≤
n? Tokius kėlinius vadinkime netvarkingaisiais. Kai kada ši problema sutinkama kinu‘
restorano uždavinio pavadinimu. Tada ji formuluojama buitiškiau. Štai vienas iš galimu‘
variantu‘.
n džentelmenu‘ būrelis atvyksta pietauti ‘i kinu‘ restorana‘ . Rūbinėje visi atiduoda savo
skrybėles, kurios po pietu‘ gra‘ žinamos atsitiktinai. Kokia tikimybė, kad m iš šiu‘ klientu‘
atgavo savo skrybėles?
Teorema. Netvarkingu‘ ju‘ keitiniu‘ skaičius lygus
n!

n
X
(−1)k

k!

k=0

.Bendras keitinio pavidalas

µ

.

¶
1 2 ... n
.
i1 i2 . . . in

Tegu Ak – aibė keitiniu‘ su savybe ik = k, X – visa keitiniu‘ aibė, o Āk = X \Ak , 1 ≤ k ≤ n.
Ieškomasis skaičius pagal 6.2 teorema‘ lygus
(1)
|Ā1 ∩ · · · ∩ Ān | = |X| −

n
X

X

|Ai | +

i=1

|Ai ∩ Aj | − · · · + (−1)n |A1 ∩ · · · ∩ An | =

1≤i<j≤n

= |X| − S1 + S2 − · · · + (−1)n Sn .
Čia, kaip ir anksčiau
Sk =

X

|Ai1 ∩ · · · ∩ Aik |.

1≤i1 <i1 ···<ik ≤n

Aibiu‘ sankirta šioje sumoje yra sudaryta iš keitiniu‘, kurie palieka vietoje i1 , . . . , ik . Kitu‘
n − k elementu‘ keitimui jokiu‘ apribojimu‘ nėra. Todėl iš viso yra (n − k)! tokiu‘ keitiniu‘.
Taigi,
µ ¶
X
n
n!
Sk =
(n − k)! =
(n − k)! = ,
k
k!
1≤i1 <i1 ···<ik ≤n

nes sumoje buvo Cnk vienodu‘ dėmenu‘. Kadangi |X| = n!, tai i‘state‘ gautuosius skaičius i‘
(1), baigiame teoremos i‘rodyma‘. /
Kinu‘ restorano uždavinio sprendimas. Pakanka klasikinio tikimybės apibrėžimo: surade‘, kiek yra galimu‘ i‘vykiu‘, kada m klientu‘ atgauna savo skrybėles, ši‘ skaičiu‘ padalijame
18

iš n!, visu‘ galimu‘ i‘vykiu‘. Sunumeruokime džentelmenus bei ju‘ skrybėles nuo 1 iki n. Jei
j-asis klientas gavo ij -a‘ skrybėle‘, tai keitiniai
µ

1 2 ... n
i1 i2 . . . in

¶

žymi visus i‘manomus elementariuosius i‘vykius. Mums palankius i‘vykius žyminčiuose keitiniuose sutapimas ij = j turi pasikartoti lygiai m kartu‘, o visu‘ likusiu‘ (n − m) klientu‘
aibės indeksai turi sudaryti netvarkinga‘ji‘ keitini‘. Pagal teorema‘ šis skaičius lygus
(n − m)!

n−m
X
k=0

(−1)k
.
k!

Kadangi m poaibiu‘, kuriu‘ elementus keitinys palieka vietoje, yra Cnm , tai gauname
n−m
X (−1)k
n!
(n − m)!
m!(n − m)!
k!
k=0

palankiu‘ i‘vykiu‘. Vadinasi, uždavinio atsakymas yra tikimybė
n−m
1 X (−1)k
.
m!
k!
k=0

/
8. Siurjekciju‘ skaičius
Keliais būdais n skirtingu̧ rutuliu̧ galėtume patalpinti i̧ m skirtingu̧ dėžiu̧? Formalizuojant ši̧ uždavini̧, tenka nagrinėkime atvaizdžius f : X → Y , kai |X| = n, o |Y | = m. Iš
viso ju‘ yra tiek, kiek n žodžiu‘, sudarytu‘ iš m raidžiu‘ abėcėlės. O kiek yra siurjekciju‘ , t.y.
atvaizdžiu‘, kada kiekvienas y ∈ Y turi bent viena‘ pirmvaizdi‘ iš aibės X? Rutuliu̧ ir dėžiu̧
uždavinyje tai atitiktu̧ sa̧lygos papildyma̧ reikalavimu, kad bent vienoje dėžėje būtu̧ bent
po viena̧ rutuli̧. Aišku, bent vienas toks rutuliu̧ išdėstymas bus tik tada, jei m ≤ n.
Teorema. n aibės ‘i m aibe‘ , m ≤ n, siurjekciju‘ skaičius lygus
m
X

µ ¶
m
(−1)
(m − k)n .
k
k

k=0

.Jei U – visu‘ atvaizdžiu‘ aibė, tai |U | = mn . Tegu Y = {y1 , . . . , ym }, o Aj – atvaizdžiai,
nei‘gyjantys reikšmės yj , 1 ≤ j ≤ m. Pagal ta‘ pačia‘ atvaizdžiu‘ skaičiaus teorema‘ gauname
|Aj | = (m − 1)n ,

|Ai ∩ Aj | = (m − 2)n ,
19

...

, |Ai1 ∩ · · · ∩ Aik | = (m − k)n .

Čia 1 ≤ i < j ≤ m, 1 ≤ i1 < i2 · · · < ik ≤ m.
Siurjekciju‘ vaizdai yra visi yj , todėl mus dominanti aibė yra lygi aibiu‘ Aj papildiniu‘
iki U sankirtai, t.y.,
S := Ā1 ∩ Ā2 ∩ · · · ∩ Ān .
Pagal praeito skyrelio teoremos išvada‘
|S| = |U | − S1 + S2 − · · · + (−1)m Sm

(1)
Čia
µ ¶
m
(m − 1)n ,
S1 =
1

µ ¶
µ
¶
m
m
n
S2 =
(m − 2) , . . . , Sm−1 =
(m − m + 1)n ,
2
m−1

i‘state‘ i‘ (1) formule‘, baigiame i‘rodyma‘./
Išvada.
µ ¶
n
X
k n
n! =
(−1)
(n − k)n ,
k

Sm = 0.

n ≥ 1.

k=0

.Kiekviena n aibės siurjekcija i‘ ja‘ pačia‘ yra ir bijekcija, o bijekciju‘ skaičius sutampa
su n keitiniu‘ kiekiu. Toliau pritaikome teorema‘, kai n = m./
9. Stirlingo skaičiai
Aibės A skaidiniu (k skaidiniu) vadiname išraiška‘
(1)

A = A1 ∪ · · · ∪ Ak ,

Aj ⊂ A, Aj 6= ∅,

Ai ∩ Aj = ∅,

1 ≤ i < j ≤ n.

Jungiamu‘ poaibiu‘ tvarka čia nesvarbi. Tegu P(n, k) – visu‘ (1) skaidiniu‘ aibė. Jos elementu‘
skaičius S(n, k) := |P(n, k)| vadinamas antros rūšies Stirlingo skaičiumi (James Stirling,
1692-1770, - škotu‘ matematikas).
Pastebėkime, kad (1) skaidinys susije‘s su aibės A siurjekcijomis i‘ k aibe‘, tarkim, i‘ aibe‘
B := {1, . . . , k}. Tegu
Q(n, k) := {f : A → B, f − siurjekcija}.
Iš 8 skyrelio teoremos turime
(2)

µ ¶
k
X
j k
|Q(n, k)| =
(−1)
(k − j)n .
j
j=0

Iš (2) išvesime patogia‘ formule‘ antros rūšies Stirlingo skaičiui S(n, k), 1 ≤ k ≤ n, nustatyti.
Susitarkime, be to, žymėti S(0, 0) = 1.
20

1 teorema.
µ ¶
k
|Q(n, k)|
1 X
j k
S(n, k) =
=
(−1)
(k − j)n .
k!
k! j=0
j
.Jei A = {a1 , . . . , an }, f ∈ Q(n, k), tai pažymėje‘
Aj = {ai ∈ A : f (i) = j},

1 ≤ j ≤ k,

gauname vieninteli‘ skaidini‘ A = A1 ∪ . . . Ak . Atvirkščiai, turėdami toki‘ skaidini‘, galėtume
apibrėžti daug siurjekciju‘. Pakaktu‘ aibės Aj elementus atvaizduoti i‘ viena‘ skaičiu‘ ij taip,
kad skaičiai i1 , . . . , ik sudarytu‘ k kėlini‘. Kadangi tokiu‘ kėliniu‘ yra k!, iš viso gautume k!
siurjekciju‘. Taigi |Q(n, k)| = k!S(n, k). Toliau pakanka pritaikyti (2) formule‘./
Jei Bn – visu‘ galimu‘ A išraišku‘, jungiant netuščius poaibius, skaičius, vadinamas Belo
skaičiumi, tai
n
X
Bn =
S(n, k).
k=1

Atkreipkime dėmesi‘ i‘ panašuma‘ su anksčiau turėta poaibiu‘ skaičiaus formule
n µ ¶
X
n
2 =
.
k
n

k=0

Dabar išvesime viena‘ rekurentu‘ji‘ sa‘ryši‘.
2 teorema. Susitarkime, kad S(0, 0) = 1. Tada
S(n, k) = kS(n − 1, k) + S(n − 1, k − 1),

1 ≤ k < n.

.Panašiai kaip ir Paskalio teoremos i‘rodyme, visus aibės A k skaidinius perskirkime
i‘ dvi dalis. Viena‘ dali‘ sudarykime iš tokiu‘ skaidiniu‘, kuriuose vienas iš jungiamu‘ poaibiu‘
yra {n}. Ju‘ pavidalas bus toks:
A = A1 ∪ . . . Ak−1 ∪ {n}.
Čia poaibiuose Aj , 1 ≤ k − 1, nėra n. Tokiu‘ skaidiniu‘ bus S(n − 1, k − 1).
Kita‘ dali‘ sudarantys likusieji skaidiniai gali būti gauti tokiu būdu. Imkime aibės
{1, . . . , n − 1} k skaidinius
{1, . . . , n − 1} = A01 ∪ · · · ∪ A0k ,
kuriu‘ bus S(n − 1, k), ir prijungdami paeiliui n prie A0j , 1 ≤ j ≤ k, iš kiekvieno tokio
skaidinio padarytume k pradinės aibės A skaidiniu‘. Todėl antroje skaidiniu‘ grupėje yra
kS(n − 1, k) A skaidiniu‘. Sudėje‘ abieju‘ klasiu‘ skaičius, gauname S(n, k)./
21

Išvada. Jei 1 ≤ k ≤ n, tai S(n, k) ≤ k n+1 .
.Pritaikykite indukcija‘./
Antros rūšies Stirlingo skaičiai yra naudingi polinomu‘ algebroje. Pažymėkime
µ ¶
x
(x)k = x(x − 1) . . . (x − k + 1) =
k!,
k

(x)0 = 1.

3 teorema. Jei S(n, 0) := 0, kai n ∈ N, ir S(0, 0) = 1, tai
xn =

n
X

S(n, k)(x)k

x ∈ R,

n ≥ 0,

00 := 1.

k=0

.Atvejis n = 0 yra trivialus. Tegu toliau n ∈ N. I‘ rodinėjamos lygybės pusėse yra n
laipsnio polinomai, todėl pakanka ja‘ patikrinti daugiau negu n tašku‘. I‘ rodysime, kad ji
teisinga su visais natūraliaisiais x ≥ n. Tuo tikslu, nagrinėjame atvaizdžius
g : A → X := {1, 2, . . . , x}.
Ju‘ yra xn . Ši‘ kieki‘ skaičiuojame kitu būdu. Tegu Y = g(X) ⊂ X – funkcijos g reikšmiu‘
aibė. Tada g : A → Y yra siurjekcija. Poaibiuose Y gali būti 1, 2, . . . , n elementu‘. Jei
|Y | = k, tai gausime |Q(n, k)| skirtingu‘ siurjekciju‘, atitinkančiu‘ skirtingus atvaizdžius
g. Pakeite‘ Y ⊂ X, vėl gautume skirtingas siurjekcijas bei atvaizdžius. Vadinasi, visas
atvaizdžiu‘ g skaičius gali būti užrašomas šitaip:
xn =

n
X

X

|Q(n, k)|.

k=1 Y ⊂X, |Y |=k

Pagal 2 teorema‘
n

x =

n
X

X

k=1 Y ⊂X, |Y |=k

S(n, k)k! =

n
X

S(n, k)k!

k=1

X
Y ⊂X, |Y |=k

1=

n
X

S(n, k)(x)k ,

k=1

¡ ¢
nes aibė X turėjo xk skirtingu‘ k poaibiu‘. Jei n ∈ N, pagal susitarima‘ S(n, 0) = 0, todėl
pastarojoje sumoje galėtume prijungti nulini‘ dėmeni‘, atitinkanti‘ k = 0. Taip gautume
teoremoje nurodyta‘ formule‘. /
Formulė
n
X
(x)n =
s(n, k)xk , x ∈ R,
k=0

apibrėžia pirmos rūšies Stirlingo skaičius s(n, k).
22

4 teorema (Ortogonalumo sa‘ryšis).
n
X

S(n, k)s(k, m) = δmn ,

m, n ≥ 0.

k=m

.Pasinaudokime aukščiau nagrinėtu‘ polinomu‘ išraiškomis per Stirlingo skaičius. Gauname
n

x =

n
X

S(n, k)(x)k =

k=1

n
X

¶
µX
¶ X
n µ X
n
k
m
S(n, k)s(k, m) xm .
S(n, k)
s(k, m)x
=
m=0

m=0

k=1

k=m

Palygine‘ polinomu‘ koeficientus prie vienodu‘ x laipsniu‘, baigiame 4 teoremos i‘rodyma‘./
Uždavinys. Išveskite rekurenčia‘ ja‘ Belo skaičiu‘ formule‘
¶
n µ
X
n−1
Bn =
Bn−k ,
k−1

n ∈ N.

k=1

10. Skirtumo operatorius
Tiesinėje realiu‘ funkciju‘ erdvėje F apibrėžkime skirtumo operatoriu‘ , t.y., atvaizdi‘
∆:F →F
∆f (x) = f (x + 1) − f (x).
Tai tiesinis atvaizdis, nes iš apibrėžimo išplaukia lygybės ∆(c1 f (x) + c2 g(x)) = c1 ∆f (x) +
c2 ∆g(x) su bet kokiom realiom konstantom c1 , c2 bei funkcijomis f (x), g(x). Naudojant
skirtumo operatoriu‘, galima išvesti nemaža kombinatoriniu‘ sa‘ryšiu‘. Pažymėkime ∆m =
∆(∆m−1 ), kai m ≥ 0, ∆1 = ∆; ∆0 = I, čia I tapatusis atvaizdis.
1 teorema. Bet kokiai funkcijai f (x) ir m ≥ 0 teisingos tapatybės
(1)

m

∆ f (x) =

m
X
k=0

(2)

µ ¶
µ ¶
m
X
m
m−j m
(−1)
f (x + m − k) =
(−1)
f (x + j),
k
j
k

k=0

f (x) =

m
X

µ ¶
m
(−1)
∆k f (x),
k
k

k=0

(3)

m µ ¶
X
m
f (x + m) =
∆k f (x),
k
k=0

23

.Pirmoji iš (1) lygybiu‘ i‘rodoma matematinės indukcijos pagalba, pasinaudojant Paskalio tapatybe. Patikrine‘ (1) su m = 0, 1 ir tare‘ kad ji ši lygybė yra teisinga dėl m − 1 ≥ 1,
skaičiuojame suma‘
Sm

¶
µ
µ ¶
m
X
m
k m−1
(−1)
f (x + m − k) =
(−1)
f (x + m − k)
:=
k
k
k=0
k=0
µ
¶
m
X
m−1
+
(−1)k
f (x + m − k).
k−1
m
X

k

k=0

Gautose sumose atmete‘ po nulini‘ dėmeni‘, o antroje dar ir pakeite‘ k − 1 = j, gauname
Sm

µ
¶
m−1 ¡
=
(−1)
f (x + 1) + (m − 1) − k)
k
k=0
µ
¶
m−1
X
¡
¢
j m−1
−
(−1)
f x + (m − 1) − j
j−1
j=0
¡
¢
= ∆m−1 f (x + 1) − ∆m−1 f (x) = ∆m−1 f (x + 1) − f (x) .
m−1
X

k

Taigi, (1) lygybė yra i‘rodyta.
Antrosios iš (1) išraišku‘ i‘rodymui pakanka pakeisti sumavimo indeksa‘.
Norėdami išvesti (2) formule‘, taikome binominiu‘ koeficientu‘ apgre‘žimo formule‘ ir
pirma‘ja‘ iš (1) lygybiu‘. Mūsu‘ ankstesniuose i‘ skyrelio žymėjimuose imame am = ∆m f (x)
bei bk = f (x − m − k). Paskutinės (3) formulės išvedimui vėl taikome ta‘ pati‘ principa‘, bet
vietoje pirmosios naudojame antra‘ja‘ išraiška‘ (1) lygybėje. /
Išvada. Jei n, m ≥ 0, tai
m n

∆ x =

m
X
k=0

m n

µ ¶
m
(−1)
(x + m − k)n ;
k

m n

k

∆ 0 := ∆ x |x=0 =

m
X

µ ¶
m
(−1)
(m − k)n .
k
k

k=0

Dydžiai ∆m 0n , m, n ≥ 0, vadinami Morgano skaičiais. Jei m ≤ n – tai n aibės
siurjekciju‘ i‘ m aibe‘ skaičius, ir jei m > n, tai bet kokiam x ∈ R, ∆m xn = 0. Iš tiesu‘,
kiekvienas operatoriaus ∆ pritaikymas sumažina polinomo xn laipsni‘ vienetu. Kai x = 0,
iš čia išplaukia tapatybė
(4)

m n

∆ 0 =

m
X

µ ¶
m
(−1)
(m − k)n = 0,
k
k

k=0

24

m > n.

Kadangi atveju m > n ir siurjekciju‘ skaičius lygus nuliui, tai darome išvada‘, kad Morgano
skaičiai visada išreiškia siurjekciju‘ kieki‘.
Užduotis. Panagrinėkite postūmio operatoriaus P : F → F, apibrėžiamo lygybe
P f (x) = f (x + 1)
arba P = ∆ + I, savybes. Iveskite keleta‘ kombinatoriniu‘ formuliu‘.
11. Laipsninė generuojanti funkcija
Dažnai kombinatorinius objektu‘ skaičiu‘ išreiškiančios sekos yra sudėtingos, todėl ju‘
tyrimui pasitelkiama funkciju‘ teorija. Sekai
a0 , a1 , . . . , an , . . .

aj ∈ R,

priskiriama formali laipsninė eilutė
a0 + a1 x + a2 x2 + · · · + an xn + . . . ,
vadinama sekos generuojančia funkcija (l.g.f.). Kai kada šia‘ eilute‘ pavyksta susumuoti,
rasti gana paprasta‘ funkcija‘, kurios Teiloro eilutė taško x = o aplinkoje sutampa su šia
generuojančia funkcija. Kombinatorikoje dažnai net nenagrinėjant šios funkcinės eilutės
konvergavimo klausimo, su ja formaliai manipuliuojama, atliekami matematinėje analizėje
žinomi veiksmai (Perskaitykite M.Bloznelio knygelės 4.1 skyreli‘). Pavyzdžiui, nurodytos
viršuje eilutės ir sekos {bm }, m ≥ 0 generuojančios funkcijos sandauga lygi eilutei
c0 + c1 x + c2 x2 + · · · + cn xn + . . .
su
cn =

n
X

ak bn−k ,

n ≥ 0.

k=0

Analizėje prieš dauginant panariui laipsnines eilutes būtu‘ pasidomėta, ar eilutės konverguoja absoliučiai. Daug seku‘ sa‘ryšiu‘, tapatybiu‘ buvo ”atspėta” manipuliuojant su generuojančiomis funkcijomis, vėliau griežtai pagrindžiant atliktas operacijas arba i‘rodant juos
kitais būdais.
Pasinaudokime binominiu‘ koeficientu‘
µ ¶
µ ¶
n
n
, 0 ≤ k ≤ n;
= 0, k > n,
k
k
generuojančia funkcija
µ ¶ µ ¶
µ ¶
n
n
n 2
+
x+
x + · · · = (1 + x)n
0
1
2
25

ir išveskime pora‘ formuliu‘.
1 teorema (Vandermondo sa‘sūka). Bet kuriems natūraliesiems skaičiams k ir m,
k, m < n, teisinga lygybė
¶
µ ¶ X
k µ ¶µ
n
m n−m
=
.
j
k−j
k
j=0
.Panaudoje‘ laipsniniu‘ eilučiu‘ (šiuo atveju, polinomu‘) dauginimo taisykle, gauname
X µn − m¶ X µm¶
(1 + x) = (1 + x)
(1 + x) =
xi
xj =
i
j
j≥0
i≥0
µ
µ
¶µ
¶¶
X
X n−m m
=
xm .
i
j
n

n−m

k≥0

m

i,j≥0
i+j=k

Sulygine‘ koeficientus prie xk , baigiame teoremos i‘rodyma‘./
2 teorema. Su bet kokiu n ≥ 0 teisinga lygybė
µ ¶
n
X
(−1)k+1 n
k=0

k+1

k

=−

1
.
n+1

.Integruodami panariui generuojančia‘ funkcija‘ gauname
Z

u

n

(1 + x) dx =
0

n µ ¶Z
X
n
k=0

k

u

xk dx,

0

n
¢ X
1 ¡
uk+1
n+1
(1 + u)
−1 =
.
n+1
k+1
k=0

I‘ state‘ u = −1, baigiame i‘rodyma‘./
2 teoremos tapatybe‘ palyginkite su anksčiau nagrinėtomis harmoniniu‘ skaičiu‘ savybėmis. Matematinėje analizėje yra išvedama apibendrintoji Niutono binomo formulė
∞ µ ¶
X
u n
(1 + x) =
x ,
n
u

x, u ∈ R, |x| < 1.

k=0

Čia, kaip jau buvo minėta,
µ ¶
u
u(u − 1) . . . (u − n + 1)
,
=
n!
n
26

n ∈ N ∪ {0}.

Funkcija (1 + x)u yra apibendrintu‘ju‘ binominiu‘ koeficientu‘ generuojanti funkcija.
Matematinėje analizėje išvedamos funkciju‘ laipsninės eilutės yra ju‘ koeficientu‘ generuojančios funkcijos. Taigi, formulės
(1)

− log(1 − x) =

∞
X
xn
,
n
n=1

|x| < 1,

bei
∞
X
1 n
x ,
e =
n!
n=0
x

(2)

x ∈ R,

duoda seku‘ {1/n}, n ≥ 1 ir {1/n!}, n ≥ 0 laipsnines generuojančias funkcijas atitinkamai.
Uždavinys. ‘Irodykite Koši tapatybe‘
X
k1 ,...,kn ≥0
1k1 +···+nkn =n

n
Y

1
= 1,
kj k !
j
j
j=1

n ≥ 1.

Sprendimas. Nagrinėjame vienetu‘ sekos l.g.f.. Naudodami (1) ir (2) formules, gauname
½X j¾
X
1
x
n
x =
= exp{− log(1 − x)} = exp
=
1−x
j
n≥0
j≥1
½ j ¾ Y X µ j ¶k
Y
x
x
1
exp
=
=
.
j
j
k!
j≥1

j≥1 k≥0

Formaliai dauginame eilutes (pagri‘skite!). Dešinėje pusėje gauname
X
k1 ,...,kn ,...≥0

X
x1k1 x2k2 . . .
xn
=
k
k
1
2
1 2 . . . k1 !k2 ! . . .
n≥0

X
k1 ,...,kn ≥0
1k1 +···+nkn =n

n
Y
j=1

1
j kj k

j!

.

Paskutiniame žingsnyje grupavome absoliučiai konverguojančios srityje |x| < 1 eilutės
narius. Taylor’o koeficientai apibrėžiami vienareikšmiškai. Vadinasi, koeficientas prie xn
yra lygus vienetui./
Laipsniniu‘ generuojančiu‘ eilučiu‘ nauda ypač išryškėja nagrinėjant rekurenčia‘sias sekas. Vėliau šiuos sa‘ryšius panagrinėsime smulkiau, dabar apsistosime ties vienu pavyzdžiu.
27

12. Katalano skaičiai
Atliekant binaria‘sias algebrines operacijas, pvz., sudėti‘ tenka suskliausti ir sudėti po
du dėmenis paeiliui. I‘ sitikinkite, kad yra 5 keturiu‘ dėmenu‘ suskliaudimo būdai, nemaišant
dėmenu‘ tvarkos. Apibendrinant gauname toki‘ rezultata‘.
1 teorema. Yra

µ
¶
1 2n − 2
Cn =
n n−1

n ≥ 2 dėmenu‘ suskliaudimo būdu‘ .
.Bet kaip suskliaudžiant paskutiniame žingsnyje suskliaudžiame du dėmenis E1 + E2 .
Jei naryje E1 buvo k dėmenu‘, tai 1 ≤ k ≤ n − 1, o E2 – n − k dėmenu‘. Pagal skaičiaus
Ck apibrėžima‘, nesikertančiu‘ aibiu‘ sa‘jungos elementu‘ formule‘ gauname
(1)

Cn =

n−1
X

Ck Cn−k ,

n ≥ 2.

k=1

Susitarkime, be to, kad C0 = 0, C1 = 1. Raskime sekos {Cn }, n ≥ 0, generuojančiu‘
funkcija‘
∞
X
Cn xn =: F (x).
n=0

Apskaičiuojame, naudodami (1),
2

F (x) =

∞ µ n−1
X
X
n=2

¶
Ck Cn−k xn = F (x) − x.

k=1

Išsprende‘ kvadratine‘ lygti‘, gauname
µ
¶
1
1/2
F (x) =
1 ± (1 − 4x)
.
2
Kadangi F (0) = 0, reikia imti minuso ženkla‘. Pasinaudodami apibendrinta‘ja Niutono
binomo formule, keliame laipsniu 1/2, ir sulyginame koeficientus prie xn . Gauname
µ ¶
1 1/2
Cn = −
(−4)n =
2 n
1 1 −1 −3
−(2n − 3) (−4)n
(2n − 2)
=−
···
=
.
2 2 2 2
2
n!
(n − 1)!n!
/
Skaičiai Cn vadinami Katalano vardu.
28

13. Eksponentinės generuojančios funkcijos
Naudojant laipsnines generuojančias funkcijas, tenka pagri‘sti ju‘ konvergavima‘ netrivialioje taško x = 0 aplinkoje. Kai koeficientu‘ seka didėja palyginti greitai, to padaryti
nepavyksta. Tokio sunkumo kai kada pavyksta išvengti normuojant koeficientus. Panagrinėsime labiausiai naudojama‘ atveji‘, kai nagrinėjamos sekos koeficientai dalijami iš indekso faktorialo. Dažnai panašiu normavimu siekiama ir pačiu‘ funkciju‘ paprastumo. Sekos
{an }, n ≥ 0 eksponentine generuojančia funkcija (e.g.f.) vadinama formali eilutė
f (x) := a0 +

a1 x a2 x2
an xn
+
+ ··· +
+ ....
1!
2!
n!

Taigi vienetu‘ sekos e.g.f. yra ex , o sekos {n!}, n ≥ 0, – funkcija 1/(1 − x).
Pastebėkime pora‘ savybiu‘, palengvinančiu‘ skaičiavimus. Tarkime g(x) – sekos {bn },
n ≥ 0, e.g.f.
Lema. Jei f (x) - sekos {an } e.g.f., tai f 0 (x) - sekos {an+1 }, n ≥ 0 e.g.f.. Formali
suma f (x) + g(x) atlikta panariui yra sekos {an + bn }, n ≥ 0 e.g.f., o sandauga f (x)g(x)
– sekos
n µ ¶
X
n
cn :=
ak bn−k
k
k=0

e.g.f.
.Pirmasis tvirtinimas gaunamas panariui diferencijuojant eilute‘ f (x). Kiti teiginiai
matosi atlikus nurodytus veiksmus/
Panagrinėkime keleta‘ pavyzdžiu‘. Pradžioje pritaike‘ e.g.f., raskime netvarkingu‘ju‘ n
eilės keitiniu‘ skaičiu‘ Dn . Prisimename atsakyma‘
Dn = n!

n
X
(−1)k+1
k=0

Pradėkime tapatybe

k!

.

n µ ¶
X
n
n! =
Dn−k ,
k
k=0

reiškiančia, kad keitiniai išskaidyti i‘ nesikertančias klases, taip,
¡n¢ kad vienoje klasėje esantys
keitiniai palieka k = 0, 1, . . . , n elementu‘ vietoje. Kadangi k = 0, kai k > n, tai pastaroji
lygybė ir lema duoda generuojančiu‘ funkciju‘ lygybe‘
1
= ex D(x),
1−x
Rade‘ funkcijos

D(x) =

∞
X
Dn n
x .
n!
n=0

D(x) = e−x /(1 − x)
29

n-a‘ Taylor’o koeficienta‘, baigiame i‘rodyma‘.
1 teorema. Tegu S(n, k) – antros rūšies Stirlingo skaičiai. Sekos {S(n, k)}, n ≥ k
e.g.f. lygi
(ex − 1)k
Fk (x) :=
, k ≥ 1.
k!
.Naudodamiesi rekurenčia‘ja Stirlingo skaičiu‘ formule, lygybe S(n, k) = 0, kai n < k,
skaičiuojame
Fk (x) =

X

S(n, k)

n≥k

=k

X
m≥k

X¡
¢ xn
xn
=
kS(n − 1, k) + S(n − 1, k − 1)
=
n!
n!
n≥k

X
x
xm+1
+
S(m, k − 1)
.
(m + 1)!
(m + 1)!
m+1

S(m, k)

m≥k−1

Eilučiu‘ konvergavima‘ užtikrina lengvai patikrinamas i‘vertis S(n, k) ≤ k n+1 . Diferencijuodami panariui, gauname rekurenčia‘ja‘ formule‘
(1)

Fk0 (x) = kFk (x) + Fk−1 (x).

Ja‘ naudodami i‘rodyma‘ baigiame matematinės indukcijos būdu. Kai k = 1, S(n, 1) = 1,
todėl norima lygybė išplaukia iš eksponentinės funkcijos skleidinio
(2)

X xn
= ex − 1.
n!

n≥1

Tare‘, kad 1 teoremoje užrašyta lygybė yra teisinga su dėl k − 1 vietoje k, iš (1) gauname
Fk0 (x) − kFk (x) =

(ex − 1)k−1
.
(k − 1)!

Diferencialiniu‘ lygčiu‘ teorijoje yra i‘rodoma, kad tokios lygtys turi tik viena‘ sprendini‘,
patenkinanti‘ sa‘lyga‘, Fk (0) = 0. Vadinasi, pakanka patikrinti, ar 1 teoremoje nurodyta
funkcija tenkina šia‘ lygti‘./
Išvada. Belo skaičiu‘ sekos {Bn }, n ≥ 1, e.g.f. lygi
(3)

B(x) := exp{ex − 1}.

.Pagal lema‘ ir Belo skaičiu‘ apibrėžima‘ pakanka sudėti visiems k ≥) teoremoje gautas
formules ir pasinaudoti (2) išraiška ./
2 būdas. Iš rekurenčiosios formulės
n µ ¶
X
n
Bn+1 =
Bk
k
k=0

30

ir Lemos išplaukia sa‘ryšis

B 0 (x) = ex B(x).

Šios diferencialinės lygties sprendinys su sa‘lyga ir yra (3) funkcija.
2 teorema. Tegu s(n, k) – pirmos rūšies Stirlingo skaičiai. Sekos {s(n, k)}, n ≥ k
e.g.f. lygi
X
¢k
xn
1¡
fk (x) :=
s(n, k)
=
log(1 + x) , |x| < 1, k ≥ 0.
n!
k!
n≥k

.Lygybės dešinėje esanti logaritminė funkcija yra apibrėžta srityje |x| < 1. Jos Taylor’o koeficientai apibrėžiami vienareikšmiškai. Vadinasi, reikia patikrinti ar skaičiai a(n, k)
apibrėžiami lygybe
¢k X a(n, k) n
1¡
log(1 + x) =
x ,
k!
n!
n≥k

sutampa su pirmos rūšies Stirlingo skaičiais. Dauginkime paskutine‘ lygybe‘ iš mk ir sudėkime pagal visus k ≥ 0. Gauname
X 1¡
¢k X k X a(n, k) n
m log(1 + x)
m
x .
k!
n!

k≥0

k≥0

n≥k

Kairia‘ja‘ puse‘ skaičiuojame pagal (2) formule‘, dešinėje keičiame sumavimo tvarka‘. Gauname
X xn X
a(n, k)mk .
exp{m log(1 + x)} =
n!
n≥0

0≤k≤n

Kadangi kairioji pusė yra polinomas (1 + x)m , tai sulygine‘ koeficientus prie vienodu‘ x
laipsniu‘, gauname
µ ¶
n
m
1 X
a(n, k)mk ,
=
n
n!
k=0

kai n ≤ m. Palygine‘ su pirmos rūšies Stirlingo skaičiu‘ apibrėžimu, matome, kad a(n, k) =
s(n, k). /
14. Rekurentieji sa‘ryšiai. Pavyzdžiai
Nagrinėsime sekas, kuriu‘ n-tasis narys tam tikra formule yra išreiškiamas per jos
narius su mažesniais indeksais. Be to, vienetinumui užtikrinti nurodoma pirmu‘ju‘ sekos
nariu‘. Tokios išraiškos vadinamos rekurenčiosiomis formulėmis. Labiausiai žinomos yra
aritmetinė ir geometrinė progresijos nusakomos formulėmis
an = an−1 + d,
31

an = qan−1

atitinkamai. Čia d yra bet koks skaičius, o q - skaičius, nelygus nuliui ir vienetui. Paskalio
tapatybė binominiams koeficientams yra dvieju‘ indeksu‘ sekos rekurenčiosios formulės pavyzdys. Labai daug uždaviniu‘ apie sekas yra sprendžiami dviem etapais. Pradžioje randami rekurentieji jos nariu‘ sa‘ryšiai, o vėliau jie yra išnagrinėjami. Antrajamaje žingsnyje
pritaikomi kombinatorikos metodai. Taip dažnai elgiamasi n-os eilės determinantu‘ teorijoje. Pradėsime nuo kitokiu‘ paprastu‘ pavyzdžiu‘.
1 uždavinys. ‘Irodykite, kad n plokštumos tiesiu‘ , tarp kuriu‘ nėra dvieju‘ lygiagrečiu‘
ir bet kurios trys iš ju‘ nesikerta viename taške, dalija plokštuma‘ ‘i
pn = 1 +

n(n + 1)
2

sričiu‘ .
Sprendimas. Akivaizdu, kad p1 = 2, p2 = 4, p3 = 7. Taikome indukcijos principa‘.
Tarkime, kad jau išvedėme k tiesiu‘ ir nustatėme plokštumos sričiu‘ skaičiu‘ pk . Vedame,
k +1 tiese‘. Keliaukime ja nuo taško, esančio dar iki pirmojo susikirtimo su viena iš pirmu‘ju‘
tiesiu‘. Šia‘ sriti‘ naujoji tiesė padalijo pusiau, už susikirtimo su pirmaja tiese esančia‘ sriti‘
- irgi pusiau. Pratese‘ šia‘ kelione‘, matome, kad kiekviena nauja sritis dalijama pusiau.
Kadangi k + 1 tiesė kirs k + 1 sričiu‘, gauname sričiu‘ skaičiaus išraiška‘
pk+1 = pk + (k + 1).
Pritaike‘ indukcijos prielaida‘ dėl pk , gauname
pk+1 = 1 +

k(k + 1)
(k + 1)(k + 2)
+ (k + 1) = 1 +
.
2
2

Vadinasi, viršuje nurodyta pn formulė yra teisinga su visais natūraliaisiais skaičiais n.
2 uždavinys (Leonardo Fibonacci). Triušiu‘ pora per antra‘ mėnesi‘ atsivedė nauja‘
porele‘ jaunikliu‘ ir vėliau kas mėnesi‘ dar po porele‘ . Kitos porelės elgėsi taip pat. Pažymėkime Fn - triušiu‘ poru‘ skaičiu‘ n mėnesio gale. ‘Irodykite, kad
√
√
( 5 + 1)k+1 − (1 − 5)k+1
√
Fn =
, n ≥ 0.
2n+1 5
Sprendimas. Nesunku matyti, kad seka Fn (vadinama Fibonačio vardu) tenkina
rekurentu‘ji‘ sa‘ryši‘
(1)

Fn = Fn−1 + Fn−2 ,

n ≥ 2.

Išnagrinėkime šia‘ lygybe‘ i‘vairiais būdais.
1 būdas. Ieškome laipsninės generuojančios funkcijos
Φ(x) =

∞
X
n=0

32

Fn xn .

Kadangi
xΦ(x) =

∞
X

Fn xn+1 = x +

n=0

ir
x2 Φ(x) =

∞
X

Fn−1 xn

n=2

Fn xn+2 =

n=0

tai

∞
X

∞
X

Fn−2 xn ,

n=2

Φ(x) − xΦ(x) − x2 Φ(x) = 1,

arba
Φ(x) =

1
1
.
=
−1
1 − x − x2
(1 − α1 x)(1 − α2−1 x)

Čia α1 , α2 - lygties

x2 + x − 1 = 0

šaknys, t.y.,
α1 = (−1 +

√

5)/2,

α2 = (−1 −

√

5)/2.

Pastebėkime, kad α2 = −α1−1 . Racionalia‘ja‘ funkcija‘ išskaidome paprasčiausiu‘ju‘ trupmenu‘
suma. Gauname
B
α1
α2
A
1
1
+
=√
−√
.
1 + α1 x 1 + α2 x
5 1 + α1 x
5 1 + α2 x
√
Pasinaudoje‘ begalinės geometrinės progresijos sumos formule, kai |x| < ( 5 − 1)/2, gauname
∞
∞
α1 X
α2 X
n n
√
√
Φ(x) =
(−α1 ) x −
(−α1 )−n xn .
5 n=0
5 n=0
Φ(x) =

Sulygine‘ koeficientus prie xn , baigiame Fn formulės išvedima‘. ¦
2 būdas. Galima naudoti ir eksponentines generuojančias funkcijas. Perraše‘ (1)
formule‘ patogesniu būdu, gauname Fm+2 = Fm+1 + Fm , m ≥ 0. Pagal 13 skyrelio lema‘
funkcija
∞
X
Fn n
x
Ψ(x) =
n!
n=0
tenkina diferencialine‘ lygti‘

Ψ00 (x) = Ψ0 (x) + Ψ(x)

ir pradines sa‘lygas Ψ(0) = Ψ0 (0) = 1. Diferencialiniu‘ lygčiu‘ teorijoje i‘rodoma, kad pastarojo uždavinio sprendinys yra funkcija
Ψ(x) =

α1 eα1 x − α2 eα2 x
√
.
5
33

Išskleide‘ eksponentines funkcijas Teiloro eilutėmis, randame n-ta‘ nari‘. ¦
15. Rekurentieji sa‘ryšiai. Bendra teorija
Dabar išvystysime bendresne‘ teorija‘. Tarkime, kad seka {un }, n ≥ 0 yra apibrėžta r
eilės sa‘ryšiu
(2)

un+r + a1 un+r−1 + · · · + ar un = 0,

n ≥ 0,

ir pradiniais nariais u0 , u1 , . . . , ur−1 . (2) pavidalo formules vadiname tiesiniais homogeniniais rekurenčiaisiais sa‘ ryšiais, o polinomas
A(x) =

r
X

aj xj ,

a0 := 1

j=0

vadinamas charakteristiniu polinomu.
(Galimas ir kitoks šio polinomo apibrėžimas:
Ã(x) =

r
X

ar−j xj ,

a0 := 1,

j=0

bet tada tolesnės formulės komplikuojasi).
Prisilaikydami mūsu‘ apibrėžimo, ištirkime laipsnine‘ generuojančia‘ funkcija‘
U (x) =

∞
X

un xn .

n=0

1 teorema. Sandauga A(x)U (x) yra polinomas
D(x) :=

r−1
X

dk xk

k=0

su
dk =

k
X

aj uk−j ,

0 ≤ k ≤ r − 1.

j=0

tais
(3)

Irodymas. Daugindami A(x) ir U (x) panariui, gauname laipsnine‘ eilute‘ su koeficien-

‘

dk =

k
X

aj uk−j .

j=0

34

Čia laikome, kad aj = 0 , kai j ≥ r + 1. Jei k ≤ r − 1, (3) formulė yra ieškomoji. Imkime
paeiliui k = r, r + 1, . . . ir naudodami (2), i‘sitikinkime, kad tada dk = 0. ¦
Išvada. Generuojanti funkcija U (x) = D(x)/A(x) yra racionalioji funkcija.
Toliau funkcijai U (x) taikysime racionaliu‘ju‘ funkciju‘ teorija‘. Tokiu‘ funkciju‘ kūne
C(x) egzistuoja U (x) išraiška paprasčiausiu‘ju‘ trupmenu‘ suma
(4)

U (x) =

ri
k X
X
i=1 j=1

lij
.
(1 − λi x)j

Čia λ−1
∈ C, 1 ≤ i ≤ k, - charakteristinio polinomo A(x) šaknys, rr - ju‘ kartotinumai,
i
r1 + · · · + rk = r, o lij ∈ C. (4) išraiška‘ galima rasti, jei pavyksta rasti A(x) šaknis. Jei
jau turime skaidini‘
A(x) = ar (x − x1 )r1 . . . (x − xk )rk ,

xi ∈ C,

tai neapibrėžtu‘ju‘ koeficientu‘ metodu randame koeficientus Aij tenkinančius lygybe‘ racionaliu‘ju‘ funkciju‘ kūne
ri
k
D(x) X X
Aij
U (x) =
=
.
j
A(x)
(x
−
x
)
i
i=1 j=1
Pastebėkime, kad xi 6= 0, nes a0 = 1. Vadinasi, iškėle‘ xi prieš skliaustus, gautume (4)
formule‘.
2 teorema. Jei U (x) turi (4) išraiška‘ , tai
un =

k
X
i=1

λni

µ
¶
j+n−1
lij
.
n
j=1

ri
X

n ≥ 0.

Irodymas. Pagal apibendrinta‘ja‘ Niutono binomo formule‘

‘

¶
¶
∞ µ
∞ µ
X
X
−j
n+j−1 n n
1
n n n
=
(−1) λi x =
λi x ,
(1 − λi x)j
n
n
n=0
n=0

|λi x| < 1.

I‘ state‘ i‘ (4) formulė ir sulygine‘ koeficientus prie vienodu‘ x laipsniu‘, baigiame 2 teoremos
rodyma‘. ¦
2 eilės tiesiniu‘ rekurenčiu‘ju‘ sa‘ryšiu‘ atveju gauname.
Išvada‘. Tarkime, kad seka {un }, n ≥ 0, apibrėžta sa‘ ryšiu un+2 + a1 un+1 + a2 un = 0
ir pradinėmis sa‘ lygomis u0 = u1 = 1. Jei A(x) = a2 (x − x1 )(x − x2 ), x1 6= x2 , λi = x−1
1 ,
tai
un = c1 λn1 + c2 λn2 ,
35

o konstantos c1 , c2 randamos iš pradiniu‘ sa‘ lygu‘ . Jei A(x) = a2 (x − x1 )2 , λ = x−1
1 , tai
un = c1 λn + c2 nλn ,
o konstantos c1 , c2 randamos iš pradiniu‘ sa‘ lygu‘ . ¦
Pavyzdys. Raskime sekos {un }, n ≥ 0, tenkinančios ketvirtos eilės rekurentu‘ ji‘ sa‘ ryši‘
un+4 − 2un+2 + un = 0,
bendra‘ ji‘ nari‘ , jei u0 = u1 = 1, o u2 = u3 = 2.
Sprendimas. Charakteristinis polinomas turi pavidala‘
A(x) = x4 − 2x2 + 1,
todėl generuojanti funkcija lygi
U (x) =

D(x)
.
(1 − x2 )2

Čia kubinio polinomo D(x) = d0 + d1 x + d2 x2 + d3 x3 koeficientai skaičiuojami pagal 1
teoremoje naudotas formules. Gauname
d0 = a0 u0 = 1,
d1 = a0 u1 + a1 u0 = 1,
d2 = a0 u2 + a1 u1 + a2 u0 = 0,
d3 = a0 u3 + a1 u2 + a2 u1 + a3 u0 = 0.
Vadinasi,
U (x) =

1+x
1
A1
A2
A3
=
=
+
+
.
(1 − x2 )2
(1 − x)2 (1 + x)
1 − x (1 − x)2
1+x

Subendravardikline‘ ir sulygine‘ skaitikliuose esančius polinomus, randame neapibrėžtuosius
koeficientus A1 , A2 , A3 . Gauname
1 = A1 (1 − x2 ) + A2 (1 + x) + A3 (1 − 2x + x2 )
arba

A1 + A2 + A3 = 1,
A2 − 2A3 = 0,
−A1
+ A3 = 0.
36

Vadinasi, A1 = 1/4, A2 = 1/2 ir A3 = 1/4. Dabar galime pasinaudoti 2 teorema.
Atsakymas.
1 + (−1)n
n+1
un =
+
.
4
2
¦
Pastebėkime, kad sprendžiant lengviau naudoti 2 teoremos i‘rodymo metoda‘, negu
išvesta‘sias formules!
16. Sudėtiniu‘ funkciju‘ Tayloro koeficientu‘ rekurentieji sa‘ryšiai
Praeitame skyrelyje, turėdami rekurentu‘ji‘ sa‘ryši‘, ieškojome bendrojo sekos nario.
Pastarasis dažnai būna sudėtingas ir apsunkina skaičiavimus. Programuojant žymiai paprasčiau naudoti rekurenčia‘sias formules. Tai ypač gerai atsispindi skaičiuojant sudėtiniu‘
funkciju‘ Tayloro koeficientus. Pradėkime nuo pavyzdžio.
Pavyzdys. Rasti funkcijos
(1)

F (x) = exp

½X
∞
j=1

¾
aj j
x .
j

n-a‘ ji‘ Tayloro koeficienta‘ , jei aj yra aprėžta realiu‘ skaičiu‘ seka.
Sprendimas. Laipsninė eilutė po eksponentės ženklu absoliučiai konverguoja srityje
|x| < 1. Ja apsiribodami, dauginame žinomus skleidinius
¶k
∞ X
∞ µ
Y
1
aj xj
F (x) =
=
j
k!
j=1 k=0
¶
∞ µ
n
X
X
Y
akj
xn .
=
kj k !
j
j
n=0
j=1
k1 ,...,kn ≥0
1k1 +···nkn =n

Taigi, ieškomi koeficientai lygūs
(2)

bn :=

n
Y

X
k1 ,...,kn ≥0
1k1 +···+nkn =n

akj
,
kj k !
j
j
j=1

n ≥ 0.

Tokia ir i‘ ja‘ panašios formulės yra labai nepatogios programuotojams.
1 teorema. Funkcijos F (x) Tayloro koeficientai bn tenkina rekurentu‘ ji‘ sa‘ ryši‘
n

bn+1 =

1 X
an−j+1 bj ,
n + 1 j=0
37

b0 := 1, n ≥ 0.

Irodymas. Diferencijuodami gauname

‘

0

F (x) =

∞
X

n−1

nbn x

= F (x)

n=1

∞
X

l

al+1 x =

∞ µX
n
X
n=0

l=0

¶
bj an−j+1 xn .

j=0

Kadangi funkcijos, esančios kairėje šios lygybės pusėje, koeficientas prie xn lygus (n +
1)bn+1 , apskliaustoji suma yra jo išraiška. ¦
2 teorema. Funkcijos
m

Gm (x) := (A(x))

:=

µX
∞

¶m
k

ak x

,

m ∈ N, a0 6= 0

k=0

su aprėžtais realiais aj Tayloro koeficientai gn := gn (m) tenkina rekurentu‘ ji‘ sa‘ ryši‘
gn+1 =

a−1
0

n µ
X
j=0

¶
(m + 1)j
m−
an−j+1 gj ,
n+1

g0 = am
0 , n ≥ 0.

Irodymas. Vėl diferencijuodami gauname

‘

G0 (x) = mAm−1 (x)A0 (x) =

∞
X

(n + 1)gn+1 xn .

n=0

Padauginame abi puses iš A(x) ir panariui sudauginame eilutes. Kairėje pusėje gauname
m

0

0

mA (x)A (x) = mGm (x)A (x) =

∞ µ
X

m

n
X

n=0

¶
(n − l + 1)gl an−l+1 xn .

l=0

Panašiai dešinėje pusėje gauname eilute‘
A(x)

∞
X

n

(n + 1)gn+1 x =

n=0

∞ µX
n
X
n=0

¶
(l + 1)gl+1 an−l xn .

l=0

Sulyginame koeficientus prie xn :
n
n
X
X
(l + 1)gl+1 an−l = m
(n − l + 1)gl an−l+1 .
l=0

l=0

Iš čia išsprendžiame gn+1 . Gauname
(n + 1)gn+1 a0 = m

n
X
l=0

(n − l + 1)an−l+1 gl −

n
X
l=0

38

n
X
¡
¢
lan−l+1 gl =
m(n − l + 1) − l an−l+1 gl .
l=0

Iš čia išplaukia ieškoma lygybė. ¦
Užduotis. Raskite funkcijos

log

µX
∞

¶
aj x ,
j

a0 = 1,

j=0

su realiais aj Tayloro koeficientu‘ rekurenčia‘ ja‘ formule‘ .
Pastaruoju atveju funkcijos abibrėžimui tektu‘ reikalauti, kad po logaritmo ženklu
esanti eilutė ne tik konverguotu‘, bet ir nebūtu‘ lygi nuliui. Ir ankstesniuose pavyzdžiuose
sekos aj aprėžtumas gali būti pakeistas reikalavimu, kad jos laipsninė generuojanti funkcija
turėtu‘ netrivialia‘ konvergavimo sriti‘. Pačios rekurenčiosios formulės turi prasme‘ be jokiu‘
išankstiniu‘ apribojimu‘.
15. Grandininės trupmenos
Reiškini‘
α = q0 +

1
q1 +

1

q2 +...

1
qk−1 + 1
qk

vadiname grandinine trupmena. Trumpesnis žymuo:
α = [q0 , q1 , q2 , . . . , qk ].
Čia q0 ∈ Z, qj ∈ N, 1 ≤ j ≤ k, o k ≥ 0 - sveikasis skaičius.
1 teorema. Kiekviena‘ racionalu‘ ji‘ skaičiu‘ galime išreikšti grandinine trupmena, be
to, vieninteliu būdu.
Irodymas. Tegu α = a/b, a ∈ Z, b ∈ N, - nagrinėjamas racionalusis skaičius. Pri‘
taikykykime Euklido algoritmo formules
a = q0 b + r0 ,
0 < r0 < b,
b = q1 r0 + r1 ,
0 < r 1 < r0 ,
r0 = q2 r1 + r2 ,
0 < r 2 < r0 , . . .
rk−3 = qk−1 rk−2 + rk−1 ,
0 < rk−1 < rk−2 ,
rk−2 = qk rk−1 .
Čia q0 ∈ Z, o gj ∈ N. Nelygybės b > r0 > r1 > · · · > rk−1 rodo, kad šiu‘ formuliu‘ yra
39

baigtinis skaičius. Dabar išreikšdami paeiliui
a
1
= q0 +
,
b
b/r0
b
1
= q1 +
,
r0
r0 /r1
r0
1
= q2 +
,...
r1
r1 /r2
rk−3
1
= qk−1 +
,
rk−2
rk−2 /rk−1
rk−2
= qk
rk−1
ir i‘statydami i‘ aukščiau stovinčias formules, gauname norima‘ išraiška‘.
Atkreipe‘ dėmesi‘ i‘ tai, kad qj yra tam tikru‘ skaičiu‘ sveikosios dalys, kurios apibrėžiamos
vienareikšmiškai, gauname ir vienaties pagi‘stuma‘. ¦
Trupmenu‘ sekos
δ0 :=

P0
:= [q0 ] = q0 ,
Q0

δ1 :=

P1
:= [q0 , q1 ],
Q1

δ2 :=

P2
:= [q0 , q1 , q2 ], . . .
Q2

nariai vadinami artininiais (reduktais). Atkreipkime dėmesi‘ i‘ tai, kad δk gaunamas iš δk−1
pakeičiant qk−1 skaičiumi qk−1 + 1/qk .
2 teorema. Pažymėkime P−1 = 1 ir Q−1 = 0. Artiniu‘ skaitikliai ir vardikliai tenkina
šiuos rekurenčiuosius sa‘ ryšius:
Pk = qk Pk−1 + Pk−2

Qk = qk Qk−1 + Qk−2

k ≥ 1.

Irodymas. Pritaikome indukcija‘. Jei k = 1, tai P1 = q0 q1 + 1 = q1 P0 + P−1 ir
Q1 = q1 = q1 Q0 + Q−1 . Tare‘, jog formulės išvestos dėl visu‘ Pj , Qj , kai j ≤ k, imame artini‘
‘

δk+1 = Pk+1 /Qk+1 .
Kaip pastebėjom anksčiau, jis gaunamas iš
δk = Pk /Qk =

qk Pk−1 + Pk−2
qk Qk−1 + Qk−2

vietoje qk i‘stačius qk + 1/qk+1 . Taigi,
δk+1 = Pk+1 /Qk+1
=

¡
¢
1
qk + qk+1
Pk−1 + Pk−2
¢
=¡
=
1
qk + qk+1
Qk−1 + Qk−2

qk+1 (qk Pk−1 + Pk−2 ) + Pk−1
qk+1 Pk + Pk−1
=
.
qk+1 (qk Qk−1 + Qk−2 ) + Qk−1
qk+1 Qk + Qk−1
40

Ta‘ ir reikėjo i‘rodyti. ¦
Išvada. Seka Qk , k ≥ 0, griežtai monotoniškai didėja.
3 teorema. Kai k ≥ 1, tai
µ
¶
Pk Pk−1
det
= Pk Qk−1 − Pk−1 Qk = (−1)k+1 .
Qk Qk−1
Be to,
δk − δk−1 =

(−1)k+1
.
Qk Qk−1

I̧rodymas. Skaičiuodami determinanta‘ pritaikome 2 teorema‘. Jis lygus priešingam
determinantui, kuriame elementu‘ indeksai vienetu yra mažesni. Po k žingsniu‘ gauname jo
reikšme‘:
(−1)k (P0 Q−1 − P−1 Q0 ) = (−1)k (q0 · 0 − 1 · 1) = (−1)k+1 .
Išvedant antra‘ja‘ formule‘, pakanka subendravardiklinti ir pritaikyti ka‘ tik gauta‘ lygybe‘. ¦
Išvada. Teisingos nelygybės
δ0 < δ1 < · · · <
Be to,

a
< . . . δ3 < δ1 .
b

a
1
| − δk | ≤
.
b
Qk Qk+1

I̧rodymas. Pakanka atidžiau i‘sižiūrėti i‘ gauta‘sias formules. ¦
Pastaroji nelygybė svarbi apytikriam skaičiavimui. I‘ racionalieji skaičiai skleidžiami
begalinėmis grandinėmis trupmenomis. Ju‘ artiniai turi visas ka‘ tik išvardintas savybes.
Apsiribosime pavyzdžiu.
Uždavinys. Ištraukime kvadratine‘ šakni‘ iš 5.
√
Sprerndimas. Kadangi skaičiaus 5 sveikoji dalis yra 2, tai
√

√
5 = 2 + ( 5 − 2) = 2 +

1
√
=
5−2

√

1
√
,
1/( 5 − 2)

√
5+2
1
√
= 4 + ( 5 − 2) = 4 +
.
1
1/( 5 − 2)

Ir vėl vardiklyje atsirado toks pats skaičius. Kartodanmi procesa‘, skaičiu‘ 4 galėtume išskirti
norimai ilgai. Vadinasi,
√
5 = [2, 4, 4, 4, . . . ].
Pagal rekurenčia‘sias 2 teoremos formules gauname artiniu‘ seka‘:
2,

9
,
4

38
,
17

161
,
72
41

682
,...
305

Priešpaskutinė parašyta trupmena aproksimuoja

√
5 tikslumu:

√
161
1
| 5−
|≤
.
72
72 · 682
Aprašytasis algoritmas yra labai greitas. Galima būtu‘ i‘rodyti, kad periodinės grandininės trupmenos ir tik jos yra kvadratiniu‘ i‘racionalybiu‘ skleidiniai.
GRAFU‘ TEORIJA
1. Pagrindinės sa‘vokos
Grafas - aibiu‘ pora G = (V, E), čia V - viršūniu‘ aibė, E - nesutvarkytu‘ju‘ viršūniu‘
poru‘ e := (x, y) =: xy = yx, x, y ∈ V arba briaunu‘ (lanku‘) aibė. Kai poros xy laikomos sutvarkytomis, G vadinamas digrafu. Viršūnės vaizduojamos taškais, briaunos jas jungiančiais lankais arba atkarpomis. Digrafo atveju papildomai nurodoma ir kryptis. Kada vietoje briaunu‘ aibės E imamas briaunu‘ rinkinys (šeima) su pasikartojimais,
pora (V, E) vadinama multigrafu. Ji‘ vaizduojant plokštumoje, dvi viršūnės jungiamos
atitinkamu kiekiu briaunu‘. Viršūnės x ir y vadinamos xy briaunos galais arba jai incidenčiomis viršūnėmis. Viena kitos atžvilgiu jos yra gretimosios (kaimyninės) viršūnės.
Geometrinis vaizdavimas dažnai yra klaidinantis, nes skirtingi brėžiniai gali atitikti
ta‘ pati‘ grafa‘ (žr. 1 pav. dviem būdais pavaizduota‘ grafa‘ K3,3 ). Grafai G = (V, E) ir
G0 = (V 0 , E 0 ) vadinami izomorfiškais, jei egzistuoja bijekcija φ : V → V 0 tokia, kad su
kiekviena briauna xy ∈ E yra patenkinta sa‘lyga:
xy ∈ E

φ(x)φ(y) ∈ E 0 .

⇐⇒

Multigrafu‘ atveju pastaroji sa‘lyga turi būti patenkinta kiekvienai iš kartotiniu‘ briaunu‘, o
digrafams – atvaizdis φ turi išlaikyti ir briaunos krypti‘.
Kai kada grafo (arba digrafo) viršūniu‘ aibėje tenka i‘vesti numeracija‘. Tada grafai
(digrafai) vadinami numeruotaisiais, o du tokie grafai G = (V1 , E1 ) ir G = (V2 , E2 ),, čia
Vi = {vi1 , . . . , vin }, vadinami izomorfiškais, jeigu grafu‘ anksčiau apibrėžtas izomorfizmas
išlaiko dar ir numeracija‘, t.y., Φ(v1j ) = v2j . Pavyzdžiai: keitiniu‘ grafinis vaizdavimas, visu‘
baigtinės aibės atvaizdžiu‘ i‘ save grafinis vaizdavimas. Apskritai izomorfiškus grafus galima
sutapatinti, laikyti juos lygiais.
Nagrinėsime tik baigtinius grafus, t.y. tik poras (V, E) su baigtinėmis aibėmis V ir E.
Šiu‘ aibiu‘ galias žymėkime |V | = n ≥ 1 ir |E| = m ≥ 0. Jei nebus pasakyta priešingai,
grafas neturės taip vadinamu‘ kilpu‘ , t.y. briaunu‘ xx. Kadangi grafas neturi kartotiniu‘
briaunu‘, tai m ≤ Cn2 . Čia Cnk - binominis koeficientas. Dažnai tokie grafai vadinami
paprastaisiais. Skaičius n vadinams grafo G eile, o m - grafo G didumu. Kai m = 0, grafas
G vadinamas tuščiuoju (tradiciškai žymimas E n ), o kai m = Cn2 , - pilnuoju. Pilname grafe
visos viršūnės yra tarpusavyje sujungtos, jis žymimas K n .
42

nis.

O kiek iš viso galima sudaryti n eilės grafu‘? Numeruotu‘ju‘ grafu‘ atvejis yra paprastes1 teorema. Galima sudaryti

2n(n−1)/2

skirtingu‘ n eilės numeruotu‘ ju‘ grafu‘ .

¡ ¢
I̧rodymas. Skaičiuojamu‘ grafu‘ didumai gali būti 0, 1, . . . , k, . . . , N := n2 . Brėžiant k
¡ ¢
didumo grafa‘, jo briaunu‘ aibe‘ galėtume parinkti iš visos galimos briaunu‘ aibės N
k būdu‘ .
Taigi, skirtingu‘ n eilės grafu‘ gauname
µ ¶
µ ¶
µ ¶
N
N
N
1+
+ ··· +
+ ··· +
= (1 + 1)N = 2N .
1
k
N
¦
Viršūnės x laipsniu (valentingumu) δ(x) laikomas incidenčiu‘ jai briaunu‘ skaičius. Kai
δ(x) = 0, x - izoliuotoji viršūnė. Skaičiai
δ(G) = min{δ(x) : x ∈ G},

∆(G) = max{δ(x) : x ∈ G}

atitinkamai vadinami minimaliuoju bei maksimaliuoju grafo laipsniais. Kai δ(G) = ∆(G)
=: k, grafas G vadinamas k reguliariuoju (k-valenčiu). Pvz., kubinis bei Petersen’o grafai
(žr. 2 pav.) yra trivalenčiai.
Grafas G0 = (V 0 , E 0 ) vadinamas G = (V, E) pografiu, jeigu V 0 ⊂ V ir E 0 ⊂ E.
Jeigu pografio G0 briaunu‘ aibėje E 0 yra visos E briaunos, jungiančios V 0 viršūnes, tai
G0 vadinamas V 0 indukuotoju pografiu, ji‘ žymėsime G[V 0 ]. Apibrėšime grafu‘ veiksmu‘.
Tarkime, kad G = (V, E) - grafas, x ∈ V 0 ⊂ V ir xy ∈ E 0 ⊂ E. Tada
G − V 0 := G[V \ V 0 ]
ir

G − E 0 := (V, E \ E 0 ).

Taigi, grafas G−x := G−{x} gaunamas iš G išmetant ne tik viršūne‘ x, bet ir jai incidenčias
briaunas, o G − xy := G − {xy} - išmetant tik briauna‘ xy. Kai kada tikslinga, atėmus iš
grafo briauna‘ xy, sutapatinti viršūnes x ir y. Ši operacija vadinama grafo sutraukimu.
Grafas (V ∪V 0 , E ∪E 0 ) vadinamas G = (V, E) ir G0 = (V 0 , E 0 ) sa‘ junga, žymima G∪G.
Dažniausiai grafu‘ sa‘jungoje viršūniu‘ aibėms dar iškeliamas reikalavimas neturėti bendru‘
tašku‘. Mes taip pat prisilaikysime šio reikalavimo. Grafu‘ G ir G0 suma G+G0 apibrėžiama
kaip ju‘ sa‘junga, papildomai išvedant visas briaunas, jungiančias V ir V 0 viršūnes.
Grafa‘ vaizdžiai charakterizuoja i‘vairios ”klajojimo” juo galimybės. Viršūniu‘ ir briaunu‘
seka‘ x0 , e1 , x1 , . . . , ek , xk su ej = xj−1 xj , xj ∈ V , j = 0, . . . , k vadiname keliu (x0 − xk keliu), o k - jo ilgiu. Kai kelyje visos briaunos yra skirtingos, ji‘ vadiname trasa. Uždara‘ trasa‘
(kai x0 = xk ir k ≥ 2) vadinsime grandine. Jeigu kelyje (arba trasoje) visos vidinės viršūnės
43

x1 , . . . , xk−1 yra skirtingos, ji‘ vadiname taku, ir uždara‘ taka‘, kai k ≥ 2, - ciklu (grandimi).
Takus bei ciklus žymėsime pereinamu‘ viršūniu‘ seka, pvz., P = x1 x2 x3 ...xk . Akivaizdžia‘
paskutine‘ briauna‘ xk x1 cikle galime ir nenurodyti. Jei grafe egzistuoja grandinė, sudaryta
iš visu‘ jo briaunu‘, tai jis vadinamas Euler’io vardu, o jei jame yra ciklas, apimantis visas
jo viršūnes, tai jis yra Hamilton’o grafas. Šios sa‘vokos nėra ekvivalenčios. Pateikite
pavyzdžiu‘.
Grafas G yra jungusis, jei bet kuria‘ pora‘ viršūniu‘ iš E jungia takas. Jei n ≥ 2, šis
grafas neturi izoliuotu‘ viršūniu‘.
2 teorema. Grafas yra jungiu‘ pografiu‘ sa‘ junga.
Irodymas. Dvi viršūnes vadinkime ekvivalenčiomis, jeigu grafe yra jas jungiantis takas.
Tai ekvivalentumo sa‘ryšis viršūniu‘ aibėje V. Ekvivalenčiu‘ viršūniu‘ klasės V1 , . . . , Vs nesikerta, grafe nėra briaunu‘, jungiančiu‘ skirtingu‘ klasiu‘ viršūnes. Indukuotieji pografiai
G[V1 ], . . . , G[Vs ] ir sudaro ieškomos sa‘jungos pografius. ¦
‘

Teoremoje apibrėžtus pografius vadinsime grafo jungumo komponentėmis. Viršūnė,
kurios atėmimas iš grafo keičia komponenčiu‘ skaičiu‘, vadinama iškarpos viršūne, o briauna,
- tiltu. Atstumu d(x, y) tarp viršūniu‘ x ir y vadinsime trumpiausio tako ilgi‘, jei toks takas
egzistuoja. Priešingu atveju, atstuma‘ laikysime begaliniu.
Grafas G = (V, E) vadinamas dvidaliu (bichromačiuoju, dvispalviu), jei V = V 0 ∪ V 00 ,
0
V ∩ V 00 = ∅, o bet kokia briauna iš E jungia viršūne‘ iš V 0 su viršūne iš V 00 . Dvidalis grafas
neturi nelyginio ilgio grandiniu‘. I‘ sitikinkite, jog ir priešingas teiginys yra teisingas!
2. Miškas ir medžiai
Grafas, neturintis ciklu‘ (beciklis), vadinamas mišku, o jungusis miškas - medžiu.
1 teorema. Grafas yra miškas tada ir tik tada, kada bet kokia‘ viršūniu‘ pora‘ jungia
ne daugiau kaip vienas takas.
Irodymas. Jei grafas nėra miškas, jame egzistuoja ciklas x0 x1 ...xl x0 . Todėl turime du
‘
takus x0 x1 ...xl ir x0 xl .
Atvirkščiai, tarkime, kad P = x0 ...xl ir P 0 = x0 yl ...ys = xl - du takai, jungiantys x0
su xl . Tarkime, kad i + 1 - mažiausias indeksas, su kuriuo xi+1 6= yi+1 , o j ≥ i mažiausias
indeksas su kuriuo yj+1 jau priklauso P , t.y. yj+1 = xk . Tada xi ...xk yj ...yi+1 yra ciklas.
Todėl grafas nėra miškas.
2 teorema. Šie tvirtinimai yra ekvivalentūs:
a) G yra medis;
b) G yra minimalus jungus grafas, t.y. bet kurios briaunos atėmimas iš grafo padidintu‘
komponenčiu‘ skaičiu‘ ;
c) G yra maksimalus beciklis grafas, t.y. sujungiant bet kokias neincidenčias viršūnes
būtu‘ sukuriamas ciklas.
Irodymas.
Pažymėkime V, E grafo G viršūniu‘ ir briaunu‘ aibes, xy ∈ E - bet kokia‘ jo briauna‘, o
u, v - bet kokias dvi neincidenčias viršūnes.
‘

44

Jei G - medis ir grafas G − xy būtu‘ jungus, tai G turėtu‘ du takus P = xx1 ...xk y ir
P = xy, vadinasi, todėl turėtu‘ cikla‘ P = xx1 ...xk yx. Tad, iš a) išplaukia b). Briauna,
kurios atėmimas didina grafo komponenčiu‘ skaičiu‘ vadinama tiltu.
Jei G - medis, tai jame egzistuoja takas nuo u iki v. Išvestas naujasis takas uv su
senuoju sudarytu‘ cikla‘, ir grafas G + uv jau turėtu‘ cikla‘. Tad, iš a) išplaukia c).
Tarkime, G - minimalus jungus grafas. Jei G nebūtu‘ medis, o turėtu‘ cikla‘ xx1 ...yx,
tai išmetus briauna‘ xy, jo jungumas nepakistu‘. Prieštara i‘rodo, jog iš b) išplaukia a).
Panašiai i‘rodomi ir like‘ teiginiai. ¦
Išvada. Jungiame grafe egzistuoja medis, kurio viršūniu‘ aibė sutampa su visa grafo
viršūniu‘ aibe.
I̧rodymas. Pasimaudokite b) savybe. ¦
Išvadoje gautasis medis vadinams minimaliu jungiančiuoju medžiu (karkasu). Nurodysime dar pora‘ karkasinio medžio išvedimo būdu‘.
1 būdas. Jungiame grafe G = (V, E) fiksuokime viršūne‘ x ∈ V ir viršūniu‘ aibe‘
suskaidykime i‘ nepersikertančias aibes
Vi = {y ∈ V : d(x, y) = i},

i = 0, 1, . . . , s < ∞.

Jei yi ∈ Vi , tai egzistuoja x−yi takas xz1 ...zi−1 yi . Pastebėkime, kad Vj 6= ∅, j = 0, 1, ..., i,
0
kai i > 0. Taigi, bet kuriam yi ∈ Vi rasime yi−1
∈ Vi−1 . Iš, gal būt, keliu‘ galimybiu‘
0
pasirinkime viena‘. Kai y perbėgs V , priskirtieji y (artimesni pradiniam taškui) ir y sudarys
jungu‘ji‘ grafa‘
T = (V, E 0 ),
E 0 = {yy 0 : y ∈ V, y 6= x}.
Kadangi i‘ y patenkama tik iš vieno taško, jis neturi ciklu‘. Taigi, T - karkasinis medis.
2 (indukcinis) būdas. Imkime x ∈ V . Tada T1 := ({x}, ∅) - medis. Tarkime, kad
jau sukonstravome medžiu‘ seka‘
T1 ⊂ T2 ⊂ · · · ⊂ Tk ⊂ G
ir medžio Ti eilė yra i. Jei k < n = |V |, tai egzistuoja pora (y, z) tokia, kad z ∈ V (Tk ),
y ∈ V \ V (Tk ), čia V (Tk ) - Tk viršūniu‘ aibė, ir zy ∈ E. Priešingas atvejis prieštarautu‘
grafo G jungumui. Apibrėžkime
Tk+1 = (V (Tk ) ∪ {y}, E(Tk ) ∪ {zy}).
Baigtiniame grafe šis procesas baigtinis. Jis baigiasi, kai k = n.
Medi‘ galime charakterizuoti ir pagal jo skaitinius parametrus: eile‘ ir diduma‘, bet apie
tai vėliau.

45

3. Viena optimizavimo problema
Jungiančiu̧ju‘ medžiu‘ savybėmis tenka naudotis sprendžiant kai kuriuos optimizavimo
uždavinius. Sakykime, reikia suprojektuoti pigiausia‘ vandentiekio tinkla‘, jungianti‘ visas
miestelio sodybas, kada žinomos visu‘ trasu‘ tarp namu‘ kainos. Jeigu gamtinės kliūtys yra
nei‘veikiamos, galima laikyti, kad trasos per šia‘ kliūti‘ kaina yra begalinė.
Formalizuojant galima i‘sivaizduoti, kad turime pilna‘ji‘ n grafa‘ G = (V, E) ir apibrėžta‘
funkcija‘
f : E → R+ .
Reikia išvesti karkasini‘ medi‘ (vesti kelias linijas i‘ ta‘ pačia‘ sodyba‘ visada bus brangiau)
T = (V, E 0 ) toki‘, kad bendra kaina
F (T ) =

X

f (xy)

xy∈E 0

būtu‘ mažiausia. Ši‘ medi‘ vadinkime ekonomišku. Pradžioje pateiksime tris šio uždavinio
sprendimo algoritmus.
1 algoritmas:
a) imame briauna‘ e = xy ∈ E su mažiausia kaina,
f (e) = min f (xy);
xy∈E

b) iš likusiu‘ briaunu‘ išrenkame pigiausia‘;
c) procesa‘ kartojame su sa‘lyga, kad išrenkamos briaunos nesudarytu‘ ciklo.
Procesas baigtinis, o gautasis grafas, kaip maksimalus beciklis grafas, pagal 2.2 teoremos c) punkta‘ bus karkasinis medis. Gautojo medžio ekonomiškuma‘ išnagrinėsime vėliau.
2 algoritmas:
a) imame briauna‘ e = xy ∈ E su didžiausia kaina,
f (e) = max f (xy)
xy∈E

ir ja‘ atimame iš grafo G;
b) ta‘ pati‘ kartojame su grafu G − e;
c) procesa‘ baigiame, kai kitas briaunos atėmimas padidintu‘ grafo jungumo klasiu‘
skaičiu‘.
Gautasis grafas, kaip minimalus jungus grafas, pagal 2.2 teoremos b) punkta‘ bus
jungiantysis medis.
3 algoritmas:
a) imame bet kokia‘ viršūne‘ x1 ∈ V ;
b) imame viena‘ iš pigiausiu‘ incidenčiu‘ x1 briauna‘ x1 x2 ∈ E, x2 ∈ V \ {x1 };
46

c) rade‘ x1 , . . . , xk ir briaunas xi xj ), i < j ≤ k ieškome x = xk+1 ∈ V \ {x1 , . . . , xk },
tokios, kad kaina f (xk+1 xi ) su kažkokiu i ≤ k būtu‘ minimali.
Procesas baigiasi, kai k = n, o briaunu‘ skaičius lygus n − 1. Taip gavome jungiant¸ji‘
medi‘.
1 teorema. Viršuje aprašytieji algoritmai duoda ekonomiškus medžius. Jei kainos
funkcija yra injektyvi, tai ekonomiškasis medis yra vienintelis.
Irodymas. Tarkime, jog T - ekonomiškas medis, turintis maksimalu‘ skaičiu‘ bendru‘
briaunu‘ su T1 , medžiu, gautu naudojant 1 algoritma‘. Jei E(T ) 6= E(T1 ), imkime pirma‘
briauna‘ xy iš T1 , bet nepatekusia‘ i‘ T . Medyje T irgi yra x − y takas, sakykim P , kurio
bent viena briauna, tegu uv, nepatenka i‘ T1 . Renkant xy, ši briauna uv buvo viena iš
kandidačiu‘, todėl f (xy) ≤ f (uv). Sudarykime nauja‘ karkasini‘ medi‘
‘

T 0 = T − uv + xy.
Jo kaina
F (T 0 ) = F (T ) − f (uv) + f (xy) ≤ F (T ),
todėl ir naujasis medis yra ekonomiškas. Bet jis turi dar daugiau bendru‘ briaunu‘ su T1 ,
nei T . Prieštara i‘rodo, kad T = T1 .
2 bei 3 algoritmais gautu‘ medžiu‘ ekonomiškumas i‘rodomas panašiais samprotavimais.
Nagrinėkime vienati‘, kai visos briaunu‘ kainos skirtingos. Taikome matematine‘ indukcija‘ grafo eilės atžvilgiu. Kai n = 2, 3, teiginys trivialus. Padare‘ prielaida‘, jog teorema
teisinga visiems n ≥ 4 eilės grafams, nagrinėdami (n + 1) eilės pilna‘ji‘ grafa‘, skelkime
viršūniu‘ aibe‘ i‘ dvi dalis V = V1 ∩ V2 , su n1 , n2 ≥ 2 viršūniu‘, n1 + n2 = n + 1 ir nagrinėkime indukuotosius pografius. Juose egzistuoja vieninteliai ekonomiški karkasiniai
medžiai T1 , T2 . Raskime
min f (xy).
x∈V1
y∈V2

Tarkime, ši minimali kaina i‘gyjama briaunoje xy, jungiančioje abu pografius. I‘ sitikinkime,
kad medis
T4 := T1 ∪ T2 + xy
yra ekonomiškas.
Tarkime, T - ekonomiškas medis. Jei T4 6= T , tai vienintelė briauna iš T4 , nepatekusi
i‘ T , gali būti tik xy. Medyje T turi būti kita briauna uv, jungianti T1 su T2 . Bet tada
f (xy) < f (uv) ir medžio
T − uv + xy
kaina būtu‘ griežtai mažesnė, nei T . Prieštara i‘rodo ekonomiško medžio vienati‘.
Pastaba. Vienaties i‘rodymas duoda dar viena‘ jungiančiojo medžio konstravimo būda‘:
kai briaunu‘ kainos skirtingos, galima grafa‘ skaidyti i‘ mažesnius ir juose ieškoti karkasiniu‘
medžiu‘, o vėliau juos sujungti.
47

4. Grafo parametru‘ ryšiai
Pradėkime nuo paprastu‘ teiginiu‘.
1 (Euler’io) lema. Grafo viršūniu‘ laipsniu‘ suma yra lyginis skaičius.
Irodymas. Pakanka pastebėti, jog kiekviena briauna, turėdama du galus, i‘neša 2
‘
vienetus i‘ suma‘
X
(1)
δ(G) = 2|E|
x∈V

¦
1 išvada. Nelyginio laipsnio viršūniu‘ kiekis grafe yra lyginis skaičius.
2 išvada. Tarkime
1 X
d(G) =
δ(x)
|V |
x∈V

yra vidutinis grafo laipsnis, o ε = |E|/|V | – vidutinis briaunu‘ skaičius, tenkantis vienai
viršūnei. Tada ε(G) = d(G)/2.
Irodymas. (1) suma lygi |V |d(G). ¦
‘
Susitarus, kad kilpos atveju viršūnės laipsnis laikomas lygiu 2, lema išlieka teisinga ir
bendresniems grafams.
2 lema. Tarkime, kad G0 = (V 0 , E 0 ) ir G00 = (V 00 , E 0 ), V 0 ∩ V 00 = ∅, - du pilnieji
grafai su
|V 0 | = n1 , |V 00 | = n2 , n1 + n2 = n.
Grafo G0 ∪ G00 didumas didžiausias, kai n1 = n − 1, o n2 = 1.
Irodymas. Dabar grafe G0 ∪ G00 turime
‘
n1 (n1 − 1) n2 (n2 − 1)
+
2
2
briaunu‘. Apskaičiuokime, kaip keičiasi bendras briaunu‘ skaičius, jei viena viršūne didesni‘
grafa‘ padidintume, o kita‘, mažesni‘ji‘, - sumažintume. Tegu n1 ≥ n2 . Gautasis briaunu‘
skaičius būtu‘ lygus
n1 (n1 + 1) (n2 − 1)(n2 − 2)
+
,
2
2
o skirtumas n1 + 1 − n2 ≥ 1.
Taigi, kartojant panašia‘ procedūra‘ pasieksime maksimalu‘ bendra‘ briaunu‘ skaičiu‘, kai n1 =
n − 1, n2 = 1. Lema i‘rodyta.
1 teorema. Jei n - grafo eilė, m - didumas, o k - jo komponenčiu‘ kiekis, tai
(1.1)

n−k ≤m≤

1
(n − k)(n − k + 1).
2
48

Irodymas. Pirma‘ja‘ nelygybe‘ i‘rodysime, taikydami matematine‘ indukcija‘ m ≥ 0
atžvilgiu. Kai m = 0, turime nulini‘ grafa‘ su n jungumo klasiu‘. Tad, nelygybė triviali.
Tegu m1 < m2 < · · · - n eilės grafu‘ G, turinčiu‘ k jungumo klasiu‘, didumai su
savybe: išmetus dar viena‘ briauna‘ iš G, padidėtu‘ jo jungiu‘ komponenčiu‘ skaičius. Kai
mj−1 ≤ m < mj , kairioji iš (1.1) nelygybiu‘ išplauks iš nelygybės, kai m = mj−1 . Todėl
pakanka nelygybe‘ i‘rodyti tik šiai sekai.
Tarkime, jog nelygybė i‘rodyta grafui su mj−1 briauna, ir nagrinėkime atveji‘ |E| = mj .
Kadangi dabar kiekviena briauna yra tiltas, išmetus kažkuria‘ iš ju‘ gauname grafa‘, kuriam
galioja indukcijos prielaida. Tegu tai - grafas
‘

G0 = (V 0 , E 0 ),
Jis turi k + 1 klase‘, todėl

|V 0 | = n,

|E 0 | = mj − 1.

n − (k + 1) ≤ mj − 1.

Iš čia išplaukia pirmoji iš (1.1) nelygybiu‘.
Vertindami m iš viršaus, nagrinėkime pati‘ ”blogiausia‘” atveji‘, kai kiekviena iš jungumo klasiu‘ yra pilnieji pografiai. Pritaike‘ lema‘ kiekvienai šiu‘ klasiu‘ porai, gauname, kad
bendras briaunu‘ kiekis m bus maksimalus, kai viena iš ju‘ yra labai didelė, o likusios - tušti
grafai. Todėl tada n-os eilės grafe su k jungumo klasiu‘, pografiu‘ eilės yra
n − k + 1,

, 1, . . . , 1.

Taigi, maksimalus briaunu‘ skaičius lygus
(n − k + 1)(n − k)
.
2
1 teorema i‘rodyta.
Išvada. Jei n eilės grafas turi daugiau nei 12 (n−1)(n−2) briaunu‘ , tai jis yra jungusis.
2 teorema. n-os eilės jungusis grafas yra medis tada ir tik tada, kada jo didumas
lygus n − 1.
Irodymas. Kai n = 1, tvirtinimas yra trivialus. Pagal pereito skyrelio teorema‘,
‘
atėmus iš n ≥ 2 eilės medžio briauna‘, gauname du medžius, kuriu‘ eilės yra 1 ≤ n1 , n2 < n,
n1 + n2 = n. Jiems pritaikome indukcijos prielaida‘ ir gauname šiu‘ medžiu‘ didumus
mi = ni − 1,

i = 1, 2.

Vadinasi pradinio medžio didumas buvo
m = m1 + m2 + 1 = (n1 − 1) + (n2 − 1) + 1 = (n1 + n2 ) − 1 = n − 1.
Tegu dabar G yra jungus n eilės ir n − 1 didumo grafas. Pagal 1 teorema‘ G0 = G − e,
čia e yra bet kuri iš briaunu‘, turi bent dvi jungumo klases. Taigi, G buvo minimalus
jungus grafas ir pagal pereito skyrelio 1 teorema‘ yra medis./
49

1 išvada. n-os eilės grafo jungiančiojo medžio didumas lygus n − 1.
2 išvada. n-os eilės miško iš k medžiu‘ didumas lygus n − k.
5. Grafo planarumas
Vaizduojant grafus plokštumoje ir brėžiant briaunas apsiribojama Žordano kreivėmis,
t.y. tolydžiomis plokščiomis kreivėmis, kurios neliečia ir nekerta save‘s pačios, išskyrus
galinius taškus. Grafus, kuriuos galima pavaizduoti plokštumoje, taip, kad skirtingos
briaunos neliestu‘ ir nekirstU‘ viena kitos ne viršūniu‘ taškuose, vadiname planariaisiais.
Formaliai kalbant, tai grafai, turintys izomorfiška‘ vaizda‘ plokštumoje su ka‘ tik minėtu
apribojiomu briaunoms. Pati‘ plokštumoje išvesta‘ grafa‘ vadiname plokščiuoju grafu.
Plokštumos sritys, apribotos plokščio grafo briaunomis ir viršūnėmis, vadinamos grafo
veidais. Visi plokštieji grafai turi viena‘ begalini‘ veida‘. Plokščiasis grafas (dažniausiai
priduriama ”be tiltu‘”) kartu su savo veidais vadinamas žemėlapiu. Tada veidus geriau
vadinti valstybėmis.
1 teorema (L.Euler, 1752). Jei G - jungus žemėlapis, n - jo eilė, m - didumas ir
f - valstybiu‘ skaičius, tai
n − m + f = 2.
Irodymas. Indukcija f atžvilgiu. Jei f = 1, tai grafas neturi ciklu‘. Vadinasi, jis yra
‘
medis. Todėl mūsu‘ teiginys išplaukia iš 3.2 teoremos išvados.
Tariame, kad teorema i‘rodyta dėl žemėlapiu‘ su mažesniu už f > 1 skaičiumi valstybiu‘.
Pastebėkime, jog grafas turi ciklu‘. Imkime bet kuria‘ ciklo briauna‘ ir atimkime iš grafo.
Dvi valstybės, kurios buvo atskirtos ciklo, susijungia i‘ viena‘. Todėl naujasis žemėlapis
turės viena valstybe mažiau. Jam pritaikome indukcine‘ prielaida‘. ¦
At egzistuoja neplanarieji grafai? Teigiamas atsakymas išplauks iš plokščiu‘ju‘ grafu‘
parametru‘ i‘verčiu‘. Dabar reikia paminėti mažiausio ilgio ciklus grafe. Susitarkime, mažiausia‘ ciklo ilgi‘ (grafo talijos apimti‘ ) laikyti begaliniu, jei ciklo iš viso nėra.
2 teorema. Planarusis n ≥ 3 eilės jungus grafas turi
(1)

m ≤ 3n − 6

briaunu‘ . Jei toks grafas turi mažiausio ilgio 3 ≤ g < ∞ cikla‘ , tai
(2)

m≤

g(n − 2)
.
g−2

Irodymas. Pradėkime nuo antrojo teiginio. Aišku, jog n ≥ g. Kadangi kieviena
‘
briauna yra ne daugiau dvieju‘ valstybiu‘ siena (tilto atveju ji bus vidine vienos valstybės
siena), tai gf ≤ 2m. I‘ statome i‘ Eulerio daugiakampio formule‘ ir gauname (2).
Parametro g atžvilgiu (2) nelygybės pusė yra mažėjanti funkcija. Tai i‘state‘ mažiausia‘
galima‘ ciklo ilgi‘ g = 3, gauname pirma‘ji‘ tvirtinima‘. Jei jokio ciklo nėra, grafas yra medis.
Tada m = n − 1 ir (1) vėl yra i‘rodyta. ¦
50

Išvada. Pilnasis grafas K 5 ir dvidalis grafas K3,3 yra neplanarieji.
Irodymas. Pirmuoju atveju g = 3, bet m = 10. Vadinasi, K 5 planarumas prieštarautu‘
‘
(2) nelygybei. Dvidalio grafo atveju g ≥ 4. Ir vėl pakaktu‘ pasinaudoti (2) i‘verčiu. ¦
Užduotis. I‘ sitikinkite, jog jungaus plokščio grafo minimalusis laipsnis neviršija 5.
Dabar galime i‘vertinti ir grafo briaunu‘ susikirtimu‘ skaičiu‘ vaizduojant ji‘ plokštumoje.
Kaip minėjome anksčiau susikirtimo taške kertasi skirtingos briaunos, jis nesutampa su
bet kurios iš ju‘ galu.
3 teorema. Tegu Cr(G) yra n ≥ 3-os eilės grafo G briaunu‘ susikirtimo tašku‘ skaičius
vaizduojant ji‘ plokštumoje. Tada
Cr(G) ≥ m − 3n + 6.
Irodymas. Grafa‘ G = (V, E) pavaizduokime plokštumoje ir apibrėžkime nauja‘ grafa‘
‘
G0 = (V 0 , E 0 ), kuriame V 0 gaunama iš V papildžius susikirtimo taškais. Todėl
|V 0 | = |V | + Cr(G) = n + Cr(G).
Atitinkamai briaunu‘ aibė E 0 gaunama iš E tarpusavyje nesikertančiu‘ briaunu‘ ir atskiru‘
besikertančiu‘ briaunu‘ daliu‘. Iš kiekvienos tokios briaunos gaunamos dvi naujojo grafo
briaunos. Todėl
|E 0 | = |E| + 2Cr(G).
Grafas G0 yra plokščias ir jam galime pritaikyti 2 teorema‘. Iš jos išplaukia
|E 0 | ≤ 3|V 0 | − 6.
Vadinasi,
|E| + 2Cr(G) ≤ 3(n + Cr(G)) − 6.
Išsprende‘ nelygybe‘ gauname teoremos teigini‘./
Minimalus briaunu‘ susikirtimu‘ skaičius yra vienas iš grafu‘ skaitiniu‘ parametru‘. Paskutinėje teoremoje gautas i‘vertis nėra tikslus, kai grafo didumas didėjant eilei kinta ne
tiesiškai. Pavyzdžiui, 1982 metais buvo pastebėta, kad Cr(G) ≥ cm3 /n2 , c > 0, jei tik
m ≥ 4n. Tai
6. Grafo viršūniu‘ spalvinimo problema
Išreiškime grafu‘ teorijos terminais toki‘ uždavini‘. Reikia sudaryti laisvai pasirenkamu‘
paskaitu‘ tvarkarašti‘, kuris užimtu‘ mažiausiai laiko, bet kad kiekvienas studentas galėtu‘
išklausyti kiekviena‘ ji‘ dominančia‘ paskaita‘. Paskaitu‘, skaitymas lygiagrečiose auditorijose
ir dėstytoju‘ kiekis yra neribojamas.
Tegu paskaitos žymi grafo viršūnes. Dvi viršūnes junkime briauna, jei atsiras bent du
studentai, norintys išklausyti abi šias paskaitas. Aišku, kad tokios paskaitos turi būti skaitomos skirtingu laiku. Vaizdumo dėlei šias viršūnes nuspalvokime skirtingomis spalvomis.
51

Tuo būdu grafo viršūniu‘ aibė išsiskaido i‘ V1 , ..., Vk poaibius viršūniu‘, turinčiu‘ vienoda‘
spalva‘. Vieno poaibio paskaitos gali būti skaitomos vienu laiku skirtingose auditorijose,
tačiau skirtingu‘ poaibiu‘ paskaitos - tik kitu laiku. Skaičius k parodys bendra‘ visu‘ paskaitu‘
trukme‘. Viršuje suformuluota užduotis reikalauja minimizuoti ši‘ skaičiu‘ k.
Bendra grafo viršūniu‘ spalvinimo problema formuluojama panašiai. Kiek reikia skirtingu‘ spalvu‘ nudažyti G grafo viršūnėms, kad gretimosios viršūnės būtu‘ skirtingu‘ spalvu‘?
Minimalus spalvu‘ kiekis χ(G) vadinamas chromačiuoju grafo skaičiumi. Jei χ(G) ≤ k,
tai grafas G vadinamas k spalviu. Formalizuojant spalvinima‘ galėtume išreikšti atvaizdžiu‘
terminais. Reiktu‘ spalvas sužymėti skaičiais 1, ..., k ir ieškoti atvaizdžio c : V → {1, ..., k}
tokio, kad viršūniu‘ aibės c−1 (i) poaibis būtu‘ nepriklausomas, t.y., bet kokiu‘ dvieju‘ jo
viršūniu‘ nejungtu‘ briauna. Chromatusis skaičius χ(G) priklauso nuo grafo struktūros.
Bet kokios eilės tuščiajam grafui jis lygus vienam, n eilės pilnajam grafui jis lygus n, o n
eilės T medžiui ar dvidaliam G grafui - χ(T ) = χ(G) = 2.
1 teorema. Jei ∆(G) yra maksimalusis grafo laipsnis, tai χ(G) ≤ ∆ + 1.
Irodymas. Taikome matematine‘ indukcija‘ grafo eilės n atžvilgiu. Mažiems n teiginys
‘
patikrinams betarpiškai. Tarkime, kad teorema i‘rodyta visiems n − 1 eilės grafams, ir ju‘
viršūniu‘ spalvinimui panaudota ne daugiau ∆(G) + 1 spalvu‘. Iš n eilės grafo atimkime
viena‘ viršūne‘ v ir pasinaudokime indukcijos prielaida. Nudaže‘ grafa‘ G−v, gri‘žtame prie G.
Viršūnės, gretimos v, yra nudažytos ne daugiau kaip ∆(G) + 1 spalvu‘. Ju‘ yra ne daugiau
kaip ∆(G). Vadinasi, viena spalva yra nepanaudota. Ja nudaže‘ v, baigiame teoremos
i‘rodyma‘. ¦
Pastebėkime, kad pilnajam grafui G = K n 6ioje teoremoje gautas i‘vertis yra nepagerinamas, tačiau 1941 metais Brooks pastebėjo, kad nepilniesiems grafams chromatusis skaičius neviršija maksmaliojo viršūnės laipsnio.
Planariu‘ju‘ grafu‘ chromatusis skaičius gali būti i‘vertintas tiksliau. Pradžioje pastebėkime tokia‘ ju‘ savybe‘.
Lema. Kiekvienas planarus grafas turi ne didesnio kaip penktojo laipsnio viršūne‘ .
Irodymas. Galime nagrinėti tik jungius planarius n ≥ 3 eilės grafus. Jei δ(v) ≥ 6
‘
kiekvienai viršūnei v ∈ V , tai iš lygybės
X
δ(v) = 2m,
v∈V

čia m - grafo didumas, išplaukia 6n ≤ 2m. Tai prieštarauja 5.2 teoremos išvadai, teigiančiai, kad planariajam jungiam grafui m ≤ 3n − 6, kai n ≥ 3. ¦
2 teorema. Kiekvienas planarusis grafas yra penkiaspalvis.
Irodymas. Kaip ir 1 teoremos i‘rodyme remsimės indukcijos principu. Kai n ≤ 5,
‘
teiginys trivialus. Tarkime, kad ji‘ jau i‘rodėm kievienam planariajam grafui, kurio eilė
mažesnė už n. Pagal lema‘ galime išskirti viršūne‘ v su δ(v) ≤ 5. Jei δ(v) < 5, Grafui G − v
pritaikome indukcijos prielaida‘ ir nudažome jo viršūnes, panaudodami 5 spalvas. Viršūnei
v gretimos viršūnės nuspalvinamos mažiau nei 5 spalvomis. Sutaupyta‘ja spalva nudažome
v ir taip baigiame užduoti‘.
52

Tegu δ(v) = 5. Nagrinėkime v gretima‘sias viršūnes v1 , v2 , v3 , v4 , v5 . Bent dvi iš ju‘
yra negretimos tarpusavyje. Priešingu atveju šios virūnės, v ir jas jungiančios briaunos
sudarytu‘ pilna‘ji‘ K 6 grafo G pografi‘. Pagal 5.2 teoremos išvada‘ planariajame grafe to būti
negali.
Tegu v1 ir v2 negretimos viršūnės. Nagrinėkime sutraukta‘ji‘ grafa‘ G0 = G \ {vv1 , vv2 }.
Pagal indukcijos prilaida‘ jam nuspalvinti pakako 5 spalvu‘. Taip ir nudažykime G0 . Dabar
išplėte‘ G0 iki G laikinai išlaikydami viršūniu‘ spalvas. Matome, kad gretimosios v viršūnės
sutaupo viena‘ spalva‘, kuria galime nuspalvinti pačia‘ v. ¦
Panaudokime viršūniu‘ spalvinimo savybes žemėlapio (jungaus plokščio grafo be tiltu‘)
valstybiu‘ spalvinimui. Žemėlapyje atidėkime valstybiu‘ sostines. Valstybiu‘, turinčiu‘ bendra‘
siena‘, sostines sujunkime briaunomis, kertančiomis šia‘ siena‘ viena‘ karta‘. Priskirdami
gautojo grafo, vadinamo it dualiuoju žemėlapiui viršūniu‘ spalvas visai valstybei, gautume
žemėlapio nuspalvinima‘. 1852 metais buvo suformuluota problema, kiek reikia spalvu‘
nuspalvinti žemėlapio valstybėms taip, kad gretimos valstybės būtu‘ skirtingu‘ spalvu‘. Iš 2
teoremos išplaukia
Išvada. Kiekvienas žemėlapis yra penkiaspalvis.
1976 m. K.Appel’is ir K.Haken’as, naudodami kompiuterius, i‘rodė tokia‘ teorema‘.
3 teorema. Kiekvienas žemėlapis yra keturspalvis.
Sugalvokite pavyzdi‘ grafo arba žemėlapio, kurio nei‘manoma nuspalvinti trimis spalvomis.
7. Medžiu‘ skaičius
Prisimename, kad grafai G = (V, E) ir G0 = (V 0 , E 0 ) vadinami izomorfiškais, jei
egzistuoja bijekcija φ : V → V 0 tokia, kad xy ∈ E tada ir tik tada, kada φ(x)φ(y) ∈ E 0 .
Multigrafu‘ atveju dar pridedamas reikalavimas, kad ši atitiktis galiotu‘ visoms kartotinėms
briaunoms. Grafa‘ su sunumeruota viršūniu‘ aibe vadinsime numeruotoju grafu. Tokiu‘ grafu‘
atveju izomorfizmas turi išlaikyti ir numeracija‘, t.y., jei x yra i-toji G grafo viršūnė, tai
izomorfiškame G0 grafe φ(x) turi būti irgi i-ta‘ja viršūne. 1889 metais Cayley apskaičiavo
neizomorfišku‘ numeruotu‘ n tos eilės medžiu‘ kieki‘ T (n)? I‘ sitinkite, kad yra
4!
+ 4 = 16
2
skirtingu‘ 4-os eilės medžiu‘.

1 ( Cayley’io) teorema. Iš viso galime sudaryti nn−2 neizomorfišku‘ numeruotu‘ n
eilės medžiu‘ .
1 -sis ‘irodymas (Prüfer’io). Tarkime G - nagrinėjamu‘ medžiu‘ aibė. Kadangi seku‘
aibės
{(a1 , . . . , an−2 ) : 1 ≤ ai ≤ n, 1 ≤ i ≤ n − 2} =: A
galia yra nn−2 , pakaks rasti bijektyvu‘ atvaizdi‘ A → G.
53

Kai n ≤ 2, teiginys akivaizdus.
Tegu toliau n > 2. Medžiui G = (V, E), kurios viršūniu‘ aibė sunumeruota, V =
{x1 , . . . , xn }, vienareikšmiškai priskirsime seka‘ α = (a1 , . . . , an−2 ) ∈ A, vadinama‘ medžio
Prüfer’io kodu. Pradėkime nuo medžio galinės viršūnės, kurios laipsnis lygus 1. Tokios
viršūnės egzistuoja, nes kiekviena briauna turi dvi viršūnes ir todėl
n
X

δ(xi ) = 2(n − 1).

i=1

Iš keliu‘ tokiu‘ viršūniu‘ išrinkime ta‘, kurios indeksas yra mažiausias. Tegu tai viršūnė xb1 , o
a1 - indeksas viršūnės, gretimos pirmajai. Grafas G−xb1 yra n−1 eilės medis, todėl procesa‘
galima kartoti, kol viršūniu‘, likusiu‘ grafe, skaičius yra didesnis už 2. Kai šis skaičius lygus
2, mes jau esame sudare‘ vienintele‘ seka‘ (a1 , . . . , an−2 ).
Atvirkščiai, ar bet kokiai sekai α = (a1 , . . . , an−2 ) ∈ A galima vienareikšmiškai
priskirti medi‘? Atidėkime n viršūniu‘ ir brėžkime norima‘ medi‘, vadovaudamiesi žemiau
nurodytomis taisyklėmis:
a) jei b1 - mažiausias iš bent dvieju‘ natūraliu‘ju‘ skaičiu‘ (iš 1, ..., n), nepasirodžiusiu‘
sekoje α, tada junkime xb1 su xa1 ;
b) aibe‘ {1, . . . , n} pakeiskime {1, . . . , n} \ {b1 }, o α - seka (a2 , . . . , an−2 );
c) procesa‘ kartojame, kol išsemiame visa‘ seka‘ (tuo pačiu nubrėžiame n − 2 grafo
briaunas);
d) tarpusavyje sujungiame dvi likusias viršūnes.
Taip vienareikšmiškai gautasis grafas yra medis, nes jis jungia visas n viršūniu‘, o jo
didumas yra n − 1.
Kadangi abu nagrinėti atvaizdžiai yra vienas kito atžvilgiu yra atvirkštiniai, teorema
i‘rodyta.
Grafu‘ teorijai artimesnis kitas Cayley’io teoremos i‘rodymo būdas.
Antrasis teoremos ‘irodymas. Tarkime T (n, k) - kiekis n tos eilės medžiu‘, kuriuose
fiksuota viršūnė x ∈ V yra k-ojo laipsnio, 2 ≤ k ≤ n − 1. Viršūnės numeris nesvarbus, jo
neminėsime. Išvesime sa‘ryši‘ tarp T (n, k) ir T (n, k − 1).
Imame medi‘ G, kuriame d(x) = k − 1. Jame išmeskime briauna‘ uv, neincidenčia‘ su
x. Grafas skilo i‘ du pomedžius, viename iš ju‘ yra viršūnės x ir u arba x ir v. Tarkime,
yra pirmasis atvejis. Sujunge‘ dabar x su v, gauname vėl medi‘ G0 , kuriame d(x) = k. Pora‘
(G, G0 ) pavadinkime junginiu ir suskaičiuokime ju‘ kieki‘ dviem būdais. Kadangi grafui G
mes galime sudaryti tiek G0 , kiek yra briaunu‘ su aukščiau minėtomis savybėmis, tai vienam
G mes turime n − 1 − (k − 1) = n − k partneriu‘. Taigi, iš viso yra (n − k)T (n, k − 1)
junginiu‘.
Skaičiuokime ta‘ pati‘ skaičiu‘ kitu būdu, pradėdami nuo G0 , kuriame d(x) = k, k ≥ 2.
Tarkime x1 , . . . , xk - gretimos x viršūnės. Paeiliui išmesdami briaunas xxi , i = 1, . . . k,
mes ”atskeltume” pomedžius T1 , . . . , Tk , kuriu‘ eilės tegu bus n1 , . . . , nk ,
(1)

n1 + · · · + nk = n − 1.
54

Grafo G0 partneri‘ junginyje dabar konstruojame tokiu būdu:
a) išmetame xx1 , o vėliau viršūne‘ x1 sujungiame su bet kokia iš viršūniu‘, nepriklausančiu‘ T1 (turime n − 1 − n1 galimybiu‘);
b) ta‘ pati‘ kartojame su T2 , . . . , Tk .
Atsižvelge‘ i‘ grafu‘ G0 kieki‘ T (n, k) ir (1) iš viso gauname junginiu‘
n
X

T (n, k)(n − 1 − ni ) = (n − 1)(k − 1)T (n, k).

i=1

Sulygine‘ abi junginiu‘ skaičiaus formules, gauname
(n − 1)(k − 1)T (n, k) = (n − k)T (n, k − 1).
Kai k = 1, ši rekurenčioji formulė irgi teisinga. Jos nagrinėjimui galime panaudoti
akivaizdu‘ fakta‘, kad T (n, n − 1) = 1 (žvaigždinio grafo atvejis). Gauname
µ
¶
n−2
T (n, k) =
(n − 1)n−k−1 .
k−1
Sudėdami šias lygybes, išvedame medžiu‘ kiekio T (n) formule‘
T (n) =

n−1
X
k=1

T (n, k) =

n−1
Xµ
k=1

¶
n−2
(n − 1)n−k−1 = ((n − 1) + 1)n−2 = nn−2 .
k−1

1 teorema i‘rodyta.
Numeruota‘ medi‘ su viena išskirta viršūne, šaknimi, vadinsime šakniniu medžiu.
Išvada. Yra dn := nn−1 šakniniu‘ n eilės medžiu‘ .
Irodymas. Kiekvieno medžio, kuriu‘ kieki‘ nusako Cayley’io teorema, šaknimi gali būti
‘
bet kuri viršūnė.
Šakniniai numeruoti medžiai vadinami Cayley’io vardu. Baigtinis ju‘ rinkinys vadinamas šakniniu mišku. Ji‘ sudarančiu‘ medžiu‘ šaknu‘ rinkinys laikomas miško šaknimi.
Kai miško medžiu‘ tvarka yra i‘skaitoma, miškas vadinamas plokščiuoju. Jo šaknis bus
sutvarkytasis medžiu‘ šaknu‘ rinkinys.
2 teorema. Jei qn – n eilės šakniniu‘ mišku‘ skaičius, tai
(2)

qn =

dn+1
= (n + 1)n−1 .
n+1

Irodymas. Imkime (n+1)-os eilės Cayley’io medi‘ ir atimkime jo šakni‘, turėjusia‘ numeri‘
‘
j ∈ {1, . . . , n + 1}. Medis skyla i‘ n eilės miška‘. Sunumeruokime jo viršūnes pirmaisiais n
natūraliu‘ju‘ skaičiu‘. Tuo tikslu buvusius viršūniu‘ indeksus, didesnius už j, sumažinkime
vienetu. Nepriklausomai nuo buvusio j, gauname viena‘ numeruota‘ n eilės miška‘. Taigi,
55

iš (n + 1)-o (n + 1)-os eilės medžio gavome viena‘ mažesnės eilės miška‘. Iš dn+1 -o tokio
medžio - (n + 1)-a‘ karta‘ mažiau medžia‘.
Atvirkščiai, turėdami n eilės šaknini‘ miška‘ iš keleto Cayley’io medžiu‘, i‘vedame papildoma‘ viršūne‘, ir ja‘ briaunomis sujungiame su medžiu‘ šaknimis. Priskirdami paeiliui papildomajai viršūnei numerius j = 1, . . . , n + 1 ir buvusiu‘ viršūniu‘ indeksus, ne mažesnius
negu j padidindami vienetu, gautume (n + 1)-a‘ (n + 1)-os eilės Cayley’io medi‘. Vadinasi,
qn = dn+1 /(n + 1). Dabar (2) išplaukia iš Cayley’io teoremos. ¦
Sprendžiant n duomenu‘ sutvarkymo pagal kokio nors požymio (rakto) didėjima‘ uždavini‘, naudojami binarieji medžiai. Jais vadiname medžius, kurie turi viena‘ 2-ojo laipsnio viršūne‘, vadinama‘ šaknimi, o kitu‘ viršūniu‘ laipsniai yra 3 (jos vadinamos vidinėmis
viršūnėmis) arba 1 (šios viršūnės vadinamos lapais). Takas nuo šaknies iki lapo atitiktu‘
kažkokio pradinio duomenu‘ kėlinio surūšiavima‘ (požymio didėjimo tvarkos atpažinima‘).
Todėl algoritma‘ aprašantis binarusis medis turi turėti n! lapu‘. Susitarkime dar, kad briaunos išvedimas iš vidinės viršūnės i‘ kaire‘ ar i‘ dešine‘ duoda skirtingus binariuosius medžius.
Todėl grafus, pavaizduotus (...) brėžinyje, laikysime skirtingais. Išvesime binariu‘ju‘ medžiu‘,
turinčiu‘ N lapu‘, kiekio CN , formule‘.
2 teorema. Teisingas rekurentusis sa‘ ryšis
(2)

CN =

N
−1
X

Ck CN −k ,

C1 = 1.

k=1

Be to,
(3)

CN

µ
¶
1 2N − 2
=
.
N N −1

Irodymas. Susitarkime, jog atveju N = 1, lapas sutampa su šaknimi, ir medi‘ sudaro
‘
tik viena viršūnė. Kai N > 1, nagrinėkime grafa‘ G − v, kai v - binariojo medžio G šaknis.
Jis sudarytas iš dvieju‘ binariu‘ medžiu‘ - kairiojo, tarkime turinčio k lapu‘, ir dešiniojo,
turinčio eile‘ N − k lapu‘. Čia 1 ≤ k ≤ N − 1 gali būti bet kuris. Kairėje pusėje gali būti
bet koks iš Ck binariu‘ju‘ medžiu‘, o dešinėje – bet koks iš CN −k medžiu‘. Sudėje‘ pagal k šiu‘
kiekiu‘ sandaugas, gauname visa‘ galima‘ binariu‘ju‘ medžiu‘ CN kieki‘. (2) formulė i‘rodyta.
Prisiminkime, jog seka, apibrėžta (2) formule, jau buvo nagrinėta kombinatorikoje (žr
I.12 skyreli‘). Tai yra Katalano skaičiu‘ seka, todėl (3) formulės išvedimo nebekartosime.
Teorema i‘rodyta.
Vidutinis tako nuo šaknies iki lapo ilgis išreiškia algoritmo, pavaizduoto binariu medžiu, efektyvuma‘.
8. Numeruotu‘ grafu‘ eksponentinės generuojančios funkcijos
Dabar susipažinsime su bendresne teorija. Galima i‘sivaizduoti, kad pradedama nuo
komponenčiu‘ arba nuo jungiu‘ grafu‘. Fiksuokime viena‘ tokia‘ klase‘ U ir reikalaukime, kad
56

kiekvienam n ≥ 0 iš n-os eilės grafu‘ joje yra tik baigtinis skaičius. Eilės n ≥ 1 grafui
viršuniu‘ numeracijai naudosime tik skaičius {1, . . . , n}. Visa‘ n eilės grafu‘ aibe‘ žymėsime
Un ⊂ U , o un = |Un | – jos elementu‘ skaičiu‘. Pagal susitarima‘ a0 = 0. Taigi, pradinȩ grafu̧
klasȩ sudaro nesikertančiu‘ poaibiU‘ sa‘junga
U=

∞
[

Un ,

un < ∞.

n=0

Formali eilutė

∞
X
un tn
U (t) =
n!
n=0

vadinama ne tik sekos {an }, n ≥ 0, bet ir grafu̧ klasės U eksponentine generuojančia
funkcija (toliau EGF).
Turėdami dvi numeruotu‘ grafu‘ klases U ir V ir apibrėšime trečia‘ W. Ja‘ sudaro visos
sutvarkytosios poros w = (u, v) ∈ U × V su visais galimais žemiau aprašytais viršūniu‘
sunumeravimais. Tai plokštieji grafai.
Jei u ∈ U viršūnės buvo numeruotos skaičiais {1, . . . , m}, o v ∈ V – skaičiais {1, . . . , n},
tai w numeracijai naudojami skaičiai {1, . . . , m + n}, naujas plokščiasis grafas w laikomas n + m eilės. Grafu‘ u ir v viršūnės pernumeruojamos, dabar naudojant skaičius
{1, . . . , m + n}, išlaikant buvusi‘ ju‘ sutvarkyma‘ (eiliškuma‘) ir taip, kad u ir v elementu‘
naujos numeracijos nesikirstu‘. Formaliai kalbant, w numeracija‘ apibrėžia bet kokios dvi
monotoniškai didėjančios funkcijos θ1 : {1, . . . , m} → {1, . . . , m + n} ir θ2 : {1, . . . , m} →
{1, . . . , m + n}, kuriu‘ reikšmiu‘ sritys nesikerta, o ju‘ sa‘junga yra visa aibė {1, . . . , m + n}.
Visi plokštieji grafai w = (u, v), u ∈ U, v ∈ V su i̧vairiomis leistinomis viršūniu̧
numeracijomis sudaro klasiu‘ U ir V skaidumo sandauga‘ , kuria‘ žymėsime W = U ∗ V. Pagal
indukcija‘ apibrėžiama ir bet kokio skaičiaus grafu‘ bei ju‘ klasiu‘ sandaugos. Atkreipkime
dėmesi‘, kad pradėjome nuo sutvarkytu‘ju‘ poru‘ (u, v), todėl griežtai kalbant, U ∗ V 6= V ∗ U.
Toliau žymėkime
U <1> = U, U <2> = U ∗ U, ... U <n> = U ∗ U <n−1> , ....
Pradedant nuo nesutvarkytu‘ju‘ poru‘, lygiai taip pat apibrėžiame Abelio skaidumo sandaugas. Ju‘ žymėjimui naudosime simboli‘ [∗]. Dabar
U [1] = U , U [2] = U[∗]U , ..., U [n] = U[∗]U [n−1] , . . .
Kadangi yra n! kėliniu‘, sandaugu‘ U <n> ir U [n] EGF riša lygybės
(1)

U <n> (t) = n!U [n] (t),

n = 0, 1, . . . .

Visas plokščiu̧ju̧ grafu̧ kompleksas bus aibė
(2)

U <∗> = {∅} ∪ U ∪ U <2> ∪ . . . .
57

Tai nesikertančiu‘ aibiu‘ sa‘junga. Panašiai
U [∗] = {∅} ∪ U ∪ U [2] ∪ . . .

(3)

bus (neplokščiu̧ju̧) grafu̧ kompleksas.
Plokštieji šakniniai numeruotieji miškai, kai pradinė struktūru‘ klasė buvo visu‘ numeruotu‘ medžiu‘ klasė, yra pirmojo komplekso pavyzdys. Funkciniai digrafai, kai pradedama
nuo jungiu‘ funkciniu‘ digrafu‘, yra antrojo komplekso tipo pavyzdys.
1 teorema. Tegu
X un tn
U (t) =
,
n!

X vn tn
V (t) =
n!

n≥1

n≥1

yra grafu‘ klasiu‘ U bei V eksponentinės generuojančios funkcijos (EGF). Plokščiu̧ju̧ grafu̧
W = U ∗ V EGF
(4)

W (t) =

X wn tn
= U (t)V (t).
n!

n≥1

Viso plokščiu̧ju̧ grafu̧ komplekso U <∗> EGF lygi
U <∗> (t) = (1 − U (t))−1 ,

(5)

o (neplokščiu̧ju̧) grafu̧ komplekso U [∗] EGF yra
U [∗] (t) = eU (t) .

(6)

Irodymas. Pastebėkime, kad n eilės sutvarkytu̧ numeruotu̧ poru̧ w = (u, v) galime
sudaryti
n µ ¶
X
n
wn =
uk vn−k ,
k
‘

k=0

nes pastaroji lygybė nurodo, kad fiksuotoje sandaugoje viena komponentė yra k, o kita –
(n − k) eilės, be to, pirmoji komponentė yra numeruota bet kokiu k indeksu‘ poaibiu iš
{1, . . . , n}. Taigi,
n
X
wn
uk vn−k
=
.
n!
k! (n − k)!
k=0

Iš čia išplaukia (4) formulė.
Pasinaudoje‘ ja bei (2) lygybe, gauname
U <∗> (t) =

X
n≥0

U <n> (t) =

X
n≥0

58

U (t)n = (1 − U (t))−1 .

Neplokščiu̧ju̧ grafu̧ kompleksui, pasinaudoje‘ (1), turime bei
U [∗] (t) =

X

U <n> (t) =

n≥0

X 1
U (t)n = eU (t) .
n!

n≥0

¦
Iš 1 teoremos išplaukia i‘domiu‘ kompleksu‘ generuojančiu‘ funkciju‘ savybiu‘.
Išvada. Tegu
X dn tn
X nn−1 tn
D(t) :=
=
n!
n!
n≥1

n≥1

yra Cayley’io medžiu‘ EGF. Tada D(t) = teD(t) , kai |t| < e−1 .
Irodymas. Pasinaudoje‘ Stirlingo formule, nesunkiai nustatome eilutės D(t) konverga‘
vimo sriti‘ |t| < e−1 . Pastebime, kad šakniniai miškai sudaro Cayley’io medžiu‘ kompleksa̧.
Vadinasi, pagal 1 teorema‘ ju‘ EGF išsireiškia per D(t). Gauname
Q(t) :=

X qn tn
= eD(t) .
n!

n≥0

Pagal 7 slyrelio teorema‘ qn = dn+1 /(n + 1), todėl
Q(t) =

X dn+1 tn
= t−1 D(t).
(n + 1)!

n≥0

Išvada i̧rodyta.
Panašiai, funkciniu‘ digrafu‘ klasės EGF tenkina lygybe‘
½X
¾
X nn
π(n) n
n
T (y) =
y = exp
y ,
n!
n!
n≥0

¦

n≥1

čia π(n) – jungiu‘ funkciniu‘ digrafu‘ skaičius. Kadangi funkciniai digrafai yra jungiu‘ digrafu‘
nesutvarkytieji rinkiniai ir funkciniai digrafai yra jungiu‘ digrafu‘ generuotas kompleksas,
pastarasis sa‘ryšis irgi yra 1 teoremos išvada. Naudojant šia‘ lygybe‘ nebesunku rasti π(n)
bei jo asimptotika‘, kai n → ∞.
lygi

Savarankiškai išnagrinėkite kita‘ pavyzdi‘ ir i̧sitikinkite, kad keitiniu‘ ciklu‘ klasės EGF
X (n − 1)!
tn = log(1 − t)−1 .
n!

n≥1

Ciklus galime sudarinėti ir iš kitokiu‘ negu skaičiai kombinatoriniu‘ struktūru‘, pvz.,
medžiu‘. Kokia bus EGF, jei pradėsime nuo struktūru‘ klasės su EGF A(t)?
59

Panašiai išvystoma ir nenumeruotu‘ju‘ grafu̧ suskaičiavimo teorija. EGF yra pakeičiamos laipsninėmis generuojančiomis funkcijomis.
9. Grafu‘ teorijos ir algebros sa‘ryšiai
Visa‘ informacija‘ apie grafus galime užrašyti matricomis. Tuo tikslu reikia skaičiais
{1, 2, ..., n} sunumeruoti grafo viršūnes. Pažymėkime aij kieki‘ briaunu‘, jungiančiu‘ i-a‘ja‘ ir
j-a‘ja‘ viršūnes multigrafe G, kai i 6= j, ir aii - dviguba‘ kilpu‘, išvestu‘ iš i viršūnės, skaičiu‘.
Kvadratinė matrica A = ((aij )), 1 ≤ i, j ≤ n, vadiname multigrafo gretimumo matrica.
Jei multigrafas neturi kilpu‘, tai matricos pagrindinėje i‘strižainėje yra nuliai. Gretimumo
matrica yra simetrinė.
Norėdami užfiksuoti, kurios briaunos jungia kurias viršūnes, i‘vedame dar viena‘ matrica‘. Dabar skaičiais {1, 2, ..., m} sunumeruojame ir briaunas. Multigrafu‘ atveju, žinoma,
numeruojamos visos briaunos bei kilpos.
Matrica‘ BG = B = (bij ), 1 ≤ i ≤ n, 1 ≤ j ≤ m, vadiname multigrafo (grafo)
incidentumo matrica, jei


 1,
bij = 2,


0,

jei i viršūnė yra incidenti j briaunai, kuri nėra kilpa,
jei i viršūnė yra incidenti j briaunai, kuri yra kilpa,
jei i viršūnė nėra incidenti j briaunai.

Apibrėžiant digrafo gretimumo bei incidentumo matricas, atsižvelgiama i‘ briaunos
krypti‘. Gretimumo matricos elementai aij lygūs skaičiui briaunu‘, išvestu‘ iš i-tos i‘ j-1
viršūne‘. Kilpos atveju skaičius nebedvigubinamas. Digrafo gretimumo matrica nebūtinai
simetrinė.
Bekilpiam digrafui incidentumo matricos elementai


 1,
bij =
−1,


0,

jei i yra pradinė j briaunos viršūnė,
jei i yra galinė j briaunos viršūnė,
i viršūnė nėra incidenti j briaunai.

Jei i viršūnė yra incidenti kilpai, pažymėtai j numeriu, tai dažnai vartojamas žymuo
bij = −0.
Pateiksime viena‘ i‘vestu‘ju‘ matricu‘ sa‘ryši‘.
1 teorema. Tarkime G - numeruotas multidigrafas be kilpu‘ , A ir B – jo gretimumo
ir incidentumo matricos atitinkamai. Tada
BB 0 = D − A.
Čia 0 žymi matricos transponavima‘ , o D – diagonali matrica, kurios ‘istrižainėje yra iš eilės
surašyti viršūniu‘ laipsniai.
60

Irodymas. Jei cij – matricos BB 0 bendrasis narys, tai

‘

(1)

cij =

m
X

bil bjl .

l=1

Todėl, kai i 6= j, sandauga bil bjl lygi 0 arba -1. Pastaroji lygybė yra teisinga tik tuo
atveju, kai xi xj = el . Sudedant pagal l, -1 dauginsis iš tokio skaičiaus, kiek yra briaunu‘,
jungiančiu‘ xi ir xj .
Kai i = j, cii yra matricos i‘strižainės narys. Matrica A turi nuline‘ i‘strižaine‘. (1)
suma lygi briaunu‘, išvestu‘ iš xi skaičiui.
Teorema i‘rodyta.
Tarkime G = (V, E) - n eilės ir m didumo grafas. Nagrinėkime funkciju‘ erdve‘
F0 (G) := {f : V → R}
funkciju‘ sudėties kiekviename taške bei daugybos iš skaliaro atžvilgiu. Funkcija‘ f nusako
jos reikšmės viršūnėse f (xj ) =: cj , 1 ≤ j ≤ n. Todėl F0 (G) izomorfiška Rn , o jos dimensija
lygi n. Jos standartinė bazė bus funkciju‘ rinkinys f1 , . . . , fn , kai funkcija fj apibrėžiama
lygybėmis
fj (xi ) = δij .
Čia δij - Kronekerio simbolis. Dabar lygybė
f (x) =

n
X

cj fj (x)−

j=1

funkcijos f išraiška standartine baze. I‘ vedus skaliarine‘ daugyba‘
0

00

< f , f >:=

n
X

c0j c00j

j=1

erdvė tampa Euklido erdve, šios daugybos atžvilgiu standartinė bazė yra ortonormuota.
Panašiai i‘vedama ir m - matė erdvė funkciju‘, apibrėžtu‘ grafo briaunu‘ aibėje:
F1 (G) := {g : E → R}.
Ji yra izomorfiška erdvei Rm .
I‘ domesnis ir svarbesnis digrafu‘ atvejis. Tegu toliau briaunos sunumeruotos skaičiais
nuo 1 iki m ir joms priskirtos kryptys. Turėdami cikla‘ L, sudaryta‘ iš briaunu‘ ei1 , . . . , eik ,
kur ei1 vienas galas sutampa su eik galu, ir fiksuodami ciklo krypti‘ (sakysim, prieš laikrodžio rodykle‘ plokščiajame digrafe), ciklui galime priskirti ciklo vektoriu‘ z̄L = (z1 , . . . , zm ),
iš 1,-1 arba 0:
61



 1, jeigu ej priklauso ciklui ir eina ciklo kryptimi;
zj =
−1, jeigu ej priklauso ciklui, bet jo kryptis priešinga;


0, jeigu ej nepriklauso ciklui.
Naudojamas ir kitas vaizdus vektoriaus z̄L užrašas
z̄L =

m
X

zj ej ,

j=1

neteikiant šioje sumoje jokios geometrinės prasmės, i‘prastos vektoriams, briaunoms ej ,
nors jos turi ir kryptis.
Kai L perbėgs visus grafo ciklus, gausime aibe‘ funkciju‘ {gL }, ju‘ tiesinis apvalkas
Z(G) erdvėje F1 (G) vadinamas ciklu‘ poerdviu. Jo dimensija dimZ(G) vadinama grafo G
ciklomačiuoju skaičiumi.
Sudarykime dar viena‘ erdvės F1 (G) poerdvi‘. Imkime viršūniu‘ aibės skaidini‘ P :
V = V1 ∪ V2 , V1 ∪ V2 = ∅.
Nagrinėkime tik tas briaunas, kurios eina iš V1 i‘ V2 arba atvirkščiai. Ši briaunu‘ aibė
vadinama pjūvio aibe. Sudarykime vektoriu‘ ūP = (u1 , . . . , um ) ∈ Rm


 1, jeigu ej eina iš V1 i‘ V2 ;
uj =
−1, jeigu ej eina iš V2 i‘ V1 ;


0, jeigu ej nejungia V1 su V2 .
dažnai užrašoma‘ suma
ūP =

m
X

u j ej

j=1

arba funkcija
gP (e) =

m
X

uj gj (e),

e ∈ E,

j=1

čia - gj , 1 ≤ j ≤ m, standartinė funkciju‘ bazė. Imant visus i‘manomus skaidinius P ,
gaunama funkciju‘ gP sistema, jos tiesinis apvalkas U (G) erdvėje C1 (G) vadinamas pjūviu‘
poerdviu (kociklu‘ poerdviu).
2 teorema. Briaunu‘ funkciju‘ erdvė - tiesioginė tarpysavyje ortogonaliu‘ poerdviu‘ Z(G)
ir U (G) suma. Jei grafas G turi n viršūniu‘ , m briaunu‘ ir k jungumo klasiu‘ , tai
dim Z(G) = m − n + k,
62

dim U (G) = n − k.

Irodymas. Tikriname teoremoje nurodytu‘ poerdviu‘ ortogonaluma‘. Imame bet koki‘
cikla‘ L ir bet koki‘ skaidini‘ P bei funkciju‘ koordinačiu‘ vektorius z̄L ir ūP ir skaičiuojame
< z̄L , ūP >. Nenuliniai šios skaliarinės sandaugos dėmenys atitiks tik L ciklo briaunoms,
priklausančioms ir P pjūviui. Ju‘ skaičius yra lyginis. Susitarkime laikyti, kad briauna
−ej , eina ciklo kryptimi, jei ej kryptis buvo priešinga ciklo krypčiai. Tada nagrinėjama
skaliarinė sandauga lygi kiekiui L ciklo briaunu‘, einančiu‘ iš V1 i‘ V2 minus kiekiui ciklo
briaunu‘, einančiu‘ iš V2 i‘ V1 . Vadinasi, ji yra lygi nuliui. Tuo pačiu poerdviu‘ ortogonalumas
i‘rodytas.
Teoremoje nurodytos dimensiju‘ formulės išplauks iš nelygybiu‘
‘

(1)

dim Z(G) ≥ m − n + k,

dim U (G) ≥ n − k.

Tarkime pradžioje, kad G - jungus grafas, k = 1. Imkime karkasini‘ medi‘ T . Tarkime,
kad medyje panaudotos e1 , . . . , en−1 briaunos, o likusios en , . . . , em buvo nepanaudotos.
Prijungimas bet kurios iš šiu‘ briaunu‘ sukuria 1 cikla‘. Ji‘ vadinsime fundamentaliuoju ciklu.
Tegu Lj , n ≤ j ≤ m, vienas iš šiu‘ fundamentaliu‘ ciklu‘, o z̄j - jo vektorius. Atkreipkime
dėmesi‘ i‘ paskutines m − (n − 1) koordinačiu‘. Kai j = n, pirmoji iš šiu‘ koordinačiu‘ lygi
1 ar -1, o kitos lygios nuliui. Panašiai, kai j = m, visos minėtos koordinatės , išskyrus
paskutine‘, lygios nuliui, o paskutinioji lygi 1 arba -1. Iš čia išplaukia vektoriu‘ sistemos
z̄j , n ≤ j ≤ m nepriklausomumas. Pirmoji iš (1) nelygybiu‘ i‘rodyta.
Nagrinėdami pjūvius irgi panaudokime karkasini‘ medi‘. Pastebėkime, kad bet kokios
T briaunos ej , 1 ≤ j ≤ n − 1, išmetimas duotu‘ pjūvi‘ Pj , (V = Vj0 ∪ Vj00 , Vj0 ∩ Vj00 = ∅), o
pati briauna ej jungtu‘ viena‘ viršūniu‘ aibe‘ su kita. Tarkime, kad ej pradžios viršūnė yra
aibėje Vj0 . Dabar šio pjūvio vektorius
ūj = (u1j , . . . , uij , . . . , un−1,j )
turės ujj = 1, o uij = 0, kai i 6= j, nes nejungia Vj0 su Vj00 . Akivaizdu, jog tiesiškai
nepriklausomu‘ tokiu‘ vektoriu‘ sudarytume ne mažiau, negu n − 1. Taigi jungaus grafo
atveju (1) lygybės i‘rodytos.
Kai G grafas turi jungumo klases G1 . . . , Gk , funkciju‘ erdvė F1 (G) yra tiesioginė
suma ortogonaliu‘ tarpusavyje funkciju‘ erdviu‘ F1 (Gj ), 1 ≤ j ≤ k, kurios pagal i‘rodyta‘
dali‘ išsiskaido dvieju‘ ortogonaliu‘ poerdviu‘ sumomis. Be to, Z(G) ∩ F1 (Gj ) = Z(Gj ) bei
U (G) ∩ F1 (Gj ) = U (Gj ),
dim U (G) = dim U (G1 ) + · · · + dim U (Gk ) = (n1 − 1) + · · · + (nk − 1) = n − k.
Čia |Vi | = ni ir n1 + · · · + nk = n.
2 teorema i‘rodyta.
Pritaikykime i‘gytas žinias elektros grandiniu‘ uždaviniuose. Elektros grandinės, kaip
žinoma, tenkina Kirchhofo srovės dėsni‘ kiekvienoje viršūnėje. Jis teigia, kad srovės, i‘ėjusios
i‘ viršūne‘, didumas lygus išėjusios iš jos srovės didumui. Ši‘ dėsni‘ galime užrašyti naudojant
63

incidentumo matrica‘ B. Tarkime w = (w1 , . . . , wm )0 – srovės vektorius stulpelis, sudarytas
iš sroviu‘, tekančiu‘ visomis briaunomis, tai matricu‘ lygybė
Bw = 0 = (0, . . . , 0)0
apima srovės dėsnius visose viršūnėse iš karto. Ieškant sroviu‘ didumu‘, tektu‘ spre‘sti šia‘
homogenine‘ lygčiu‘ sistema‘. Todėl imtume tik tiesiškai nepriklausomos incidentumo matricos eilutes.
Panašiai elgiamasi ir potencialu‘ atveju. Jei z̄L - L ciklo vektorius, o p̄ = (p1 , . . . , pm )
- potencialu‘ skirtumu‘ vektorius, tai Kirchhoff’o potencialu‘ dėsnis teigia, jog potencialu‘
skirtumu‘ uždaroje grandinėje (viename cikle) suma lygi nuliui, t.y.
< z̄L , p̄ >= 0.
Kadangi grandinėje gali būti daug tarpusavyje priklausomu‘ ciklu‘, nebūtina juos visus
naudoti. Iš tiesu‘, vektoriai z̄L priklauso ciklu‘ poerdviui Z(G), kurio dimensija lygi m−n+1
(grandinė yra jungi, k = 1), todėl pakanka naudoti tik fundamentaliuosius ciklu‘ vektorius.
Surade‘ karkasini‘ medi‘ T , išvesta‘ sakykim, per briaunas e1 , ..., en−1 imkime paeiliui likusias
briaunas en , ..., em . Tarkime gautu‘ju‘ ciklu‘ vektoriai z̄j , n ≤ j ≤ m surašyti eilutėmis,
sudaro matrica‘ C, (m − n + 1) × m, tada visa informacija apie potencialus užrašoma
matricine lygybe.
Kirchhoff ’o potencialu‘ dėsnis. Jei C fundamentaliu‘ ju‘ ciklo vektoriu‘ sudaryta
matrica, o p̄ - potencialu‘ skirtumu‘ vektorius stulpelis, tai
C p̄ = 0.
Grafu‘ teorijoje nagrinėjami ir bendresni srautai.
Priedas. Tipiniai i‘skaitos bilietai
(I‘ skaita duodama tik už 4 balus !)
1. (3 balai) Išvesti netvarkingu‘ju‘ keitiniu‘ skaičiaus formule‘
Dn = n!

n
X
(−1)k
k=0

k!

.

2. (2 balai) Rasti sekos {un }, n ≥ 0, bendra‘ji‘ nari‘, jei u0 = 1/4, u1 = 1, u2 = 2 ir
un+3 − un+2 − un+1 + un = 0.
3. (1 balas) Apibrėžkite binaru̧ji̧ medi̧ ir suformuluokite pasirinktinai viena‘ teigini‘
apie ji̧.
64

4. (1 balas) Užrašykite digrafo G = (V, E), čia
V = {x1 , . . . , x10 }
yra viršūniu‘ aibė, o
E = {x1 x2 , x1 x5 , x2 x4 , x4 x5 , x4 x7 , x5 x6 , x7 x6 , x8 x9 , x9 x8 , x10 x9 } −
lanku‘ aibė, gretimumo matrica‘ bei raskite penkis jo skaitinius parametrus.
Kitas variantas
1. (3 balai) I‘ rodykite, kad kiekvienas plokščias grafas yra penkiaspalvis.
2. (2 balai) Išveskite lygybe‘
n µ ¶
X
2n+2 − 1
1
n
1
−
=
,
(n + 1)(n + 2) n + 1
k (k + 1)(k + 2)

n ≥ 1.

k=0

3. (1 balas) Apibrėžkite kartotinius gretinius ir užrašykite ju‘ skaičiavimo formule‘.
4. (1 balas) Raskite numeruotojo medžio, kurio Priūferio kodas yra
α = {1, 1, 5, 4, 4, 1, 5, 6},
lapu‘ skaičiu‘.

65