Primož Potočnik
Zapiski predavanj iž Diskretne Matematike I
Ljubljana, marec 2011
Naslov: Zapiski predavanj iz Diskretne Matematike I Avtor: Primoz Potočnik 1. izdaja
Dostopno na spletnem naslovu www.fmf.uni-lj.si/~potocnik
CIP - KataloZni zapis o publikaciji Narodna in univerzitetna knjiznica, Ljubljana
519.11(0.034.2) 519.17(0.034.2)
POTOČNIK, Primoz, 1971 -
Zapiski predavanj iz Diskretne Matematike I [Elektronski vir] Primoz Potočnik. - 1. izd. - El. knjiga. - Ljubljana : samozal., 2011
Način dostopa (URL):
http://www.fmf.uni-lj.si/~potocnik/Ucbeniki/DM-Zapiski2010.pdf
ISBN 978-961-93056-1-4 255519488
Izdano v samozalozbi marca 2011. Avtor si pridrzuje vse pravice.
Kazalo
1	Osnovna načela preštevanja......................................1
1.1	S čim se ukvarja diskretna matematika..................1
1.2	Tri nacela prestevanja....................................1
2	Izbori ..............................................................4
2.1	Urejeni izbori s ponavljanjem............................4
2.2	Urejeni izbori brez ponavljanja..........................5
2.3	Neurejeni izbori brez ponavljanja........................6
2.4	Neurejeni izbori s ponavljanjem..........................8
2.5	Ponovno o igri loto........................................10
2.6	Permutacije mnozic in multimnozic......................10
2.7	Binomski simboli in Pascalov trikotnik..................11
3	Nacelo vkljucitev in izkljucitev..................................15
3.1	Unija dveh mnozic........................................15
3.2	Unija poljubno mnogo mnozic............................15
4	Razbitja mnozic in razclenitve stevil............................18
4.1	Stirlingova stevila druge vrste............................18
4.2	Lahova stevila ............................................21
4.3	Stirlingova stevila prve vrste ............................23
4.4	Stevilo razcelnitev naravnega stevila....................24
4.5	Prostori polinomov in Stirlingova ter Lahova stevila .	25
5	Porazdelitve, barvanja in preslikave..............................27
5.1	Preslikave..................................................28
5.2	Ekvivalencni razredi preslikav - dvanajstera pot ....	28
6	Delovanja grup in prestevanje orbit..............................32
6.1 Permutacije ................................................32
6.2	Množenje permutacij in simetrična grupa..............33
6.3	Delovanja grup............................................34
6.4	Stabilizatorji in orbite delovanja ........................35
6.5	Preštevanje orbit in Cauchy-Frobeniusova lema ....	37
6.6	Delovanje grupe na funkcijah............................38
6.7	Ciklični indeks delovanja grupe..........................39
6.8	Izrek Redfielda in Polya..................................40
7	Rekurzivne enačbe................................................42
7.1	Fibonaccijevo zaporedje..................................42
7.2	Prostor zaporedij ..........................................43
7.3	Linearne rekurzivne enacbe s konstantnimi koeficienti	43
7.4	Linearne nehomogene enacbe s konstantnimi koeficienti	45
8	Osnovno o grafih..................................................47
8.1	Definicija in osnovni pojmi ..............................47
8.2	Metricne lastnosti ........................................48
8.3	Nekatere druzine grafov..................................49
9	Izomorfizmi in avtomorfizmi......................................53
9.1	Izomorfnost grafov........................................53
9.2	Avtomorfizmi grafov......................................55
10	Drevesa ............................................................57
10.1 Vpeta drevesa ............................................58
11	Eulerjevi in hamiltonovi grafi....................................60
11.1	Eulerjevi grafi..............................................60
11.2	Hamiltonovi grafi..........................................60
12	Povezanost in Mengerjev izrek....................................62
12.1	Mengerjev izrek ............................................62
12.2	2-povezani grafi in bloki ..................................63
13	Ravninski grafi in Eulerjeva formula ............................64
13.1	Eulerjeva formula ..........................................64
13.2	Izreka Wagnerja in Kuratowskega........................66
14	Barvanja grafov....................................................68
14.1	Barvanje tock..............................................68
14.2	Barvanje povezav ..........................................69
1 Osnovna načela preštevanja
1.1	S čim se ukvarja diskretna matematika
Diskretna matematika se pretezno ukvarja s koncnimi in stevnimi mnozicami ter relacijami na njih. Na kratko, ukvarja se z razlicnimi tipi diskretnih struktur. Med bolj poznane naloge, s katerimi se ukvarja diskretna matematika, so naloge prestevanja. Delu diskretne matematike, ki obravnave taksne naloge, recemo preštevalna kombinatorika. Poleg prestevalne kombinatorike pa moderna diskretna matematika zdruzuje se vrstno drugih matematicnih podrocij, kot so: teorija grafov, teorija koncnih geometrij, teorija kombinatoricnih nacrtov itd.
1.2	Tri načela preštevanja
Ce matematik zeli presteti kake objekte s predpisanimi lastnostmi, to obicaj-no stori v dveh korakih: Najprej objekte, ki jih presteva, zdruzi v mnozico, nato pa tej mnozici doloci njeno moš (tudi kardinalnost). Pri dolocanju moci dane mnozice, si veckrat pomagamo z nekaj preprostimi naceli. Navedimo tri izmed njih.
Nacelo produkta
Mnogokrat si lahko elemente mnozice A, ki jo prestevamo, predstavljamo kot urejene n-terice, katerih i-ta komponenta pripada mnozici Ai. V tem primeru si lahko pomagamo z načelom produkta, ki pravi, da je moc karte-zicnega produkta danih mnozic enaka produktu njihovih moci:
nn
i n Aii = n lAii.
i=1 i=1
Tipicen zgled uporabe tega nacela so naloge z vecfaznim izbiranjem. Denimo, da je kombinatoricni objekt podan z zaporedjem n izbir, pri cemer v i-tem koraku izbiramo izmed moznostmi v mnozici Ai. Taksnen kombinatoricni objekt lahko enacimo z urejeno n-terico izbir A1 x ... x An. Stevilo vseh taksnih objektov je tedaj enako produktu moci mnozic Ai. Oglejmo si konkretno nalogo:
Zgled. Študentsko kosilo je sestavljeno iz predjedi, glavne jedi in sladice. Za predjed si lahko izberemo govejo juho z rezanci ali zelenjavno juho z jušnimi kroglicami. Za glavno jed imamo na razpolago puranji zrezek v gobovi omaki,
sardele na čaru ali ocvrt sir. Sladica je bodisi jabolko bodisi čokoladna rezina. Koliko različnih kosil si lahko sestavi študent?
Rešitev: Kosilo lahko opišemo kot urejeno trojico, kjer prva komponenta predstavlja predjed, druga komponenta glavno jed in tretja komponenta
Načelo vsote
Kadar elemente množice A (katere moC želimo doloCiti) razporedimo v nekaj med seboj disjunktnih podmnožic Ai, A2,..., An, katerih moCi poznamo, lahko moc množice A dolocimo na podlagi nacela vsote, ki pravi, da je moc unije paroma disjunktnih množic enaka vsoti njihovih moCi:
S tem preprostim nacelom lahko na videz zapleteno nalogo (prestevanje elementov mnozice A) prevedemo na vec nekoliko manj zapletenih kombi-natoricnih nalog (prestevanje elementov podmnozic Ai).
Zgled. Varnostno geslo je sestavljeno iz osmih znakov. Vsaj en in največ trije znaki gesla morajo biti stevilke (med 0 in 9), ostali pa črke slovenske abecede. Koliko različnih gesel lahko sestavimo?
Rešitev: Varnostna gesla razdelimo v tri skupine A1, A2 in A3, pri cemer v skupino Ai razvrstimo tista gesla, ki so sestavljena iz i stevilk in 8 — i crk. Mnozice A1, A2 in A3 so paroma disjunktne, njihova unija pa je mnozica vseh varnostnih gesel. Iskano stevilo je zato enako vsoti moci mnozic A1, A2 in A3.
Moc mnozice Ai, i G {1,2,3}, lahko dolocimo s pomočjo nacela produkta. Mislimo si, da geslo iz mnozice Ai izberemo v treh fazah. V prvi fazi izberemo i pozicij izmed osmih moznih pozicij za stevilke v geslu. Kdor je seznanjen s srednjesolsko kombinatoriko, ve, da je taksnih izbir (8). V drugi fazi pa izberemo urejeno i-terico stevilk med 0 in 9, ki jih razvrstimo na i pozicij, ki smo jih izbrali v 1. fazi. Teh izbir je 10i. Nazadnje izberemo se urejeno (8 — i)-terico crk, ki jih razvrstimo na preostalih 8 — i pozicij varnostnega gesla. Taksnih izbir je 258-i. Vseh varnostnih gesel je zato
sladico. Razlicnih kosil je tako 2 ■ 3 ■ 2 = 12.
n
n
Ai n Aj = 0 za i = j ^ |[J Ai| = ^2 |Ai|.
i=1
i=1
|A11 + |A2| + |A3| = Q
■ 10■257 +
7
■ 102■256+ ■103■255 « 1,7■1012.
2
6
Nacelo enakosti
Iz definicije moci (kardinalnosti) mnozice sledi, da imata mnozici A in B enako moc, brz ko med njima obstaja bijektivna preslikava.
3f: A ^ B, bijekcija ^ |A| = |B|.
Na tem dejstvu sloni morda najpogosteje uporabljen prijem v kombinatoriki: Ce zelimo presteti elemente mnozice A, je dovolj poiskati bijektivno preslikavo iz mnozice A v kako mnozico B, katere moc ze poznamo.
Zgled. Naj bo X množica z n elementi. Koliko podmnožic premore množica X ?
Rešitev: Naloga sprasuje po moci potenžne množice PX mnozice X. Resili jo bomo tako, da bomo nasli bijektivno preslikavo med mnozico PX in mnozico vseh urejenih n-teric z elementi iz mnozice Z2 = {0,1}. Oznacimo elemente mnozice X z xi, x2,..., xn. Poljubni podmnozici B G PX priredimo karakteristižni vektor x(B) = (a\,..., an) G Zn, za katerega je ai = 1, ce je xi G B, in ai = 0 sicer. Na ta nacin smo definirali preiskavo x: PX ^ Zn. Ni se tezko prepricati, daje preslikava x bijektivna, zato je |PX | = |Zn| = 2n. Pri slednji enakosti smo seveda uporabili nacelo produkta.	■
2 Izbori
Razdelek pričnimo z naslednjim zgledom. Pri igri loto se v bobnu nahaja 39 kroglic, ostevilcenih s stevili 1,2,..., 39. Organizator igre iz bobna zaporedoma sedemkrat izvleče po eno kroglico. Na koliko načinov lahko to stori?
Odgovor je odvisen od tega, kako razumemo besedo "način". Osnovni dilemi pri razumevanju naloge sta, ali naj kroglico, ki smo jo v posameznem koraku izvlekli, vrnemo v boben in ali je za nas vrstni red izvlečenih kroglič pomemben. Ti dve dilemi mora seveda razresiti tisti, ki nam je nalogo zastavil. Od njegovega odgovora je odvisno, kako bomo nalogo resevali.
Kadar je za zastavljalca naloge vrstni red pomemben, bomo prestevali urejene izbore, ki jim zaradi zgodovinskih razlogov recemo tudi variacije. Ce kroglice vracamo v boben, bomo govorili o variacijah s ponavljanjem, sicer pa o variacijah brez ponavljanja. Ce pa vrstni red ni pomemben, bomo steli neurejene izbore, ki jih imenujemo tudi kombinacije. Podobno kot prej govorimo o kombinacijah s ponavljanjem in brez ponavljanja - odvisno od tega, ali kroglice vracamo v boben ali ne.
V nadaljevanju si bomo vsako od stirih moznih interpretacij naloge ogledali nekoliko podrobneje. Za lazjo izrazavo bomo rezultat vlecenja kroglic imenovali žreb. Mnozico 39 kroglic oznacimo z N = {1,2,..., 39}.
2.1 Urejeni izbori s ponavljanjem
Denimo, da izvlecene kroglice v boben vracamo, vrstni red izvlecenih kroglic pa je pomemben. Tedaj lahko rezultat zreba enolicno predstavimo z urejeno sedmerico elementov mnozice kroglic N, pri cemer urejeno sedmerico (a1, ..., a7) razumemo kot tisti zreb, pri katerem v i-tem poskusu izvlecemo kroglico ai £ N. To nas napelje na idejo, da urejeni izbor s ponavljanjem definiramo na naslednji nacin.
Definicija 2.1 Naj bo N poljubna množica in r poljubno naravno stevilo. Urejeni r-terici (a1, a2,..., ar) elementov mnozice N reCemo urejeni izbor elementov mnozice N dolzine r. Ce želimo poudariti, da so lahko nekateri izmed elementov ai med seboj tudi enaki, dodamo, da gre za urejeni izbor s ponavljanjem. Množico vseh takžnih izborov označimo s simbolom V (N, r).
opomba. Urejeni izbor elementov n-elementne množice dolžine r v literaturi imenujejo tudi variacija s ponavljanjem n elementov reda r.
Ker mnozica V (N, r) vsebuje vse urejene r-terice elementov mnozice N, je enaka kartezicnemu produktu r kopij mnozice N:
V (N, r) = N x N x ... x N
r
Od tod (in z upostevanjem nacela produkta) neposredno sledi naslednja trditev.
Trditev 2.2 Naj bo N poljubna množica z n elementi in r poljubno naravno stevilo. Tedaj množica V (N, r) premore nr izborov.
2.2 Urejeni izbori brez ponavljanja
Se naprej si mislimo, da je vrstni red izvlecenih kroglic pomemben, le da tokrat izbranih kroglic v boben ne vračamo. Tako kot prej si zreb, v katerem v i-tem koraku izberemo kroglico ai, predstavimo z urejeno sedmerico (a1,...,a7) elementov ai G N. Ker kroglic ne vracamo, so elementi ai paroma razliCni. Po drugi strani pa vsaka sedmerica paroma razlicnih elementov mnozice N predstavlja kak zreb. Moznih zrebov je torej toliko, kot je razlicnih sedmeric paroma razlicnih kroglic v bobnu. Povedano povzemimo v naslednjo formalno definicijo urejenega izbora brez ponavljanja.
Definicija 2.3 Urejeni r-terici paroma razlicnih elementov mnoZice N reCe-mo urejeni izbor elementov mnozice N dolzine r brez ponavljanja. MnoZico vseh taksnih izborov oznacimo s simbolom V (N, r).
Urejenih izborov brez ponavljanja je seveda nekoliko manj kot vseh urejenih izborov. Preden jih prestejemo, vpeljimo naslednji funkciji naravnih Sstevil n in r:
n- = n(n — 1) ■ ■ ■ (n — r + 1), n! = nn = n(n — 1) ■ ■ ■ 1
in dodatno definirajmo se n0 = 0! = 1 za vsak n G No. Simbolu n- recemo padajoča potenca stevila n, simbolu n! pa n fakulteta (tudi faktoriela).
Trditev 2.4 Naj bo N poljubna mnozica z n elementi in r poljubno naravno stevilo. Tedaj mnozica V (N, r) premore n- izborov.
Dokaz: Formalni dokaz trditve je najlazje izpeljati z indukcijo na dolzino izbora r. Ce je r = 1, je tipicni izbor oblike (a), kjer je a element
mnozice N. Ker je elementov mnozice N ravno n, je toliko tudi izborov. Formula torej drzi za r = 1.
Pa denimo, da za neki k formula drzi za vse r < k. Dokazimo, da velja tudi za r = k + 1. Res! Oznacimo elemente mnozice N s simboli ai,..., an. Izbore iz V (N, k+1) razvrstimo v n skupin, R1,..., Rn, pri cemer v skupino Ri razvrstimo vse izbore, ki imajo na prvem mestu element ai. Ce izboru (ai, x1,..., xk) iz mnozice Ri odrezemo prvo komponento, dobimo "ostanek" (x1,... , xk), ki je izbor iz V (N \ {ai}, k). Pri tem se vsak izbor iz V (N \ {ai}, k) pojavi natanko enkrat kot "ostanek" izbora iz skupine Ri. Zato je v vsaki skupini Ri natanko toliko izborov, kot je izborov v mnozici V (N \ {ai},k); teh pa je, kot zagotavlja indukcijska predpostavka, (n — 1)k. Vseh iskanih izborov je tako n(n — 1)k = n^+3 = nr. S tem je indukcijski korak dokazan.	I
Za razliko od urejenih izborov s ponavljanjem, kjer je dolzina izbora poljubno velika, je dolzina urejenega izbora brez ponavljanja omejena s stevilom elementov, ki jih izbiramo. Z drugimi besedami,
V (N, r) = 0, brz ko je r> |N|.
Urejenim izborom elementov mnozice N brez ponavljanja najdaljse dopustne dolzine (torej dolzine r = |N|) recemo tudi permutacija mnozice N. Iz trditve 2.4 neposredno sledi naslednje:
Trditev 2.5 Stevilo vseh permutacij n-elementne množice je enako
Opomba. Permutacijo (ai,..., an) mnozice N lahko razumemo tudi kot linearno ureditev elementov mnozice N, pri kateri je a1 "prvi" element, ki mu "sledi" element a2 in tako dalje, vse do "zadnjega" elementa an. Ce pa so elementi mnozice N ze vnaprej podani z nekim vrstnim redom (npr. ce je N = {1, 2,..., n}) pa lahko na permutacijo (a1,..., an) pogledamo tudi kot na bijektivno preslikavo iz mnozice N vase, ki i-temu elementu mnozice N priredi element aj.
nn = n!.
2.3 Neurejeni izbori brez ponavljanja
Mislimo si sedaj, da vrstni red izbranih kroglic ni pomemben, izbranih kroglic pa ne vračamo v boben. V tem primeru lahko izid zreba enolicno podamo z množico sedmih izzrebanih kroglic. Moznih izidov zreba je torej toliko, kot je vseh sedemelementnih podmnozic mnozice kroglic N. To nas napelje na naslednjo definicijo.
Definicija 2.6 Naj bo N poljubna množica z n elementi in r poljubno nenegativno celo stevilo. Tedaj r-elementni podmnožici množice N režemo neurejeni izbor elementov mnozice N brez ponavljanja dolzine r. MnoZico vseh taksnih izborov oznacimo s simbolom K(N, r) njihovo stevilo pa s simbolom
(n) = K^r)^
ki mu pravimo binomski simbol (tudi binomski koeficient) in ga preberemo "n nad r".
opomba. Za mnozico K(N, r) vseh r-elementnih podmnozic mnozice N je v navadi vec razlisnih simbolov, med drugim tudi simbol (^f), ki je morda zaradi svoje podobnosti z binomskim simbolom prirocnejsi za pomnjenje.
Trditev 2.7 Za poljubni nenegativni celi števili n in r velja enakost
(n\ n-\r) r! '
Dokaz: Naj bo N poljubna n-elementna mnozica in r poljubno nenega-tivno celo stevilo. Za r = 0 trditev preide v stavek, da poljubna mnozica premore natanko eno podmnozico z 0 elementi. Ker je prazna mnozica edina 0-elementna mnozica, je slednje ocitno pravilno. Predpostavimo torej lahko, da je r > 1.
Trditev bomo dokazali tako, da bomo ponovno presteli vse urejene izbore brez ponavljanja iz mnozice V (N, r). Za A G K(N, r) definirajmo naslednjo mnozico urejenih izborov:
Ra = {(a1,..., ar) : {a1,..., ar} = A}.
Opazimo, da je Ra natanko mnozica vseh permutacij mnozice A, zato je |Ra| = r!. Ker se vsak izbor iz V (N, r) pojavi v natanko eni od mnozic Ra (namrec tisti, za katere je mnozica njegovih komponent enaka A), je stevilo vseh taksnih izborov enako (n)r!. Iz trditve 2.4 tedaj sledi enakost
Delimo se z r! in dobimo formulo iz trditve.
2.4 Neurejeni izbori s ponavljanjem
Nazadnje se lotimo se razlicice naloge, kjer vrstni red izbranih kroglic ni pomemben, izzrebane kroglice pa vraCamo v boben. V tem primeru izida zreba zal ne moremo podati z mnozico izzrebanih kroglic, saj mnozica ne dopusca veckratnih pojavitev svojih elementov. Zato za opis zreba potrebujemo matematicno strukturo, ki ima podobne lastnosti kot mnočica, dopusca pa veckratno pripadnost kakega elementa. Taksnemu objektu pravimo mul-timnočica. Formalno je multimnozico najlazje opisati kot preslikavo, ki vsakemu potencialnemu elementu priredi njegovo kratnost v multimnozici. Pri tem za elemente, ki jih v multimnozici ni, recemo, da v njej nastopajo s kratnostjo 0.
Definicija 2.8 Multimnozica z elementi v mnozici N je poljubna preslikava
/: N ^ No.
Pri tem stevilu /(a), a G N, recemo kratnost elementa a v multimnozici /, vsoti
pa moc multimnozice / .
Neformalno pa lahko multimnozice podajamo tudi kot mnozice, pri cemer dopuscamo, da se nekateri elementi multimnozice pojavijo vec kot enkrat. Pri tem vrstni red elementov, tako kot pri mnozicah, ni pomemben. Na primer, multimnozico /: {a, b, c, d} ^ N0,
/(a) = 1, /(b) = 2, /(c) = 0, /(c) = 3,
lahko podamo tudi z nastevanjem elementov
/ = [b, c, c, a, c, b] = [c, b, c,b,a,c] = ... ali / = [a1, b2, c3].
Moc multimnozice / je 6.
Neurejene izbore s ponavljanjem lahko sedaj opisemo v jeziku multimno-
zic.
Definicija 2.9 Naj bo N mnozica moci n. Multimnozici moci r z elementi v mnozici N recemo neurejeni izbor elementov mnozice N dolzine r s ponavljanjem. Mnozico vseh taksnih multimnozic oznacimo s simbolom
K(N, r),
njihovo Stevilo pa s
K(n, r).
Trditev 2.10 Za poljubni nenegativni žtevili n in r velja
/n + r — 1\ /n + r — 1N
K(n,r) =	ti.
n — 1	r
Dokaz: Vzemimo n-elementno mnozico N = {a1,...,an}. Trditev dokazemo na strog matematicen nacin tako, da najdemo bijektivno preslikavo iz mnozice K(N, r) v mnozico K(Nn+r-1,n — 1).
Naj bo ^: N ^ No multimnozica moci r. Za k G {1,..., n — 1} defini-rajmo
bk = MaO + ... + Mafc) + k
in jih zdruzimo v mnozico BM = {b1, b2,..., bn-1}. Dokazimo najprej, da je Bm podmnozica mnozice Nn+r-1 in da premore n — 1 elementov. Ker je
bk+1 = bk + ju(ak+1) + 1	(*)
za vsak k > 1, je zaporedje stevil bk strogo narascajoce. Ker je b1 = ^(a1) +
1 > 1, so stevila bk pozitivna. Po drugi strani pa je
n
bn-1 = MaO + ... + Man-1) + n — 1 < ^ ^(ak) + n — 1 = r + n — 1.
k= 1
Zato je res BM element mnozice K(Nn+r-1,n — 1). Dokazimo zdaj, da je preslikava
$: K(N,r) ^K(Nn+r-1,n — 1),	= BM,
bijekcija. Surjektivnost dokazemo tako, da vzamemo poljubno (n — 1)-elementno podmnozico B C Nn+r-1, uredimo njene elemente bk po velikosti, b1 < b2 < ... < bn-1, in dolocimo stevila ^(ak) tako, da zadoscajo formuli (*). Dobimo:
^(a1) = b1 — 1, ^(ak) = bk — bk-1 — 1 za k > 2.
Za tako doloceno multimnozico ^ G K(N, r) ocitno velja BM = B. S tem je surjektivnost preslikave $ dokazana. Injektivnost sledi iz dejstva, da so stevila bk v formuli (*) natanko dolocajo vrednosti ^(ak).	I
2.5 Ponovno o igri loto
Na koncu poglavja se vrnimo k nasi zacetni nalogi o stevilu moznih zrebov sedmih kroglic. Pri vseh stirih razlicicah naloge prestevamo izbore elementov mnozice z n = 39 elementi dolzine r = 7.
Ce je vrstni red izvlecenih kroglic pomemben, kroglice pa vracamo v boben, stejemo urejene izbore s ponavljanjem. Teh je - v skladu s trditvijo 2.2 - natanko
397 = 137231006 679.
Ce je vrstni red izvlecenih kroglic pomemben, kroglic pa ne vracamo v boben, stejemo urejene izbore brez ponavljanja. Teh je - v skladu s trditvijo 2.4 - natanko
397 = 77 519 922 480.
Ce vrstni red izvlecenih kroglic ni pomemben, kroglice pa vracamo v boben, stejemo neurejene izbore s ponavljanjem. Teh je - v skladu s trditvijo 2.10 - natanko
'39 + 7 - 1\ /45n
,= 45 379 620.
77
Nazadnje si oglejmo se interpretacijo naloge, ki ustreza dejanskim pravilom igre loto, torej, ko vrstni red izvlecenih kroglic ni pomemben in kroglic ne vracamo v boben. Tedaj stejemo neurejene izbore brez ponavljanja, ki jih je - v skladu s trditvijo 2.7 - natanko
'39\ 397
„ ,	= 15 380 937.
7 J 7!
2.6 Permutacije mnoZic in multimnoZic
Ze v razdelku o urejenih izborih brez ponavljanja smo definirali pojem per-mutacije mnozice. Omenili smo, da si lahko permutacijo dane mnozice predstavimo kot linearno ureditev njenih elementov. Vcasih pa se pojavi potreba po linearnem urejanju elementov multimnozice. Na primer, ce zelimo presteti vse besede, ki jih lahko sestavimo s premetavanjem crk besede BANANA, moramo presteti vse linearne ureditve crk B, treh kopij crke A in dveh kopij crke N, pri cemer kopij posamezne crke med seboj ne locimo. Taksno linearno ureditev lahko strogo matematicno opisemo s pojmom per-mutacije multimnozice.
Definicija 2.11 Naj bo ^: A ^ No multimnožica moži n. Urejeni n-terici (x1,... ,xn), v kateri se vsak element a £ A pojavi natanko a)-krat, rečemo permutacija multimnozice
Trditev 2.12 Naj bo ^ multimnoZica moci n z elementi x1,..., Xk in krat-nostmi = n^ Tedaj je število permutacij multimnozice ^ enako
n	n!
n1,...,nfc/ n1! ••• nfc!
Dokaz: Za vsak i G {1,..., k} definirajmo mnozico Xi = {x^} x Nni ter mnozice Xi zdruzimo v mnozico X = Uk=1Xi. Na elemente mnozice X lahko pogledamo kot na elemente multimnozice pri cemer pojavitve istega elementa med seboj razlikujemo.
Iz permutacije mnozice X lahko dobimo permutacijo multimnozice ^ tako, da pri vsakem elementu mnozice X odmislimo njegovo drugo komponento.
Na primer, ce je ^ = {X1, x;], x^}, potem iz permutacije
((X2,3), (x1,1), (x2,1), (x2,2), (xs, 2), (xs, 1))
mnozice X dobimo permutacijo (x2, x1, x2, x2, x3, x3) multimnozice
Vsako permutacijo multimnozice ^ lahko na taksen nacin dobimo iz natanko n1! ■ ■ ■ n^! razlicnih permutacij mnozice X. Ker je permutacij mnozice X natanko n!, je permutacij mnozice ^ natanko n!/n1! ■ ■ ■ nk!.	I
opomba. Simbolu ( n ) = —r^—r recemo tudi multinomski simbol.
2.7 Binomski simboli in Pascalov trikotnik
Oglejmo si nekaj zanimivih lastnosti binomskih simbolov, ki smo jih vpeljali v razdelku 2.3. Zacnimo z izrekom, ki pojasni njihovo ime.
Trditev 2.13 V kolobarju polinomov Q[x,y] za vsako naravno stevilo n velja naslednja, tako imenovana binomska identiteta.
(x + y)n = jr (n)xn-ryr.
r=o Vr/
Dokaz: Trditev lahko dokazemo z indukcijo na stevilo n. Zanimivejsa pa je naslednja kombinatoricna utemeljitev identitete. Potenco (x + y)n najprej zapisimo kot produkt n faktorjev oblike x + y:
(x + y)(x + y) ••• (x + y).
Ko s pomočjo distributivnostnega zakona odpravimo vse oklepaje, dobimo vsoto produktov oblike a1a2 ... an, kjer posamičen faktor ai izberemo izmed nedoločenk x in y v i-tem oklepaju (x + y) zgornjega produkta:
(x + y)n =	a1a2 ... an.
(a1,...,an)e{x,y}n
Produkt a1a2 ... an je torej oblike xryn-r, pri čemer r pove, koliko od faktorjev ai je enakih x. Ker lahko r oklepajev, iz katerih za ai vzamemo nedoločenko x, izberemo na (n) načinov, se posamični člen xryn-r v razvoju
potence binoma (x+y)n pojavi natanko (n)-krat. S tem je trditev dokazana.
■
S pomočjo binomske identitete lahko izpeljemo naslednji zanimivi enakosti. Prva od enakosti je hkrati poslediča dejstva, da je stevilo vseh podmnozič n-elementne podmnoziče enako 2n.
Trditev 2.14
£ (n) = 2";
r=0 V 7
£ (-i)r (n) = o.
r=0
Dokaz: Prvo trditev dobimo, če v binomsko formulo vstavimo x = y = 1, drugo pa, če vstavimo x = 1 in y = -1.	I
Naslednja trditev pravi, daje binomski simbol (") neobčutljiv za zamenjavo r ^ n — r.
Trditev 2.15 Za poljubni števili n, r, 0 < r < n, velja enakost
nn n — r
Dokaz: Trditev lahko dokazemo z računskim rokohitrstvom takole: Najprej formulo za binomske koefičiente podamo v naslednji "neokrajsani" obliki,	( )
r J r! r!(n — r)! Nato pa v zgornji formuli za r vstavimo n — r, in dobimo naslednjo enakost:
n	n!	n!	n
n — rj (n — r)!(n — (n — r))! (n — r)!r!
n\ nr	n!
r
S tem je trditev dokazana.
Za nas pa je zanimivejši naslednji kombinatoricni dokaz. Naj bo N poljubna n-elementna podmnoZica. Definirajmo preslikavo, ki vsaki r-elementni podmnoZici A C N priredimo njen komplement C 7V". Ni se teZko prepričati, da je taksna preslikava bijekcija med mnoZico K(N, r,) vseh r-elementnih podmnoZic mnoZice N in mnoZico K(N", n — r) vseh (n — r)-elementnih podmnoZic mnoZice N. Ker je prvih , slednjih pa , je trditev s tem dokaZana.	I
Trditev 2.16 Za poljubni števili n, r G No, r < n, velja:
n +1\ /n\ / n r + 1/ Vr/ Vr + 1
Dokaz: Navedimo dva dokaZa te trditve. Prvi je povsem racunski in temelji na formuli iZ trditve 2.7. Racunajmo:
n\ + / n \ nr + nr+1 (r + 1)nr + nr+1
r) \r + 1/ r! (r +1)!	(r +1)!
(r + 1)nr + (n — r)nr (n + 1)nr n + 1r+1 /n + 1
(r + 1)!	(r + 1)! (r +1)! \r + 1,
Drugi dokaZ trditve pa je povsem kombinatoricen in uposteva le dejstvo, da je enako stevilu r-elementnih podmnoZic n-elementne mnoZice.
Naj bo N poljubna (n + 1)-elementna mnoZica. BreZ iZgube splosnosti lahko predpostavimo, da je N = {1,2,...,n,n + 1}. MnoZico (r + 1)-elementnih podmnoZic raZdelimo v dve skupini: V prvi naj bodo tiste podmnoZice, ki vsebujejo element n + 1, v drugi pa preostale. V drugi skupini so tako pristale ravne vse (r + 1)-elementne podmnoZice mnoZice N \ {n + 1} - teh je natanko (r+J.
Prestejmo se one iZ prve skupine - imenujmo jo R1. Vsaki podmnoZici A iZ R1 priredimo mnoZico A' = A\ {n +1}. Ker A po predpostavki vsebuje element n + 1, je A' r-elementna podmnoZica mnoZice N\ {n + 1}. Predpis A ^ A' tako podaja preslikavo med R1 in K(N\ {n +1}, r). Ni teZko videti, da je preslikava, podana s predpisom, A' ^ A' U {n + 1} inverZ preslikave A ^ A'. Zato je preslikava A ^ A' bijekcija, in mnoZici R1 ter N\ {n + 1} sta enako mocni. Ker slednja steje elementov, je to hkrati tudi moc mnoZice R1. V obeh skupinah skupaj je torej + (r+J podmnoZic. Po
drugi strani pa obe skupini podmnozič skupaj tvorita mnozičo vseh (r + 1)-elementnih podmnozič (n + 1)-elementne mnoziče N, za katere pa vemo, da jih je ("+!). Enakost je s tem dokazana.	I
Formula iz trditve 2.16 nosi ime Pascalova identiteta. Omogoča nam računati binomske koefičiente rekurzivno s pomočjo sheme, ki ji rečemo Pascalov trikotnik. Shema ima obliko enakokrakega trikotnika, ki ga gradimo iz "gornjega" oglisča "navzdol" tako, da na skrajni mesti vsake vrstiče najprej vpisemo stevilo 1, "notranjost" vrstiče pa zapolnimo tako, da v vsako prazno mesto vpisemo vsoto stevili, ki stojita levo in desno diagonalno nad praznim mestom. Pri tem prvo vrstičo, v kateri stoji le ena stevilka, namreč
1, imenujemo 0-to vrstičo, naslednje pa prva, druga, tretja itd. Podobno skrajno levemu mestu v vsaki vrstiči rečemo 0-to mesto, naslednja pa prvo, drugo, tretje itd. Iz Pasčalove identitete tedaj sledi, da se na r-tem mestu n-te vrstiče nahaja s tevilo (").
3 NaCelo vkljuCitev in izključitev
Nacelo vsote nam pove, da je moc unije paroma disjunktnih mnozic enaka vsoti njihovih moci. Kaj pa, ce mnozice niso paroma disjunktne? Tedaj je moc unije seveda strogo manjsa od vsote moci posameznih mnozic, saj pri sestevanju moci mnozic elemente, ki nastopajo v presekih dveh ali vec mnozic stejemo vec kot enkrat. Nacelo vkljucitev in izkljucitev podaja zvezo med mocjo unije ter mocmi posameznih mnozic ter njihovih presekov.
3.1	Unija dveh mnoZic
Pricnimo s preprostim zgledom unije dveh mnozic A in B. Ce prestejemo najprej elemente mnozice A, nato pa se elemente mnozice B, smo presteli vsak element unije A U B, pri cemer smo elemente v preseku A n B presteli dvakrat. Zato velja dobro znana formula:
|A U B| = |A| + |B| - |A n B|.
3.2	Unija poljubno mnogo mnoZic
Ce je mnozic vec, moc njihove unije racunamo s pomocjo naslednje trditve. Trditev 3.1 Naj bodo A1,..., An poljubne mnozice. Za k G {1,..., n} naj
Sk = r |aej Ai | je(Nn)
označuje vsoto moci presekov vseh k-teric mnozic Ai. Tedaj je
n
iun=1 Ai | = j(-1)k-1Sk.	(*)
k=1
Dokaz: Naj bo x element unije un=1Ai. Tedaj je x vsebvan v vsaj eni od mnozic Ai. Pa denimo, da je x vsebovan v natanko m mnozicah Ai. Tedaj se za vsak k G {1,... ,n} element x pojavi v natanko (') presekih niejAi za katere je |J| = k. To pa pomeni, da x za vsak k prispeva k desni strani enakosti (*) natanko (—1)k-1('), skupaj torej
n	/ \	'	/ \
r (-Dk-M m)=1+r (-Dk"M m)=!•
k=1	k	k=o	k
kjer smo pri zadnji enakosti uporabili trditev 2.16. S tem je trditev dokazana.
Zgled. Naj bo Pn množica vseh permutacij množice Nn. Elementu i G Nn rečemo fiksna točka permutačije n = (a1,...,an) G Pn, če velja ai = i. Permutaciji brez fiksnih točke rečemo tudi deranzma. Koliko deranžmajev v Pn obstaja?
Rešitev: Za i = 1,..., n naj bo Ai mnoziča vseh permutačij v Pn, za katere je i fiksna točka. Unija Ui=1 Ai je natanko mnoziča vseh permutačij, ki niso deranzmaji. Nas torej zanima stevilo
dn = |Pn|-|un=1 Ai| = n! - | un=1 Ai|.
Vzemimo poljubno indeksno mnozičo J G (Nn) in premislimo, koliko elementov premore presek niejAi. Elementi tega preseka so natanko tiste permutačije (a1,... ,an), za katere je ai = i za vsak i G J, na preostalih mestih Nn \ J pa se nahaja poljubna permutačija mnoziče Nn \ J. Zato je moč preseka niejAi enaka (n — k)! in
Sk = E |niJ Ail = (n) (n — k)! = n.
Jeft)	!
Iz načela vključitev in izključitev sledi:
nn
| un=1 Ai| = E(—1)k-1Sk = n! E(—1)k-1 . k=1 k=1 !
Opazimo, da zaporedje n zelo hitro konvergira k e-1. Verjetnostna inter-pretačija tega dejstva je, da je verjetnost, da naključno izbrana permutačija nima fiksnih točk, priblizno enaka e ^ 0,37.	■
Zgornjo nalogo o deranzmajih lahko srečamo v najrazličnej sih preoblekah, med katere sodi tudi spodnja.
Zgled. V krcmo na Divjem zahodu vstopi druscina n revolverasev. Ker je v salonu prepovedano nositi orožje, pri vratih vsak odda svoj revolver. Zaradi objektivnih okoliscin so v nekem trenutku krcmo prisiljeni na hitro zapustiti, pri cemer vsak na slepo zagrabi enega od n oddanih revolverjev. Kolikšna je verjetnost, da nihce od revolverasev ni zagrabil svojega revolverja.
Rešitev: Ce revolverase označimo z naravnimi stevili med 1 in n, lahko situačijo po odhodu iz salona opi semo s permutačijo (a1,...,an) mnoziče revolvera sev, kjer je ai zaporedna stevilka lastnika revolverja, ki ga je ob odhodu zagrabil i-ti revolveras. Vseh moznih situačij po odhodu je torej n! in vse so enako verjetne. Situačije, kjer nihče od revolverasev ne zagrabi
svojega revolverja, pa ustrezajo natanko deranzmajem. Zato je verjetnost tega dogodka enaka
dn =	i)fc1
n! =	) k!.
k=0
4	Razbitja množic in razčlenitve Števil
V tem poglavju bomo prestevali raZbitja dane n-elementne mnoZice na k nepraZnih podmnoZic. Pojasnimo najprej natancno, kaj s tem mislimo.
Definicija 4.1 RaZbitje mnoZice A je družina R = {A1,..., Ak} nepraznih, paroma disjunktnih podmnoZic množice A, katerih unija je enaka množici A. Množicam Aj reCemo tudi deli raZbitja.
Na primer, ce je A = {a, b, c, d}, je R = {{a}, {b, c, d}} raZbitje mnoZice A na 2 nepraZni mnoZici. Poleg raZbitja R, mnoZica A premore se sest drugih raZbitij na 2 nepraZni mnoZici. Najprej se tri, kjer je eden od delov moci 1 (in drugi moci 3), nato pa s e tri tak s na, kjer je sta oba dela raZbitja moci 2.
Poleg obicajnih raZbitij mnoZice, pa bomo obravnavali tudi tako imenovana urejena razbitja, kjer elemente vsakega dela raZbitja uredimo. Kaj natanko s tem mislimo, bomo pojasnili v nadaljevanju.
4.1 Stirlingova stevila druge vrste
5	tevilu vseh raZbitij n-elementne mnoZice A na k nepraZnih podmnoZic recemo Stirlingovo .število druge vrste in ga oZnacimo z S(n, k). MnoZico teh razbitij oznacimo z S (A, k). Ocitno velja naslednje:
S (n, k) = 0 za k > n, S(n, n) = 1 in S (n, 1) = 1.	(*)
Dodatno definiramo se S(n, 0) = 0 za vsak n > 1 in S(0,0) = 1.
Ostala stevila S(n, k) pa najenostavneje racunamo s pomocjo naslednje rekurzivne formule.
Trditev 4.2 Za vsak par n, k G N, 1 < k < n, velja
S (n, k) = S (n — 1, k — 1) + kS(n — 1, k).
Dokaz: Naj bo N = {x1,..., xn} poljubna n-elementna mnoZica, R mnoZica vseh razbitij mnoZice N na k nepraznih podmnoZic, R0 mnoZica tistih razbitij iz R, v katerih nastopa podmnoZica {xn} in R1 = R \ R0.
Vzemimo poljubno razbitje R = {A1,...,Ak} G R. Mislimo si, da element iz mnoZice N izreZemo. Tedaj razbitje R preide v razbitje R' = {A1 \ {xra},..., Afc \ {xra}} mnoZice N\ {x„}.
Ce razbitje R sodi v skupino R0, tedaj je ena od mnoZic razbitja R' praZna in mislimo si lahko, da jo iZ R' odstanimo. Tako dobimo raZbitje
(n — 1)-elementne množice N\{xn} na k — 1 nepraznih podmnožic. Obratno, vsako razbitje T = {A^,..., A'k_ 1} množice N \ {xn} na k — 1 nepraznih podmnožic lahko z vključitvijo množice {xn} dopolnimo do razbitja R = {{xn},Al ...,Ak_ 1} množice N. Ni težko videti, da je R edino razbitje iz R0, za katero je R' = T. S tem smo dokazali, da je preslikava R ^ R' bijekcija med množicama R0 in množico S (N \ {xn}, k — 1) nepraznih podmnožic. Po nacelu enakosti sledi |R0| = S(n — 1,k — 1).
Ce pa razbitje R sodi v skupino R1, tedaj nobena od množic razbitja R' ni prazna, kar pomeni, da je R' razbitje mnozcie N \ {xn} na k nepraznih podmnožic. Ce vzamemo poljubno razbitje T = {A^^,..., Ak} množice N \ {xn} na k nepraznih podmnožic, lahko z vkljucitvijo elementa {xn} v katero koli od k množic Ai dobimo razbitje R iz skupine R1, za katerega je R' = T. Tako dobljena razbitja R so hkrati edina, za katera je R' = T, kar pomeni, daje vseh razbitij iz skupine R1 natanko k-krat toliko, kot je razbitij (n — 1)-elementne množice N\ {xn} na k-nepraznih podmnožic, torej kS(n — 1, k).
Trditev sedaj z lahkoto sledi, saj je |R| = |R0| + |R11 = S(n — 1,k — 1) + kS (n — 1,k).	■
Rekurzivna formula nam omogoca, da Stirlingova stevila 2. vrste racu-namo podobno kot binomske koeficiente. Sestavimo tabelo, v kateri na preseciscu n-te vrstice in k-tega stolpca stoji stevilo S(n, k):
n|k	0	1	2	3	4	5	6	7
0	1	0	0	0	0	0	0	0
1	0	1	0	0	0	0	0	0
2	0	1	1	0	0	0	0	0
3	0	1	3	1	0	0	0	0
4	0	1	7	6	1	0	0	0
5	0	1	15	25	10	1	0	0
6	0	1	31	90	65	15	1	0
7	0	1	63	301	350	140	21	1
Iz zacetnih pogojev sledi, da so nad glavno diagonalo same nicle, po diagonali same enke, v prvem stolpcu pa, razen pri prvem elementu, zopet same nicle. Stevilo S (n, k) v tabeli dobimo tako, da sestejemo stevilo, ki stoji diagonalno levo nad njim in k-kratnik stevila neposredno nad njim. Stevilo 65, ki leži v vrstici 6 in stolpcu 4, smo torej dobili tako, da smo sesteli 25 (levo zgoraj) in 4 ■ 10 (smo v stolpcu 4, nad iskanim stevilom pa stoji 10).
Stirlingova stevila 2. vrste imajo zanimivo interpretacijo tudi pri problemih prestevanja funkcij med dvema koncnima množicama.
Trditev 4.3 Naj bosta N in K poljubni koncni mnozici moci n in k. Tedaj je stevilo vseh surjektivnih preslikav iz mnozice N v mnozico K enako
k!S (n, k).
Dokaz: Naj bodo b1,..., bk elementi mnozice K in f: N ^ K poljubna surjektivna preslikava. Za vsak i G {1,..., k} definirajmo mnozico
Ni = f-1(bi) = {x G N : f(x) = bi}.
Tedaj druzina {N1,..., Nk} tvori razbitje mnozice N na k nepraznih delov. Na ta nacin smo definirali preslikavo $ iz mnozice vseh surjektivnih funkcij iz N v K ter mnozico S (N, k).
Pri tem opazimo, da za razbitje R = {N1,..., Nk} G S(N, k) in surjek-tivno preslikavo f: N ^ K velja $(f) = R, ce in samo ce je f definirana s predpisom
f (x) = bi ^^ x G Nn(i),
za neko permutacijo n mnozice indeksov {1,..., k}. Od tod sledi, da se v vsako razbitje iz S(N, k) preslika natanko k! razlicnih surjektivnih preslikav iz N v K. Zato je taksnih surjektivnih preslikavo natanko k! | S (N, k)| = k!S(n, k).	■
S pomocjo trditve 4.3, rekurzivne formule in nacela vkljucitev in izkljucitev lahko dokazemo naslednjo zanimivo formulo.
Trditev 4.4 Za poljubni naravni stevili n, k, k < n, velja
S(n,k) = 1 E (k)(-Dk-iin i=1 ^ '
Dokaz: Naj bosta N in K, |N| = n, |K| = k, poljubni mnozici in naj A oznacuje mnozico vseh preslikav iz N v K, ki niso surjektivne. Ker je vseh preslikav iz N v K natanko kn, je moc mnozice A enaka kn — k!S(n, k).
Zdaj pa prestejmo elemente mnozice A se na drug nacin. Naj bodo b1,..., bk elementi mnozice K in za vsak i G {1,..., k} naj Ai predstavlja mnozico vseh tistih funkcij iz N v K, ki elementa bi nimajo v svoji sliki. Tedaj je mnozica A ocitno unija mnozic Ai.
Vzemimo poljubno i-elementno podmnozico J = {bj,..., bJi} mnozice {1,..., k}. Tedaj presek njejAj vsebuje natanko vse funkcije iz mnozice N v mnozico K \ {bj,..., bJi} in zato premore natanko (k — i)n elementov.
Vsota Si moči presekov njejAj po vseh i-elementnih podmnozičah J mnoziče {1,..., k} zato znasa
0 >—■>"
Trditev sedaj sledi neposredno iz načela vključitev in izključitev.	I
4.2 Lahova števila
Lahovo stevilo L(n, k) je definirano kot stevilo linearno urejenih razbitij n-elementne mnoziče na k nepraznih podmnozič. Neformalno lahko linearno urejeno razbitje mnoziče A = {a1,..., an} opisemo kot običajno razbitje, pri čemer vsako mnozičo razbitja linearno uredimo. Dve razbitji na iste mnoziče se pri tem razlikujeta, če se razlikujeta vrstna reda elementov v kateri od mnozič razbitja.
Razliko med običajnimi in linearno urejenimi razbitji si oglejmo na naslednjem primeru. Naj bo A = {a, b, c, d} in poisčimo vsa (običajna) razbitja na mnoziče A na dve podmnoziči. Le-ta so
{{a, b}, {c, d}}, {{a, c}, {b,d}}, {{a, d}, {b,c}},
{{a}, {b, c, d}}, {{b}, {a, c, d}}, {{c}, {a,b,d}}, {{d}, {a,b,c}}. Razbitje {{a, b}, {c, d}} porodi stiri različna linearno urejena razbitja:
{(a, b), (c, d)}, {(b, a), (c,d)}, {(a,b), (d,c)}, {(b,a), (d,c)}.
Podobno velja za ostala razbitja na dve enako močni mnoziči. Po drugi strani pa razbitje {{a}, {b, c, d}} porodi 3! = 6 različnih linearno urejenih razbitij - za vsako linearno ureditev elementov {b, c, d} po eno. Zato je
L(4, 2) = 4 ■ 3 + 6 ■ 4 = 36.
Za skrajne vrednosti Lahovih stevil očitno velja naslednje:
L(n, k) = 0 za k > n , L(n, n) = 1 in L(n, 1) = n!.
Dodatno definiramo s e L(n, 0) = 0 za vsak n > 1 in L(0,0) = 1.
Podobno kot pri Stirlingovih stevilih 2. vrste lahko tudi za Lahova stevila izpeljemo rekurzivno zvezo. Izpeljava se razlikuje zgolj v tem, da tu pri stetju razbitij iz skupine R1 iz danega razbitja T = {A1,..., A'k} mnoziče N \ {xn} lahko najdemo n — 1 + k razbitij R iz skupine R1, za katera je
R' = T; izbrisani element lahko namreč vrinemo v katero koli množico Ai na eno od |Ai| + 1 razpoložljivih mest (za vse elemente množice Ai ali pa pred kakega od |Ai| elementov množice A). Element lahko torej vrinemo v razbitje na (|Ai| + 1) + (|A2| + 1) + ... + (|Ak| + 1) načinov, kar znese n — 1 + k. Od tod sledi naslednja trditev.
Trditev 4.5 Za 1 < k < n velja
L(n, k) = L(n — 1, k — 1) + (n + k — 1)L(n — 1, k).
Z indukcijo na stevilo n in z uporabo rekurzivne formule iz trditve 4.5 lahko izpeljemo tudi eksplicitno formulo, ki Lahova stevila izrazi s pomocjo binomskih simbolov.
Trditev 4.6 Za 1 < k < n velja
(n — 1\ n! /n\ (n — 1)! L(n,k) = '	1 11
k — 1) k! \k) (k — 1)!'
Podobno kot pri binomskih simbolih in Stirlingovih s tevilih 2. vrste, lahko tudi Lahova stevila racunamo s pomocjo sheme, ki izhaja iz rekurzivne zveze. V spodnji tabeli na preseciscu n-te vrstice in k-tega stolpca stoji stevilo L(n, k), ki ga dobimo tako, da sestejemo stevilo, ki stoji diagonalno levo nad njim in (n + k — 1)-kratnik stevila neposredno nad njim. Stevilo 240, ki lezi v vrstici 5 in stolpcu 2, smo torej dobili tako, da smo se steli 24 (levo zgoraj) in 6 ■ 36.
n|k	0	1	2	3	4	5	6	7
0	1	0	0	0	0	0	0	0
1	0	1	0	0	0	0	0	0
2	0	2	1	0	0	0	0	0
3	0	6	6	1	0	0	0	0
4	0	24	36	12	1	0	0	0
5	0	120	240	120	20	1	0	0
6	0	720	1800	1200	300	30	1	0
7	0	5040	15120	12600	4200	630	42	1
Poleg obicajnih Lahovih stevila se v literaturi pojavljajo tudi predznačena Lahova .števila, definirana s formulo
L'(n,k) = (—1)nL(n, k).
4.3 Stirlingova stevila prve vrste
Stirlingovo število prve vrste s(n,k) stejeje razbitja n-elementne mnozice na k nepraznih ciklično urejenih mnozic. Pri tem pojem "ciklicno urejena mnozica" pomeni mnozico, denimo A = {a, b, c, d}, skupaj s ciklicnim vrstnim redom elementov, denimo
[a, b, c, d] = [b, c, d, a] = [c, d, a, b] = [d, a, b, c].
Hiter premislek pokaze, da lahko vsako m-elementno mnozico ciklicno uredimo na (m — 1)! nacinov, saj si lahko ciklicno ureditev predstavljamo kot linearno ureditev mnozice, pri cemer m linearnih ureditev, ki se razlikujejo zgolj za ciklicni pomik, stejemo kot isto ciklicno ureditev. Ker je linearnih ureditev m-elemente mnozice m!, je zato ciklicnih ureditev m = (m — 1)!.
Stirlingova stevila za mejne pare stevil n in k zadoscajo enakostim
s(n, k) = 0 za k > n , s(n,n) = 1 in s(n, 1) = (n — 1)!.
Dodatno definiramo se s(n, 0) = 0 za vsak n > 1 in s(0,0) = 1.
Na zelo podoben nacin kot pri Stirlingovih stevilih druge vrste in Lahovih stevilih lahko tudi tu izpeljemo naslednjo rekurzivno formulo.
s(n, k) = s(n — 1, k — 1) + (n — 1)s(n — 1, k).
V tabeli Stirlingovih stevil 1. vrste, v kateri na preseciscu n-te vrstice in k-tega stolpca stoji stevilo s(n, k), lezijo nad glavno diagonalo same nicle, po diagonali same enke, v prvem stolpcu pa, razen prvega elementa, spet same nicle. V skladu z rekurzivno formulo izracunamo stevilo s(n, k) v tabeli tako, da se stejemo stevilo, ki stoji levo zgoraj nad njim, in (n — 1)-kratnik stevila, ki stoji neposredno nad njim. Na primer, na preseci scu vrstice 5 in stolpca 3 dobimo vsoto s tevila 11 (levo zgoraj) in s tevila (5 — 1) ■ 6 = 24, torej 35.
n|k	0	1	2	3	4	5	6	7
0	1	0	0	0	0	0	0	0
1	0	1	0	0	0	0	0	0
2	0	1	1	0	0	0	0	0
3	0	2	3	1	0	0	0	0
4	0	6	11	6	1	0	0	0
5	0	24	50	35	10	1	0	0
6	0	120	274	225	85	15	1	0
7	0	720	1764	1624	735	175	21	1
V literaturi srecamo tudi predznačena Stirlingova .števila prve vrste, ki so definirana s formulo
s'(n,k) = (—1)n-ks(n, k).
4.4 Število razčelnitev naravnega števila
Zaporedju (neničelnih) naravnih števil m1 < m2 < ... < mk, katerih vsota je enaka n, rečemo razčlenitev naravnega .števila n na k členov. Stevilo vseh tak š nih razčlenitev označimo s p^(n). Očitno je
pk(n) = 0 za k > n. Dodatno definiramo p0(0) = 1 in p0(n) = 0 za n > 0. Trditev 4.7 Za vsak par naravnih števil n, k velja
pfc(n) = pfc-i(n - 1) + pfc(n - k).
Dokaz: zdruzimo tiste razčlenitve (m1,..., mk), za katera je m1 = 1 v mnozičo R0, tiste, za katera pa je m1 > 1, pa v mnozičo R1. C e razčlenitvi iz mnoziče R0 odvzamemo prvi element m1 = 1, dobimo razčlenitev stevila n — 1 na k — 1 sumandov. Obratno, če razčlenitvi stevila n — 1 na k — 1 sumandov dodamo na začetek eničo, dobimo razčlenitev iz R0. Zato je |Ro| = pfc-1(n — 1).
Razčlenitev (m1,... ,mk) G R1 lahko spremenimo v razčlenitev stevila n — k na k sumandov, če vsak m^ zmanj samo za 1. Ker vsako razčlenitev stevila n — k na k sumandov dobimo na tak sen način natanko enkrat, je IR1I = pfc (n — k). Od tod dobimo p^ (n) = |Ro| + |R1 = pfc-1(n — 1) + pfc (n — k).	■
Računanje stevil pk(n) si olaj samo, če sestavimo tabelo, v kateri na presečisču n-te vrstiče in k-tega stolpča stoji stevilo pk(n). Začetni pogoji in rekurzivna formula pravijo, da so nad glavno diagonalo same ničle, po diagonali same enke, v prvem stolpču pa, razen prvega elementa, spet same ničle. Stevilo pk(n) v tabeli dobimo tako, da sestejemo stevilo, ki stoji levo zgoraj nad njim, in stevilo, ki stoji k vrstič nad iskanim stevilom. Na primer, na presečisču vrstiče 7 in stolpča 3 dobimo vsoto stevila 3 (levo zgoraj) in stevila 1 (tri vrstiče visje).
n|k	0	1	2	3	4	5	6	7
0	1	0	0	0	0	0	0	0
1	0	1	0	0	0	0	0	0
2	0	1	1	0	0	0	0	0
3	0	1	1	1	0	0	0	0
4	0	1	2	1	1	0	0	0
5	0	1	2	2	1	1	0	0
6	0	1	3	3	2	1	1	0
7	0	1	3	4	3	2	1	1
4.5 Prostori polinomov in Stirlingova ter Lahova stevila
Za konec razdelka predstavimo presenetljivo interpretacijo Stirlingovih in Lahovih stevil v teoriji polinomskih kolobarjev. Naj Q[x] oznacuje kolobar polinomov z racionalnimi koeficienti v nedolocenki x. Na kolobar Q[x] lahko pogledamo tudi kot na neskoncno razsezen vektorski prostor nad obsegom Q. Poleg standardne baze
S — {1, x, x , x , . . .}
prostora Q[x] definirajmo s e bazi
Sp = {1,x,x2, x3,...} = {1,x,x(x — 1),x(x — 1)(x — 2),...}, Sn = {1, x, x2, x3,...} = {1,x,x(x + 1),x(x + 1)(x + 2),...}.
Ker so vse tri zgoraj na stete mnozice baze prostora Q[x], lahko vsak polinom vsake od njih zapisemo kot linearno kombinatocijo polinomov iz vsake druge od njih. Koeficienti taksnih razvojev so tesno povezani s Stirlingovimi ter Lahovimi stevili.
Dokazali bomo le trditev, ki podaja razvoj standardnih baznih polo-nomov iz S po polinomih iz Sp.
Trditev 4.8 Naj bo n poljubno nenegativno celo število. Tedaj v kolobarju polinomov Q[x] velja naslednja enakost
^ S (n, k)xk
fc=0
Dokaz: Trditev lahko dokazemo s pomocjo indukcije na naravno stevilo n in rekurzivne formule za S (n, k) povsem racunsko. Mi pa bomo raje navedli kombinatoricni dokaz.
Naj bo m poljubno naravno stevilo in A = {a1,...,am} poljubna m-elementna mnozica. Kot vemo, je moc mnozice An vseh urejenih n-teric elementov iz A enaka mn. Pa pre s tejmo s tevilo elementov mnozice An s e na drug nacin.
Za poljuben element (x1,..., xn) G An definirajmo ekvivalencno relacijo ~ na mnozici Nn = {1, 2,..., n} s pravilom: i ~ j, ce in samo ce xi = . Ekvivalencni razredi te relacije tvorijo razbitje mnozice Nn na nekaj (vsaj eno in ne vec kot n) nepraznih podmnozic. Pa naj , k G {1, 2,...,n}, predstavlja mnozico vseh tistih elementov iz An, ki na tak nacin porodijo razbitje z natanko k deli.
xn
Dokazati zelimo, da je moc mnozice Xk enaka S (n, k)mk. To storimo tako, da najdemo bijekcijo med Xk in mnozico S (Nn,k) x V (A, k). Ena od taksnih bijekcij je na primer preslikava, ki vsaki m-terici iz Xk priredi par (R, (y1,...,yk)), kjer je R razbitje mnozice Nn porojeno na zgoraj opisani nacin z elementi mnozice Xk, (y1,... ,yk) pa k-terica, ki jo dobimo iz m-terice (x1,..., xm), ce pregledujoc z leve proti desni odstranjujemo vse ponovitve elementov, ki smo jih srecali ze prej.
Ker je An disjunktna unija mnozic Xk za k = 1,..., n, od tod sledi
nn
mn = £ |Xk | = £ S (m, k)mk. k=1 k=1
Ker je S(m, 0) = 1 za m > 1, lahko k vsoti na desni dodamo se clen s k = 0.
Tako smo dokazali, da se polinoma na levi in desni strani enakosti iz trditve ujemata pri neskoncno mnogo vrednostih spremenljivke x. Ker pa je vsak polinom iz Q[x] stopnje n enolicno dolocen ze z n + 1 vrednosti v n + 1 tockah, to pomeni, da sta polinoma iz trditve resnicno enaka.	I
Zgornjo trditev lahko pogojno razumemo tako: Prehodna matrika med bazama S in Sp je ravno matrika Stirlingovih stevil.
Podobne formule, v katerih nastopajo Stirlingova s tevila 1. vrste in La-hova stevila lahko izpeljemo tudi za prehode med preostalimi urejenimi pari baz S, Sp in Sn.
5 Porazdelitve, barvanja in preslikave
Poleg nalog o izborih se v osnovni kombinatoriki pojavljajo tudi naloge o porazdelitvah objektov v skupine. Tipična naloga o porazdelitvah je naslednja:
Kokoši šo znesle n jajčk. Na koliko načinov lahko jajčka porazdelimo v k škatel?
Podobno kot pri izborih lahko tudi tu nalogo razumemo na več različnih načinov. Vprasamo se namreč lahko, ali med seboj razlikujemo jajčka in ali razlikujemo med različnimi skatlami. Tako dobimo stiri različiče osnovne naloge.
Poleg osnovne naloge nas bosta v vsaki od stirih različič zanimali tudi nekoliko spremenjeni nalogi, pri katerih bomo steli le tiste porazdelitve, pri katerih so vse skatle zasedene, in tiste porazdelitve, pri katerih je v vsaki s katli največ eno jajče. Število različič se s tem pomnozi s tri, tako da dobimo 12 različnih tipov nalog o porazdelitvah. Tem dvanajstim nalogam včasih slikovito (in nekoliko mistično) rečemo tudi dvanajstera pot (angl. twelfold way).
Naloge o porazdelitvah imajo tudi nekoliko bolj "barvito" preobleko. C e si mislimo, da je vsaka skatla napolnjena s svojo barvo za barvanje jajčk, si razporejanje jajčk lahko predstavljamo kot barvanje. Namesto o stevilu razporeditev v k s katel se tako lahko sprasujemo o stevilu različnih barvanj jajčk s k barvami.
Nazadnje si oglejmo se, kako nalogo o porazdelitvi jajčk oblikovati v strogem matematičnem jeziku. Oglejmo si najprej različičo naloge, kjer razlikujemo tako med jajčki kot med s katlami (oz. barvami, če nam je interpretačija z barvami ljub sa). V tem primeru lahko jajčka o stevilčimo (navadno s stevili med 1 in n), skatle (barve) pa označimo s simboli c1,... ,ck. Porazdelitev jajčk po skatlah lahko sedaj predstavimo s preslikavo iz mnoziče jajčk v mnozičo s katel, ki vsakemu jajčku priredi tisto s katlo, v katero ga razporedimo. C e pri porazdelitvi (barvanju) zahtevamo, da je vsaka skatla zasedena z vsaj enim jajčkom (oz. vsaka barva uporabljena), pre stevamo surjektivne preslikave. C e pa zahtevamo, daje v vsaki s katli največ eno jajče (oz. nobeni dve jajči nista iste barve), prestevamo injektivne preslikave.
Kako matematično obravnavati naloge, kjer skatel ali jajčk med seboj ne razlikujemo, bomo videli v nadaljevanju.
5.1	Preslikave
V tem razdelku nas bo zanimalo, koliko funkcij iz n-elementne mnozice N v k-elementno mnozico K obstaja. V nadaljevanju bomo elemente mnozice N oznacevali z a1,..., an, elemente mnozice K pa s c1,..., .
Naj KN oznacuje mnozico vseh preslikav iz N v K, (KN)i mnozico vseh injektivnih preslikav in (KN)s mnozico vseh surjektivnih preslikav iz N v K.
Vsako preslikavo f G KN lahko enolicno predstavimo z n-terico
(f(a!),...,f(an)) G Kn
njenih slik. V tem smislu smemo na preslikave iz N v K gledati kot na urejene izbore elementov mnozice K dolzine n. Pri tem injektivnim preslikavam utrezajo izbori brez ponavljanja. Od tod sledita prvi dve formuli spodnje trditve. Formulo o stevilu surjektivnih preslikav pa smo dokazali ze v razdelku o Stirlingovih stevilih 2. vrste.
Trditev 5.1 Naj bo N poljubna n-elementna množica in K poljubna k-elementna množica. Tedaj velja
|KN| = kn, |(KN)i| = kn, |(KN)s| = k!S(n, k).
5.2	Ekvivalenčni razredi preslikav - dvanajstera pot
S pomocjo permutacij bomo v tem razdelku na mnozici preslikav iz mnozice N v mnozico K uvedli tri ekvivalencne relacije. V definiciji spodaj smo mnozico vseh permutacij mnozice A (gledanih kot bijektivne preslikave iz A v A) oznacili s simbolom Sym(A).
Definicija 5.2 Naj bosta N in K poljubni neprazni množici in f, g G KN poljubni preslikavi. Tedaj pišemo
f g ^ 3A G Sym(K) : g = A o f; f g ^ 3p G Sym(N) : g = f o p; f	g ^ 3A G Sym(K), p G Sym(N): g = A o f o p.
Vsaka od teh treh ekvivalencnih relacij razbije mnozico NK na ekvi-valencne razrede. Ni tezko videti, da ekvivalencni razred kake surjektivne preslikave vsebuje le surjektivne preslikave, ekvivalencni razred injektivne preslikave pa le injektivne preslikave. Zato tudi mnozici (NK)s in (NK)i razpadeta na ekvivalence razrede glede na te tri ekvivalencne relacije. Osrednje vprasanje tega razdelka je, koliko je teh ekvivalencnih razredov. Preden odgovorimo na to vpras anje, pa si oglejmo zgled.
ekvivalenčni razredi preslikav - dvanajstera pot
29
Zgled. Naj bo N = {1,..., 5}, K = {01,02,03} in f: N ^ K, f (1) = f (2) = 01, f (3) = f (4) = 02, f (5) = 03.
S katerimi funkcijami je f v relaci (oz. in ~n,k)■
Rešitev: Preslikava f je v relaciji z natanko tistimi preslikavami, pri katerih se elementa 01 in 02 pojavita med slikami dvakrat, element 03 pa enkrat.
Nadalje, preslikava f je v relaciji s tistimi preslikavami g, za katere
je
g(1) = g(2),g(3)= g(4),
elementi g(1),g(3) in g(5) pa so paroma razlicni.
Nazadnje, preslikava f je v relaciji ~N,K z vsemi tistimi funkcijami, pri katerih se dva izmed treh elementov {01,02,03} pojavita med slikami dvakrat, tretji pa enkrat.	■
Trditev 5.3 (Dvanajstera pot) Naj bo N poljubna n-elementna množica in K poljubna k-elementna množica. Tedaj je žtevilo ekvivalenžnih razredov, na ketere razpadejo mnoZice KN, (KN)i in (KN)s pri relacijah =, , in ~N,K enako Številom v spodnji tebeli.
relacija	K N	(K N )i	(K N )s
=	kn	kn	k!S(n, k)
	fn+k—1\	(k\	
	l ra )	u	\n-kJ
	ek=1 s (n,i)	1, za k > n, 0 sicer	S (n, k)
~N,K	Ek=1 Pi(n)	1, za k > n, 0 sicer	Pk(n)
Dokaz: Naj bo N = {a1,..., an} in K = {01,..., 0k}. Pravilnost prve vrstice (kjer stejemo kar preslikave in N v K, saj vsak ekvivalencni razred glede na relacijo enakosti vsebuje natanko en element) sledi iz trditve 5.1.
Oglejmo si sedaj relacijo . Množico ekvivalencnih razredov množice KN oznacimo s [KN]n. Vzemimo preslikavo f: N ^ K in ji priredimo multimnozico
V = [f (a1 ),...,f (an
moci n z elementi iz K. Multimnozica, ki pripada ekvivalentni preslikavi g = f 0 P, P e Sym(N), je enaka V = [f (p(a1)),..., f (p(an))]. Ker vrstni
red pri navajanju elementov multimnozice ni pomemben, je ^ = Zato lahko definiramo preslikavo
p: [KN ]n ^ K(K, n), p([/j) = [/ (a1),..., / (on)].
Bijektivnost preslikave p dokazemo tako, da ji poi scemo inverzno preslikavo ■0, ki multimnozico [b1,..., 6nj moci n z elementi iz K preslika v ekvivalencni razred preslikave /: N ^ K, /(aj) = za i = 1,..., n. Bralcu prepu s camo, da preveri, da sta p in 0 vzajemno inverzni preslikavi. S tem smo dokazali:
|[KN]n| = |K(K,n)| = (k + n - 1
Preslikava /: N ^ K je injektivna, ce in samo ce je kratnost vsakega elementa multimnozice p([/j) enaka 1, se pravi, natanko tedaj, ko je p([/j) v resnici podmnozica mnozice K moci n. Zato je ekvivalencnih razredov injektivnih preslikav natanko toliko kot n-elementnih podmnozic mnozice K.
|Kk n >.]Ni=i( c
Stevilo ekvivalencnih razredov surjektivnih preslikav dolocimo tako, da multimnozici ^: K ^ No, ki pripada preslikavi / G (KN)s, priredimo multimnozico n': K ^ N0, ^'(c) = ^(c) — 1. Opazimo, da pravilo ^ ^ podaja bijektivno preslikavo med multimnozicami ^ moci n z lastnostjo ^(c) > 1 za vsak c G K in multimnozicami moci n — k. Zato je
|[(KN)s]n| = : K ^ No; M = n,^ > 1}| = |K(K,n — k)| = (n — ]
n — k
Osredotocimo se sedaj na relacijo . Mnozico ekvivalencnih razredov mnozice KN glede na to relacijo oznacimo s [KN]k. Vzemimo preslikavo /: N ^ K in ji priredimo razbitje
{/-1(c) : c G Im(/)}
mnozice N na |Im(/)| paroma disjunktnih nepraznih podmnozic. Opazimo, da poljubna ekvivalentna preslikava g = A o /, A G Sym(K), porodi isto razbitje mnozice N. Zato lahko za vsak i G {1,..., k} definiramo preslikavo, ki slika iz mnozice ekvivalencnih razredov preslikav /: N ^ K z i-elementno sliko Im(/) v mnozico razbitij mnozice N na i nepraznih podmnozic, po pravilu [/] ^ {/-1 (c) : c G Im(/)}. Ni tezko preveriti, da je ta preslikava
bijektivna. Od tod neposredno sledita formuli za stevilo ekvivalenčnih razredov na mnozičah KN in (KN)s.
Razbitje, ki pripada injektivni preslikavi, je natanko razbitje mnoziče N na enoelementne mnoziče. Zato je ekvivalenčni razred injektivnih funkčij en sam, če seveda kasna injketivna preslikava iz N v K obstaja - sičer je stevilo ekvivalenčnih razredov enako 0.
Podobno razmislimo tudi situačijo v primeru relačije . Tu vlogo razbitij mnoziče N nadomestijo razbitja naravnega stevila n. Podrobnosti izpusčamo.	I
6 Delovanja grup in preštevanje orbit 6.1 Permutačije
Bijektivno preslikavo iz mnoziče O v mnozičo O imenujemo tudi permutačija mnoziče O. Ker lahko tak sno bijektivno preslikavo enolično predstavimo z urejeno n-teričo njenih, paroma različnih slik, je permutačij n-elementne mnoziče natanko toliko kot je vseh taksnih n-terič, torej n!.
Mnozičo vseh permutačij mnoziče O bomo označili s Sym(O), identično preslikavo iz O v O pa z idn. Za zapis permutačij uporabljamo več različnih načinov, za nas pa bo najprimernej s i čiklični zapis permutačije, ki ga bomo predstavili na naslednjem primeru.
Naj bo O = {1, 2, 3, 4, 5, 6} in naj bo n: O ^ O permutačija podana s
n(1) = 3, n(2) = 6, n(3) = 5, n(4) = 4, n(5) = 1, n(6) = 2.
Tedaj je čiklični zapis permutačije n enak
n = (1, 3, 5)(2, 6)(4).
Pri tem stevila v prvem oklepaju beremo kot: "1 se preslika v 3, 3 se preslika v 5 in 5 se preslika v 1". Drugi oklepaj bi pomenil: "2 se preslika v 6 in 6 se preslika v 2". Zadnji oklepaj pa se bere kot: "4 se preslika v 4". Pri tem posameznim "oklepajem" rečemo čikli permutačije, stevilu elementov v posameznem oklepaju pa dolžina čikla.
Seveda čiklični zapis permutačije ni enolično določen: permutačijo n bi prav tako lahko zapisali na naslednje načine:
n = (5,1, 3)(2, 6)(4) = (3, 5,1)(6, 2)(4) = (6, 2)(3, 5,1)(4) = (6, 2)(4)(3, 5,1).
Kratek premislek pokaze, da lahko permutačijo n zapi semo v čiklični obliki na (3 ■ 2) ■ 3! = 18 načinov.
Kadar je iz konteksta razvidno, katere elemente permutačija permutira, čikle dolzine 1 iz čikličnega zapisa permutačije navadno izpu sčamo. Tako je običajnej s i zapis permutačije n naslednji:
n = (1, 3, 5)(2, 6).
Domenimo se se, da bomo sliko n(x) elementa x pri permutačiji n označavali v "eksponenti" obliki:' xn.
6.2 MnoZenje permutacij in simetrična grupa
Naj bo Q koncna mnozica, in Sym(Q) mnozica vseh permutacij mnozice Q. Obstajata dva standardna nacina, kako definirati mnozenje na Sym(Q):
Ker so permutacije preslikave, jih lahko komponiramo, kot smo to vajeni pri preslikavah. Na primer, ce je Q = {1, 2, 3, 4, 5}, g = (1,3,4)(2, 5) in h = (2,4, 5), potem je
g o h = (1, 3, 4, 2) in h o g = (1, 3, 5, 4).
Poleg operacije komponiranja o: Sym(Q) xSym(Q) — Sym(Q), o: (g, h) — g o h pa lahko na mnozici Sym(Q) definiramo s e binarno operacijo imenovano komponiranje z desne:
■ : Sym(Q) x Sym(Q) —y Sym(Q), ■ : (g, h) — h o g.
Medtem ko je navadno komponiranje uglaseno z obicajnim zapisom per-mutacij, saj velja (g o h)(a) = g(h(a)), pa je desno komponiranje uglaseno z eksponentnim zapisom permutacij, saj je
a(g-h) = (ag)h, vendar (g ■ h)(a) = (h(g(a)).
Operacijama o in ■ recemo tudi levo mnoZenje in desno mnoZenje permutacij.
Vaja. Preveri:
•	(1,4, 3)(2, 5) o (1, 2)(4, 5) = (1, 5, 3)(2, 4).
•	(1,4, 3)(2, 5) ■ (1, 2)(4, 5) = (1, 5)(2,4, 3).
•	(1, 3, 5) ■ (2, 4) = (1, 3, 5)(2, 4) = (1, 3, 5) o (2,4).
•	(1, 3, 4) ■ (4, 5) = (1, 3, 4) o (4, 5).
Ker za vsako permutacijo g G Sym(Q) velja idn o g = g o idn = g in idn ■ g = g ■ idn = g ter ker sta obe mnozenji (tako levo kot desno) asociativni, postane mnozica Sym(Q), skupaj z vsako od njiju, grupa, v kateri vlogo enote igra permutacija idn.
Definicija 6.1 Grupi (Sym(Q), o) in (Sym(Q), ■) imenujemo leva simetricna grupa in desna simetricna grupa množice Q in ju oznacimo s simboloma SymL(Q) in SymD(Q).
Ker smo se odlocili za eksponentni zapis permutacij, nam bosta ljubsa desno mnozenje in desna simetricna grupa. Zato bomo grupo SymD (Q) oznacevali kar z Sn, pikico pri desnem mnozenju pa, kot je to obicajno, izpu scali.
Podgrupi grupe Sn recemo permutacijska grupa na mnozici Q.
6.3 Delovanja grup
Dve permutačiji na mnoziči O predstavljata isti element grupe Sym(O) natanko tedaj, ko elemente slikata na enak način. V kombinatoriki pa je velikokrat smiselno opazovati grupe, katerih elementi sičer permutirajo mnozičo O, vendar tako, da smeta dva, sičer različna elementa grupe "delovati" na mnoziči O na enak način. Da bomo lahko obravnavali tudi tak sne situačije, vpeljimo pojem "delovanja grupe".
Naj bo G grupa in O mnoziča. Delovanje grupe G na mnoziči O je poljubna preslikava
$:O x G ^ O, (w,g) ^ ,
ki zado sča pogojema:
•	w1 = w za vse w G O;
•	= (wg)h za vse w G O in g, h G G.
Delovanje grupe G na O pa lahko opisemo tudi kot homomorfizem iz G v simetrično grupo Sq na naslednji način. Naj bo < O x G ^ O delovanje. Definirajmo preslikavo
<1: G ^ Sn, <(g) = (w M- ).
Ni se tezko prepričati, da je < je homomorfizm group
Obratno, naj bo G ^ Sq poljuben homomorfizem grup. Definirajmo delovanje grupe G na O:
x G ^ O, (w,g) m-
Pri tem velja naslednje: Ce pričnemo z delovanjem <, mu priredimo ho-momorfizem < in temu homomorfizmu spet priredimo delovanje <, dobimo natanko začetno delovanje <.
< = <
To kaze na to, da lahko delovanje grup enakovredno definiramo tako, kot smo to storili v teh zapiskih, ali pa kot homomorfizem v simetrično grupo.
Ce delovanje grupe G na O predstavimo kot homomorfizem G ^ Sq, potem sliki homomorfizma ^ rečemo permutačijska reprezentačija grupe G in jo označimo z Gn. Opazimo, da je Gn permutačijska grupa, ki vsebuje natanko tiste permutačije mnoziče O, ki permutirajo tako, kot permutira kaksen element iz g.
Mnozici vseh g G G, ki pribijejo vsak element mnozice Q se imenuje jedro delovanja. Ce na delovanje pogledamo kot na homomorfizem G ^ Sq, potem je jedro delovanja ravno jedro homorfizma
Ker(^) = {g G G : tf(g) = id}.
Iz 1. izreka o homomorfizmih iz teorije grup tedaj sledi Gn = G/Ker(^).
Ce jedro delovanja vsebuje le nedelavni element grupe, potem je delovanje zvesto. C e G deluje zvesto na Q, potem je pripadajoci homomorfizem G ^ Sn injektiven, in zato Gn = G. V tem smislu lahko zvesta delovanja enacimo s pripadajocimi permutacijskimi grupami.
6.4 Stabilizatorji in orbite delovanja
Naj grupa G deluje na mnozici Q in naj bo u poljuben element mnozice Q. Mnozici
Gw = {g G G : ug = u}
vseh elementov grupe G, ki element u pribijejo, recemo stabilizator elementa u v grupi G, mnozici slik
uG = {ug : g G G}
pa recemo orbita elementa u pri delovanju grupe G.
Za zgled si oglejmo klasicni primer iz teorije grup. Za poljubno grupo G in elementa g, h G G definirajmo
hg = g-1hg.
Z lahkoto se prepricamo, da smo s tem definirali delovanje grupe G na mnozici Q = G, ki ga imenujemo delovanje grupe G na sebi s konjugacijo. Stabilizator Gh elementa h pri tem delovanju vsebuje vse tiste elemente g G G, za katere velja g-1hg = h, torej tiste g G G, ki komutirajo s h. Podobno, element g G G lezi v jedru tega delovanja, ce in samo ce velja g-1hg = h za vsak h G H, torej ce in samo ce lezi g v centru grupe G. Orbite hG imenujemo konjugiranostni razredi elementov grupe G.
Definiramo lahko tudi delovanje grupe G na mnozici Q = {H : H < G} vseh njenih podgrup s predpisom:
Hg = g-1Hg = {g-1hg : h G H}.
Grupi Hg pri tem recemo konjugiranka grupe H. Stabilizator GH podgrupe H G Q je enak normalizatorju grupe H v G.
Trditev 6.2 Naj grupe G deluje na množici Q. Tedaj za poljubna elementa g G G in u G Q velja
G(w«) = (GW)g .
Stabiližatorja dveh elementov množice ki ležite v isti orbiti grupe G, sta torej konjugirana.
Dokaz: Vzemimo poljuben element h G G. Tedaj trditev neposredno sledi iz naslednje verige ekvivalenc:
h G Gw ^ uh = u ^ wgg-1hg = ug ^ g-1hg G G(w9).
Trditev 6.3 Množica orbit pri delovanju grupe G na množici Q predstavlja ražbitje množice Q.
Dokaz: Ker vsak element mnozice u lezi v orbiti uG, je unija vseh orbit pri delovanju grupe G enaka Q. Naj bosta uG in PG orbiti z nepraznim presekom. Dokazati moramo, da sta tedaj enaki. Res. Naj bo 7 G uG n PG in naj bo 5 poljuben element orbite uG. Tedaj obstajajo elementi g, h, t G G, da je y = ug = Ph in 5 = u*. Sledi 5 = u* = (Phg-1 )* = Phg-1*. S tem smo dokazali, daje uG C PG. Ce zamenjamo vlogi u in P, dokazemo vsebovanost se v drugo smer in s tem enakost orbit uG in PG. Orbite pri delovanju grupe G torej res tvorijo razbitje mnozice Q.	I
Trditev 6.4 Naj grupa G deluje na množici Q in naj bo u poljuben element množice Q. Tedaj velja enakost
|GW ||uG| = |G|.
Dokaz: Oznacimo z G(u — P) mnozico elementov grupe G, ki preslikajo tocko u v izbrano tocko P mnozice Q. Ce P ni element orbite uG, potem je mnozica G(u — P) prazna. Predpostavimo sedaj, da je P G uG, izberimo element g G G(u — P) in definirajmo preslikavo f: G(u — P) — G s predpisom f (h) = hg-1. Z lahkoto se prepricamo, da je preslikava f in-jektivna in da je njena slika enaka stabilizatorju Gw. Zato je moc mnozice G(u — P) enaka redu stabilizatorja Gw, brz ko P pripada orbiti uG, in je enaka 0, ce lezi P zunaj uG.
Sestejemo sedaj moci mnozic G(u — P) po vseh P G Q in vsoto oznacimo z S. K vsoti S prispevajo le tisti elementi P, ki lezijo v orbiti uG - vsak
tak sen natanko |GW |. Zato je ta vsota enaka |GW | |wG|. Po drugo strani pa vsak element g grupe G lezi v natanko eni mnoziči G(w ^ P), namreč tisti
pri kateri je P = . Zato je vsota S enaka tudi |G|. S tem je dokaz končan.
■
Opomba. Prijemu, ki smo ga uporabili v zgornjem dokazu, v kombinatoriki pogosto rečemo računovodsko pravilo (angl. čounting prinčiple). Računovodsko pravilo pravi, da je vsota elementov dane matrike enaka tako vsoti njenih vrstičnih vsot kot tudi vsoti njenih stolpčnih vsot. Pravilo lahko v zgornjem dokazu uporabimo na sledeč način: Definiramo matriko, katere vrstiče so indeksirane z elementi množiče O, stolpči z elementi grupe G, na presečisču vrstiče P G O ter stolpča g G G pa stoji 0 ali 1, odvisno od tega ali je g G G(w ^ P) ali ne. Vrstična vsota pri elementu P G O je tedaj enaka |G(w ^ P)|, vse stolpčne vsote pa so enake 1.
Definicija 6.5 Delovanje grupe G na mnozici O je tranzitivno, ce je wG = O za nek (in tedaj vsak) w G O.
6.5 Preštevanje orbit in Cauchy-Frobeniusova lema
Pri prestevanju kombinatoričnih objektov nam je velikokrat v pomoč preprosta, vendar uporabna formula za izračun stevila orbit grupe, ki se v literaturi pogosto pojavlja z imenom Burnsidova lema, ali pa (zgodovinsko pravilneje) Caučhy-Frobeniusova lema. Poglejmo, kaj pravi.
Izrek 6.6 (Caučhy-Frobeniusova lema) Naj grupa G deluje na mnoZici O in naj m označuje število orbit tega delovanja. Za element g G G naj Fix(g) = {w : = w} predstavlja mnoZico elementov O, ki jih element g pribije. Tedaj velja enakost
m|G| = ^ |Fix(g)|.
Dokaz: Naj bodo O1,..., Om orbite delovanja grupe G na O. Oglejmo si mnozičo
M = {(a, g) : a G O,g G Ga}
in pre stejmo njene elemente na dva načina. Najprej opazimo, da je moč mnoziče M enaka vsoti moči stabilizatorjev Ga po vseh a G O. Vemo tudi, daje moč stabilizatoja | Ga | enaka |G|/|Oj|, kjer je Oj tista orbita, ki vsebuje element a. Zato
m	i	m
|M| = E |Ga| = ^^ M = £ |G| = m|G|.
Po drugi strani pa lahko elemente mnozice M prestejemo tako, da sestejemo moci mnozic
Mfl = {(a,g) : a G Q,g G Ga} = {(a,g) : a G Fix(g)}.
Zato
|M| = £ |Mg| = £ |Fix(g)|.
S tem je izrek dokazan.	I
6.6 Delovanje grupe na funkcijah
Pricnimo z zgledom. Oglisca pravilnega sestkotnika bi radi pobarvali s tremi barvami: belo, rdeco in modro. Na koliko nacinov lahko to storimo, ce stejemo dve barvanji kot enaki, brz ko lahko iz enega preidemo v drugega s pomocjo vrtenja sestkotnika okoli njegovega sredisca?
Prevedimo nalogo v matematicni jezik. Oznacimo oglisca sestkotnika s stevili 1,...,6, zacens i z 1 in nadaljujoc v pozitivni smeri z 2, 3 itd. Barvanje sestkotnika si lahko predstavljamo kot funkcijo iz mnozice oglisc N = {1,..., 6} v mnozico barv K = {B, R, M}.
Naj bo G grupa vrtenj sestkotnika, predstavljena kot permutacijska grupa na mnozici ogli sc. C e barvanje p: N ^ K "zavrtimo" z rotacijo g G G, potem dobimo naceloma drugacno barvanje pg: N ^ K doloceno s pravilom pg(a) = p(ag ). Dve barvanji p1,p2: N ^ K sta torej "enaki", ce obstaja permutacija g G G, za katero je p2 = p1 g. Ni tezko videti, da je preslikava KN x G ^ KN, (p, g) ^ pg, delovanje grupe G na mnozici KN. Iz zgoraj povedanega sledi, da sta dve barvanji sestkotnika "enaki" natanko tedaj, ko sta v isti orbiti tega delovanja. Ce zelimo re siti zastavljeno nalogo, moramo torej pre s teti s tevilo orbit induciranega delovanja grupe G na KN. Odgovor ponuja naslednja posledica Cauchy-Frobeniusove leme.
Izrek 6.7 Naj bosta N in K končni mnozici in naj končna grupa G deluje na mnozici N. Za vsak g G G naj c(g) označuje število orbit grupe (g) na mnozici N. Tedaj je stevilo orbit delovanja grupe G pri njenem naravnem delovanju na mnozici preslikav KN enako
iG £ iKi"<s>.
Dokaz: Spomnimo se, da grupa G deluje na mnozici KN funkcij iz N v K v skladu z naslednjim predpisom:
pg(a) = p(ag-1), p G Kn, g G G, a G N.
Ni tezko videti, da element g G G pribije funkcijo p: N — K natanko tedaj, ko je p konstantna na vsaki orbiti grupe (g). Tak sna funkcija je enolicno dolocena z naborom c(g) elementov iz K. Zato je funkcij, ki so konstantne na vsaki orbiti grupe (g) natanko |K|c(g). Z drugimi besedami, Fix(g) = |K|c(g). Ce oznacimo stevilo orbit grupe G na KN z m in uporabimo Cauchy-Frobeniusovo lemo (Izrek 6.6), dobimo
m|G| = £ Fix(g) = £ |K|c(g).
g€G	g€G
Zgornjo enakost delimo z |G| in dobimo enakost, ki jo dokazujemo. I
Vrnimo se k nalogi o barvanju ogli sc pravilnega sestkotnika. Grupa G vrtenj sestkotnika vsebuje naslednje permutacije:
id, s = (1, 2, 3, 4, 5, 6), s2 = (1, 3, 5)(2, 4, 6),
s3 = (1, 4)(2, 5)(3, 6), s4 = (1, 5, 3)(2, 6, 4), s5 = (1, 6, 5, 4, 3, 2), ki imajo naslednje stevilo orbit:
c(id) = 6, c(s) = 1, c(s2) = 2, c(s3) = 3, c(s4) = 2, c(s5) = 1.
Zato je iskano stevilo razlicnih barvanj pravilnega sestkotnika z dvema barvama enako:
-(36 + 31 + 32 + 33 + 32 + 31) = 130.
6
6.7 Ciklični indeks delovanja grupe
Nalogo o barvanju oglisc pravilnega sestkotnika s tremi barvami lahko nekoliko otezimo in vprasamo, koliko izmed 130 barvanj je taks nih, da so natanko 3 oglisca bela, 2 ogli sci rdeci in 1 oglisce modro. Pri tem barvanj, ki so v isti orbiti delovanja grupe vrtenj sestkotnika se vedno ne locimo med seboj. Na tovrstna vprasanja nam odgovarja teorija Polya in Redfielda. Pricnimo s pojmom, ki na videz nima velike zveze z na so nalogo.
Naj grupa G deluje na mnozici N. Vzemimo poljuben element g G G in s kj(g), i = 1,...,n, oznacimo stevilo orbit grupe (g) dolzine i. Ce je g permutacija mnozice N, porojena z delovanjem elementa g, tedaj ki (g)
ustreza številu ciklov dolžine i v cikličnem zapisu permutacije g. Zato n-terici (k1(g),k2(g), ...,kn (g)) rečemo ciklična .struktura elementa g.
Elementu g G G s ciklicno strukturo (k1,k2,..., kn) priredimo element zg(x1,..., xn) = x1klx2k2 ■ ■ ■ xnkn kolobarja Q[x1,x2,..., xn]. Vsoto
ZG(x1, ...,xn)= |-G ^ zg (x1, ...,xn)
1 1 geG
imenujemo ciklični indeks delovanja grupe G.
Zgled. Izračunaj ciklični indeks naravnega delovanja ciklične grupe C6 na množici {1,2,3,4, 5,6}.
Rešitev: Sestavimo tabelo elementov grupe C6 in njihovih ciklicnih struktur:
g	cikl. strukt.	zg(xi, x2, x3, x4, xs, xq)
id	(6, 0,0,0,0, 0)	xi6
(1, 2, 3, 4, 5, 6)	(0, 0,0,0,0,1)	xe
(1, 3, 5)(2, 4, 6)	(0, 0, 2,0,0, 0)	2 x32
(1,4)(2, 5)(3, 6)	(0, 0,0, 3,0, 0)	x23
(1, 5, 3)(2, 6, 4)	(0, 0, 2,0,0, 0)	2 x32
(1, 6, 5, 4, 3, 2)	(0, 0,0,0,0,1)	X6
Ciklicni indeks grupe A4 lahko precitamo iz zadnjega stolpca:
Zc6 (x1 ,x2, x3, x4,x5,x6) = 6 (x16 + x23 + 2x32 + 2x6) .
6.8 Izrek Redfielda in Polya
Zvezo med ciklicnim indeksom delovanja in stevilom neekvivalentnih barvanj s predpisanim stevilom objektov dane barve podaja izrek Redfielda in Polya.
Izrek 6.8 (Redfield 1927, Polya 1937) Naj grupa G deluje na množici N moči n in naj bo K = {c1,... ,ck} poljubna množica moCi k. CikliCni indeks delovanja grupa G na množici N označimo z ZG(x1,... ,xn). Definirajmo polinom
k k k p(t1 ,...,tk) = zg(Y, ti, ^ t2,..., £ tn) g Q[t1,...,tk ].
i=1 i=1 i=1
Tedaj je koeficient v polinomu p pri monomu t^1 t^2 • • • tfcfe enak številu tistih
orbit pG induciranega delovanja grupe G na mnozici preslikav KN, za katere
je p-1 (cj) = a za vsak i G {1,..., k}.
S pomocjo zgornjega izreka re simo nalogo z zacetka razdelka takole. V ciklicni indeks ciklicne grupe C6 vstavimo namesto nedolocenke xj, i = 1,..., 6, vsoto t1j + t2j + 13j. Dobimo:
6 (x16 + X23 + 2x32 + 2xe) =
6 ((t1 +12 +13)6 + (t2 +12 +13)3 + 2(t1 +13 +13)2 + 2(t6 +12 +16)) =
Zanima nas koeficient pri monomu tft2t3. Le-ta se pojavi le pri clenu (t1 + t2 +13)6 in tu s koeficientom
6 \ 6!
= 60.
,3,2,1) 3! • 2! Iskano stevilo neekvivalentnih barvanj je torej enako 60 = 10.
7 Rekurzivne enačbe
Opomba. Zapiski teh predavanj so nekoliko zgosceni. Pomagate si lahko tudi z razlago v [3].
7.1 Fibonaccijevo zaporedje
Oglejmo si dobro znani zgled zaporedja stevil F0, F1, F2,..., ki je definirano rekurzivno s predpisom
Fo = 0, F1 = 1, Fra+2 = Fra+1 + Fn za vse n G No.
tako definirano zaporedje imenujemo Fibonaccijevo zaporedje, stevilo Fn pa n-to Fibonaccijevo stevilo. Tip vpra sanja, s katerim se bomo ukvarjali v tem razdelku, je, kako izracunati n-to Fibonaccijevo stevilo, ne da bi pred tem izracunali vsa predhodna Fibonaccijeva stevila.
Zgornjo nalogo lahko nekoliko posplosimo. Naj bodo c0,..., cd poljubna kompleksna stevila in naj bo f: N0 — C poljubna funkcija. Iscemo zaporedje kompleksnih stevil a0, a1, a2,..., katerega prvih d clenov je enakih v naprej predpisanim vrednostim 60,..., 6d-1 G C,
ao = 60, a1 = 61, ..., ad-1 = 6d-1	(1)
in ki za vsak n G N0 zadosca enakosti
cdan+d + Cd-1an+d-1 + ... + C1an+1 + C0a„ = f (n)	(2)
Pri tem bomo predpostavili, da je c0, cd = 0, saj bi sicer lahko s preostevil-cenjem dobili enakost istega tipa, vendar z manj cleni na levi strani enakosti. Z deljenjem z vodilnim koeficientom Cd lahko predpostavimo celo, da je Cd = 1.
Izrazu (2) recemo linearna rekurzivna enačba s konstantnimi koeficienti, enakostim (1) pa začetni pogoji enačbe (1). Ce je funkcija f (n) na desni strani enakosti konstantno enaka nic, pristavimo se besedico homogena. Neznanka v enacbi (2) je simbol (an)neNo, ki predstavlja neznano zaporedje (in ne neznano stevilo, kot smo vajeni pri obicajnih enacbah iz srednjesolske matematike).
Linearno rekurzivno enacbo s konstantnimi koeficienti lahko re s ujemo s pomocjo linearne algebre, in sicer v kontekstu vektorskega prostora vseh zaporedij, ki si ga bomo ogledali v naslednjem razdelku.
7.2	Prostor zaporedij
Naj bo F poljuben obseg. Preslikavi
a: No ^ F
rečemo zaporedje s členi v obsegu F. Vrednosti a(n), n G N0, rečemo člen zaporedja in ga navadno označimo z an. Zaporedje a pa navadno označimo s simbolom (an)No, včasih pa tudi povr sno s simbolom (a1, a2, a3,...). Mnozičo vseh zaporedij s členi v F označimo z FNo.
C e mnozičo FNo opremimo z operačijami sestevanja, mnozenja in mnozenja s skalarjem po komponentah, dobimo algebrsko strukturo, ki zadosča aksiomom algebre. Mi se bomo v nadaljevanju omejili na operačiji sestevanja in mnozenja s skalarjem, ter tako na mnozičo FNo gledali kot na vektorski prostor.
Spomnimo se, da za vsak vektorski prostor V nad obsegom F mnozičo vseh linearnih preslikav iz V v V označimo z End(V). C e mnozičo End(V) opremimo z operačijama sestevanja in mnozenja s skalarjem po komponentah, dobimo vektorski prostor. Ce pa na mnoziči End(V) definiramo se mnozenje kot komponiranje preslikav, postane vektorski prostor End(V) algebra. Nas bo se posebej zanimal element mnoziče End(V), ki mu rečemo preslikava pomika in je definiran s predpisom:
E: FNo ^ FNo, E (ao,a1,a2,...) = (ab a2, a3,...).
7.3	Linearne rekurzivne enačbe s konstantnimi koeficienti
Oglejmo si sedaj, v kaksni zvezi so linearne rekurzivne enačbe s prostorom zaporedij in endomorfizmi nad njimi. Naj bo
Q(x) = xd + Cd-1 xd-1 + ... + C1X + co, co = 0,
polinom s koefičineti v obsegu F. Ce namesto nedoločenke x vstavimo preslikavo E, dobimo nov element algebre End(FNo). Oglejmo si, kdaj je neko zaporedje (an)neNo v njegovem jedru. Opazimo, da velja naslednje:
(ara)„eNo G Ker(Q(E)) ^ ... ^
ara+d + Cd-1ara+d-1 + ... + C1 ara+1 + coa„ = 0 za vsak n G No. (3)
Ugotovili smo, da je jedro endomorfizma Q(E) natanko mnoziča vseh resitev enačbe (3). Polinomu Q(x) pri tem rečemo karakteristični polinom enačbe (3).
Pricnimo z resevanjem homogene enacbe (3). V nadaljevanju bomo predpostavili, da je F = C. Ce zelimo enacbo re siti, moramo poiskati jedro endomorfizma Q(E).
Karakteristicni polinom Q(x) najprej razcepimo na linearne faktorje:
Q(x) = (x — A1)S1 ••• (x — Afc )sk.
Iz linearne algebre se spomnimo naslednjega izreka.
Izrek 7.1 Ce sta p(x) in q(x) tuja polinoma in je A endomorfizem vektorskega prostora V, potem je jedro endomorfizma p(A)q(A) enako direktni vsoti jeder endomorfizmov p(A) in q(A).
Z indukcijo lahko zgornji izrek posplo simo na poljubno stevilo paroma tujih polinomov. Iz tega sledi naslednje:
Ker(Q(E)) = Ker((E — A1I71) © ... © Ker((E — Afc/)sfc)
Zadosca torej, da ugotovimo, kaj je jedro K = Ker((E—A/)s) za poljuben A = 0 in s G N. Premislimo najprej, da je razseznost taksnega jedra enaka s. V resnici dokazemo nekoliko splos nejso trditev.
Trditev 7.2 Naj bo p(x) = + ... + c1x + c0 poljuben polinom stopnje s. Tedaj je razseznost jedra Ker(p(E)) enaka s.
Dokaz: Definirajmo preslikavo
Ker(p(E)) ^ Fs, (an)neNo ^ (ao, a1,..., as_1).
Ta preslikava je ocitno linearna in injektivna. Je pa tudi surjektivna, saj lahko za vsak nabor zacetnih clenov a0,..., as-1 iz enakosti
an+s — cs_1an+s_1 ... c0an
rekurzivno izracunamo clene as,as+1,..., za katere bo zaporedje (an)n^No lezalo v jedru operatorja p(E). Vektorska prostora Ker(p(E)) in Fs sta torej izomorfna. S tem je trditev dokazana.	I
Zdaj vemo, da je razseznost jedra K enaka s. Zadosca torej najti s linearno neodvisnih zaporedij iz K. Z neposrednim racunom se prepricamo, da zaporedja
(An)n€No, (nAn)n€No, ("^"OnGNo, ..., (n^ 1An)n€No
lezijo v jedru K, in ker so ocitno linearno neodvisna, tvorijo njegovo bazo. Vsako zaporedju v jedru K je torej neka linearna kombinacija zgornjih zaporedij. C e so a0,...,as-1 koeficienti taksne linearne kombinacije, ima ustrezno zaporedje obliko (A(n)An)neNo, kjer je
A(n) = a0 + a1n + ... + as-1ns-1.
S tem smo dokazali:
Trditev 7.3 Zaporedje lezi v jedru operatorja (E — A/)s, če in samo če je oblike (A(n)An)neNo, kjer je A(n) kak polinom stopnje največ s — 1.
Ce povzamemo vse do sedaj povedano, ugotovimo, da se splosna resitev homogene enacbe (3) glasi:
an = A1(n)An + A2(n)An + ... + Afc (n)A£,
kjer je A^n) poljuben polinom stopnje najvec si — 1.
7.4 Linearne nehomogene enačbe s konstantnimi koeficienti
Splo sna re sitev nehomogene enacbe
Cda„+d + Cd-1 an+d-1 + ... + C0a„ = f (n)
ima obliko
an = zn + bn ,
kjer je 6n kaka (imenujmo jo posebna) resitev zgornje enacbe in zn resitev pripadajoce homogene enacbe
CdZ„+d + Cd-1Zn+d-1 + ... + C0^„ = 0 . Kadar je funkcija f (n) oblike
f (n) = p(n)an ,	(*)
kjer je p(n) polinom stopnje r in a s-kratna nicla karakteristicnega polinoma Q(x) (lahko je tudi s = 0), resitev 6n poi scemo z nastavkom
6ra = nsP(n)an ,
kjer je P (n) polinom stopnje r z nedolocenimi koeficienti.
Kadar je nehomogeni del f (n) enak vsoti funkcij oblike (*), f (n) = f1(n) + f2(n) + ... + fk(n), je posebna re sitev 6n vsota posebnih resitev nehomogenih enacb Cda„+d + Cd-1an+d-1 + ... + C0a„ = fi(n), 1 < i < k.
Zgled. Poisči splosno resitev rekurzivne enačbe
an+2 — 2an+1 + an = 3n + 1.
Rešitev: Karakteristični polinom Q(x) = (x — 1)2 ima a = 1 za dvojno ničlo. Zato posebno re s itev bn poi s čemo z nastavkom bn = n2(An + B)1n. Nastavek vstavimo v enačbo in dobimo
A(n + 2)3 + B (n + 2)2 — 2A(n + 1)3 — 2B(n + 1)2 + An3 + Bn2 = 3n + 1.
Odpravimo oklepaje in primerjamo koefičiente pri potenčah n. Dobimo sistem linearnih enačb za koefičienta A in B:
6A = 3, 2B + 6A = 1 .
Sistem re s imo in dobimo posebno re s itev bn = 2n3 — n2. Re s imo se pripadajočo homogeno enačbo, resitev je zn = C+Dn, ter obe re sitvi sestejemo: an = C + Dn — n2 + 2 n3.	■
8 Osnovno o grafih
Opomba. Ta razdelek v veliki meri sledi prvemu poglavju knjige [3]. 8.1 Definicija in osnovni pojmi
Naj bo V (obicajno koncna) neprazna mnozica in E poljubna druzina dvoele-mentnih podmnozic mnozice V. Paru r = (V, E) pravimo graf na mnozici točk (tudi vozlišč) V = V (r) in z množico povezav E = E (r). Ce je {u, v} povezava grafa r, tedaj pravimo, da sta tocki u in v sosednji in pi s emo u ~ v. Hkrati pravimo, da sta tocki u in v kraji sci povezave {u, v}. Povezavo {u, v} vcasih pisemo krajse kot uv ali vu.
Opomba. Vcasih dopuscamo tudi grafe, ki imajo med nekaterimi pari tock vec povezav (vzporedne povezave) ali pa imajo povezave, ki imajo obe krajisci enaki (zanke). Takim grafom bomo rekli multigrafi. Ce definiramo, da zanka prispeva 2 k stopnji tocke, potem lema 8.1 velja tudi za multigrafe. Kadar zelimo poudariti, da govorimo o (multi)grafih brez zank in vzporednih povezav, takim grafom recemo enostavni grafi.
Poleg multigrafov je grafom sorodna stuktura usmerjeni graf. Neformalno si ga lahko predstavljamo kot graf (ali celo kot multigraf), kjer vsako povezavo usmerimo. Namesto kraji sc povezave v tem primeru govorimo kot o zacetku in koncu povezave (repu in glavi povezave). C e je u rep in v glava povezave uv, potem napisemo u ^ v in recemo, da je uv usmerjena povezava grafa r.
Grafe si radi tudi narisemo. To storimo tako, da vozlisca grafa predstavimo kot tocke ravnine, povezavo med sosednjima vozliscema pa kot krivuljo (obicajno kar kot daljico) s krajiscema v tockah ravnine, ki ustrezata krajiscema povezave.
Stopnja točke (tudi valenca točke) u v grafu r, oznacimo jo z degr(u), je enaka stevilu povezav grafa r, ki imajo tocko u za svoje krajisce. Tockam stopnje 0 pravimo izolirane tocke. Graf r je regularen, ce obstaja tako stevilo k, da velja degr(u) = k za vsak u G V (r). V tem primeru recemo tudi, da je graf r k-regularen, oziroma, da je regularen stopnje k. Stopnje tock in stevilo povezav grafa veze naslednja enakost:
Lema 8.1 (O rokovanju). Za vsak graf r velja
£ deg(v) = 2 •lE(r)|.
vev (r)
Dokaz: Uporabili bomo tako imenovano računovodsko pravilo. Naj bo M mnoziča vseh urejenih parov (u, e) G V (r) x E(r), za katere je u krajisče povezave e. Pre stejmo elemente mnoziče M. Po eni strani velja
|M| = E deg(u), «ev (r)
po drugi strani pa
|M| = E 2 = 2 ■ |E(r)|.
eeE(r)
S tem je trditev dokazana.	I
Posledica 8.2 Vsak graf ima sodo mnogo tock lihe stopnje.
Opomba. V usmerjenih grafih namesto stopnje deg(v) definiramo vhodno stopnjo deg-(v) in izhodno stopnjo deg+ (v) točke v, pri čemer prva predstavlja stevilo točk u grafa r, za katere je uv usmerjena povezava grafa r, druga pa stevilo točk u grafa r, za katere je vu usmerjena povezava grafa r. V kontekstu grafov lema o rokovanju preide v enakost
E deg-(v)= E deg+(v) = |E|. »ev (r)	»ev (r)
Graf r' je podgraf grafa r, če velja V (r') C V (r) in E(r') C E (r). Podgraf r' je vpet, če velja V (r') = V (r), in je indučiran z mnozičo točk U C V (r), če velja V (r') = U in E (r') = {uv G E (r) | u,v G V (r')}. V tem primeru pi semo tudi r' = r[U].
Graf r je dvodelen, če lahko mnozičo točk V (r) zapisemo kot disjunktno unijo dveh podmnozič A, B C V (r) tako, da je za vsako povezavo uv G E (r) ena od točk u, v vsebovana v mnoziči A, druga pa v mnoziči B. Mnoziči A in B imenujemo mnoziči dvodelnega razbitja grafa r.
8.2 Metrične lastnosti
Zaporedje točk vov1... vk grafa r je sprehod dolzine k, če v ~ vi+1 za 0 < i < k. Sprehod je enostaven, če so vse povezave na njem različne. Sprehod je sklenjen, če je vo = vk. Sprehod, na katerem so vse točke različne, je pot, enostaven sklenjen sprehod z vsaj eno povezavo, na katerem sta enaki le prva in zadnja točka, pa je čikel grafa. Zaradi enostavnosti dopusčamo tudi sprehode dolzine 0, tj. sprehode oblike vo. Sprehod dolzine 0 je seveda hkrati tudi pot, domenimo pa se, da ga ne bomo imeli za čikel.
Lema 8.3 Ce med točkama grafa obstaja sprehod dolžine k, potem med njima obstaja tudi pot dolžine največ k.
Dokaz: Naj bosta u in v poljubni tocki grafa r med katerima obstaja sprehod. Ce je u = v, tedaj med njima obstaja pot dolzine 0 in trditev ocitno velja. Predpostavimo torej, da je u = v. Med vsemi sprehodi med u in v izberimo najkrajsega, denimo S = v0v1... vm, u = v0, v = vm. Dovolj je dokazati, da je S pot. Pa denimo, da temu ni tako. Tedaj obstajata v zaporedju v0, v1,..., vm kaka tocka ponovi, denimo vi = v j za 0 < i < j < m. Vendar tedaj je tudi S' = v0v1... vivj+1... vm sprehod med u in v, ki pa je ocitno kraj si od sprehoda S. To pa nasprotuje nas i izbiri sprehoda S in dokazuje, da je S pot.	I
Za dve tocki u in v recemo, da sta v isti povezani komponenti, ce med njima obstaja sprehod. Ni tezko videti, da je relacija "biti v isti povezani komponenti" ekvivalencna. Njenim ekvivalencnim razredom recemo povezane komponente grafa. Graf je povezan, ce ima eno samo povezano komponento.
Razdaljo dr(u, v) med tockama u in v v grafu r definiramo kot dolzino najkraj se poti od u do v v r. (C e taka pot ne obstaja, za razdaljo vzamemo vrednost to.) Kot pove lema 8.3, bi lahko razdaljo ekvivalentno definirali tudi kot dolzino najkraj sega sprehoda med danima tockama.
S tako definirano razdaljo postane mnozica tock povezanega grafa metricni prostor. Najvecji razdalji med parom tock grafa pravimo premer (tudi di-ameter) grafa,
diam(r) = max{dr(u, v) | u, v G V (r)} .
Dolzini najkrajsega cikla v grafu pravimo tudi notranji obseg (ali ožina) grafa.
8.3 Nekatere druZine grafov
V tem razdelku si bomo ogledali nekaj druzin grafov, ki jih pogosto srecujemo v zgledih in nalogah.
Polni grafi Kn: V(Kn) = Zn, E(Kn) = {uv | u, v G Zn,u = v}. Polni graf Kn ima n tock in (n) = n(n2-1) povezav. Je (n — 1)-regularen graf in je dvodelen le za n = 1 in 2.
Poti P„: V(Pn) = Zn, E(Pn) = {u(u + 1) | u = 0,1,..., n — 2}. Pot P„ ima n tock in n — 1 povezav (njena dolzina je n — 1). Za n = 1 in n = 2 je enaka grafu Kn. Vse poti so dvodelni grafi.
o	o-o
Slika 1: Polni grafi K1, K2, K3, K4 in K5.
O	O-C)	o-o-o
Slika 2: Poti Pi, P2, P3 in P4.
Cikli Cn (n > 3): V(Cn) = Zn, E(Cn) = {u(u + 1) | u G Zn}. Kadar dopuščamo tudi multigrafe, sta definirana še cikla C1 (zanka) in C2 (par vzporednih povezav). Cikel Cn ima n točk in n povezav. Je 2-regularen graf in je dvodelen natanko tedaj, ko je n sodo število. Vsak 2-regularen graf je disjunktna unija enega ali več ciklov. Cikel C3 imenujemo tudi trikotnik.
n	?-'?
6-b i-(i
Slika 3: Cikli C3, C4, C5 in C6.
Polni dvodelni grafi Km,n: V (Km,n) = A U B, kjer velja |A| = m, |B| = n in A n B = 0, E(Km,n) = {uv | u G A, v G B}. Polni dvodelni graf Km,n ima m + n točk in mn povezav. Graf Km,n je regularen natanko tedaj, ko je m = n. Vsi grafi Km,n so dvodelni. Grafom K1,n pravimo tudi zvezde.
Hiperkocke Qd: V(Qd) = {(ui, u2,..., ud) | Ui G {0,1}}, E(Q,n) = {uv | u, v G V(Qd) : d=1 |ui — vi| = 1}. Običajno med hiperkocke stejemo tudi 0-razsezno kočko Q0 = K1. Hiperkočka Qd (skelet d-razsezne kočke) ima 2d točk in d ■ 2d 1 povezav. Je d-regularen graf. Vse hiperkočke so dvodelni grafi (za mnoziči dvodelnega razbitja vzamemo mnozičo točk, ki imajo sodo mnogo komponent enakih 0, in mnozičo točk, ki imajo liho mnogo komponent enakih 0).
Kolesa W,n (n > 3): V(Wn) = Z,nU{^}, E(Wn) = {u(u+1),uto | u G Zn}. Graf Wn ima n + 1 točk in 2n povezav. Za kolesa velja 5(Wn) = 3 in A(Wn) = n. Edino regularno kolo je W3 ~ K4. Nobeno kolo ni dvodelen
Slika 4: Polni dvodelni grafi K1,g, K2,4 in K3,3.
10 11
o-o
110 111 100/1 101
010
011
010 011 111 110 101 100
000 001
1 00 01 000 001
Slika 5: Hiperkočki Q1 in Q2 ter dve sliki hiperkočke Q3
graf.
Slika 6: Kolesa Wi, W in W>.
Posplošeni Petersenovi grafi Pn,k (n > 3 in 0 < k < n): V(Pn,fc) = {ui,vi | i G Zn}, E(Pn,fc) = {uiui+1 ,ujvj,vjvj+fc | i G Zn}. Posploseni Petersenov graf Pn,k ima 2n točk. Ce je n = 2k, ima 3n povezav in je kubičen graf, za n = 2k pa ima 5n povezav. Graf Pn,k je dvodelen natanko tedaj, ko je stevilo n sodo in stevilo k liho. Druzina ima ime po Petersenovem grafu P5,2.
Krožni grafi Cir(n; S): Naj bo S poljubna podmnoziča grupe Zn, ki ne vsebuje elementa 0 in ki z vsakim elementom s G S vsebuje tudi nasprotni element n — s. Krozni graf r = Cir(n; S) na n točkah in s simbolom S je določen takole:
v (r) = Zn
in
E(r) = {uv | v — u G S} .
Med krozne grafe spadajo polni grafi in čikli: Kn = Cir(n; {1,2,..., n — 1}) in Cn = Cir(n; {1, n — 1}).
Slika 7: Petersenov graf in posplosena Petersenova grafa P8,1 in P8,2.
Krozni graf Cir(n; S) ima n tock in povezav. Je |S|-regularen graf. Naj bo S = {s1,..., sd}, kjer je d > 1. Ce je gcd(n, s1,... ,sd) = 1, potem je krozni graf Cir(n; S) dvodelen natanko tedaj, ko je stevilo n sodo, vsa stevila si, 1 < i < d, pa so liha.
Cayleyjevi grafi Cay(G; S): Cayleyjevi grafi so posplositev kroznih grafov. Naj bo G koncna grupa in S poljubna podmnozica grupe G, ki ne vsebuje enote grupe G in ki z vsakim elementom s G S vsebuje tudi nasprotni element s-1. Cayleyjev graf r = Cay(G; S) grupe G in s simbolom S je dolocen takole:
V (r) = G in E(r) = {uv | uv-1 G S} .
Med cayleyjeve grafe spadajo tudi hiperkocke, saj lahko graf Qd predstavimo kot cayleyjev graf grupe Z^ s simbolom S = {(1,0,..., 0),(0,1,..., 0),..., (0, 0,..., 1)}. Cayleyjevi grafi so |S|-regularni grafi.
9 Izomorfizmi in avtomorfizmi
opomba. Ta razdelek v veliki meri sledi drugemu poglavju knjige [3].
Vzemimo grafa r in r'. Bijektivni preslikavi p : V (r) ^ V (r'), za katero je uv G E(r) natanko tedaj, ko je p(u)p(v) G E (r'), pravimo izomorfizem grafov. Grafa r in r' sta izomorfna, oznaka r ~ r', če med njima obstaja kaksen izomorfizem. Pri delu z grafi izomorfnih grafov med seboj običajno ne ločimo (npr. pravimo, da graf vsebuje cikel, kar pomeni, da vsebuje podgraf, ki je izomorfen nekemu ciklu). V primeru, ko je graf r' kar enak grafu r, izomorfizmu grafov pravimo avtomorfizem grafa. C e mnozico av-tomorfizmov danega grafa r opremimo z operacijo komponiranja preslikav, dobimo grupo, ki ji pravimo grupa avtomorfizmov grafa r in jo oznacimo z Aut(r). Kadar za poljubni tocki grafa obstaja avtomorfizem, ki prvo preslika v drugo, pravimo, da je graf tranzitiven po točkah. Vsi cayleyjevi grafi so tranzitivni po tockah.
9.1 Izomorfnost grafov
Lastnosti grafa, ki jo imajo poleg grafa samega tudi vsi z njim izomorfni grafi, pravimo invarianta grafa. Osnovni nacin, s katerim dokazemo, da grafa nista izomorfna, je, da poiscemo grafovsko invarianto, v kateri se obravnavana grafa locita. Preproste invariante so: stevilo tock in povezav, stevilo podgrafov izbrane vrste (npr. trikotniki), stopnje tock, dvodelnost, itn. Izomorfnost obicajno dokazemo tako, da konstruiramo izomorfizem. Vcasih si delo lahko poenostavimo, ce upo stevamo, da sta grafa izomorfna natanko tedaj, ko sta izomorfna njuna komplementarna grafa.
Zgled. Dokazimo, da sta grafa r in r2 s slike 9 izomorfna, grafa r3 in r4 s slike 10 pa ne.
u
u
4
v
v
v
v
5
6
7
8
u
u
5
v
v
v
v
2
4
u
u
2
Slika 9: Grafa r in
Rešitev: Graf r2 je dvodelen z razbitjem C = (vi, v2, v3, v4}, D = (v5, v6, v7,vg}. Hitro tudi opazimo, da mnoZici A = (u1,u3, U6,-Ug} in B = (u2, U4, U5, U7} tvorita dvodelno razbitje grafa r1. Izomorfizem ^ : r2 ^ r1 mora dvodelno razbitje seveda ohranjati. Poskusimo preslikati toCko v1 v U2. Ker je v5 edina toCka v mnozici D, ki toCki v1 ni sosednja, in toCka Ug edina toCka v mnozici B, ki toCki u2 ni sosednja, mora izomorfizem <p preslikati toCko v5 v toCko Ug.
Pri sliki toCke v2 imamo spet nekaj svobode, pa se odloCimo za toCko U4. S tem smo, enako kot zgoraj, doloCili sliko toCke v6, ki se mora preslikati v toCko U6. Nadaljujemo podobno in dobimo preslikavo ki se nam zdi primeren kandidat za izomorfizem:
x	Vi	V2	V3	V4	V5	V6	V7	Vg
^(x)	U2	U4	U5	U7	Ug	U6	U3	U1
Sedaj moramo preveriti, ali preslikava ^ povezave grafa r2 res preslika bijektivno na povezave grafa r1. Za vsak xy G E(r2) poglejmo sliko ^>(x)^>(y):
xy	V1V6	V1V7	V1V8	V2V5	V2V7	V2V8	V3V5	V3 V6	V3V8	V4V5	V4V6	V4V7
	U2U6	U2U3	U2U1	8 U 4 U	U4U3	U4U1	U5U8	U5 U6	U5U1	U7U8	U7U6	U7U3
V spodnji vrstiCi smo dobili natanko vse povezave grafa G1, kar pomeni, da je preslikava ^ res izomorfizem. Omenimo se, da je graf r1 prikazan kot 3-koCka Q3, graf r2 pa kot polni dvodelni graf K4,4 brez stirih neodvisnih povezav, K4,4 — 4K2.
Slika 10: Grafa r3 in r4.
Oglejmo si sedaj grafa r3 in r4. Vidimo, da graf r4 vsebuje Cikel dolzine 4, graf r3 pa ne. Podobno vsebuje graf r4 le dva Cikla dolzine 5, r3 pa mnogo veC. Grafa tako nista izomorfna. Graf r3 je izomorfen Petersenovemu grafu, graf r4 pa 5-strani prizmi C5DK2.	■
9.2 Avtomorfizmi grafov
Izomorfizmu grafa vase recemo tudi avtomorfizem grafa. Avtomorfizem grafa r je torej permutacija tock grafa, ki vsak par sosednjih vozlisc preslika v par sosednjih vozli sc. (Pozor: ce bi dovoljevali tudi neskoncne grafe, bi morali zahtevati tudi, da se par nesosednjih vozlisc preslika v par ne-sosednjih vozli sc.) Avtomorfizem grafa r lahko torej razumemo kot element simetricne grupe Sym(V(r)).
Ker je produkt dveh avtomorfizmov grafa ocitno spet avtomorfizem grafa (in ker je identiteta tudi avtomorfizem vsakega grafa), tvori mnozica vseh avtomorfizmov grafa podgrupo grupe Sym(V(r)). To mnozico oznacimo s simbolom Aut(r) in jo imenujemo grupa avtomorfizmov grafa r.
Dolocati grupo avtomorfizmov grafa je naceloma tezak problem, za nekatere posebne druzine grafov, pa je naloga dokaj lahka. Poglejmo si nekaj primerov:
•	Aut(Kn) = Sra;
•	Aut(Cn) = Dra;
•	Aut(Km ,n) = Sm ^ ce m = n;
•	Aut(Kn ,n) — (Sn ^ Sra) X S2.
Nekoliko zanimivejse je dolocanje grupe avtomorfizmov Petersenovega grafa.
Zgled. Dokazi, da je grupa avtomorfizmov Petersenovega grafa izomorfna grupi S5.
Rešitev: Najprej opazimo, da lahko Petersenov graf predstavimo takole:
V (Pet) = {{i, j} : i, j G Z5,i = j}, {i, j } - {s, t} ^ {i, j} n {s, t} = 0.
Sedaj je ocitno, da vsaka permutacija a G Sym(Z5) porodi avtomorfizem grafa a, ki je definiran s predpisom {i,j}<J = {iCT}. Na ta nacin smo grupo Sym(Zn) = S5 vlozili v grupo Aut(r). Dokazati moramo le se, da Petersenov graf ne premore drugih avtomorfizmov. To storimo z naslednjim premislekom.
Naj bo v = {0,1} G V (Pet) in G = Aut(Pet). Najprej opazimo, da S5 (in zato tudi Aut(Pet)) deluje tranzitivno na tockah Petersenovega grafa. Zato nam lema o orbiti in stabilizatorju pove
|G| = 10 ■ |Gv|.
Podobno vidimo, da Gv deluje tranzitivno na sosesčini {{2, 3}, {3,4}, {2,4}} vozlisča v, saj vozlisče u = {2,3} preslikamo v vozlisče {3,4} z avtomorfiz-mom a G Gv za a = (0)(1)(3)(2, 4) G S5 in v vozlisče {2, 4} z avtomorfizmov a za a = (0)(1)(2)(3,4). Zato je
|G| = 10 ■ |Gv| = 10|Gvu||uGv| = 10 ■ 3 ■ |Gvu|.
Poglejmo si sedaj orbito elementa z = {3,4} pri delovanju grupe Gvu. Ker je z sosed v, se lahko z elementom iz Gvu preslika zgolj v soseda v. Očitno se ne more preslikati v u, saj se tja preslika ze u sam. Po drugi stani pa avtomorfizem a G Gvu za a = (0)(1)(2, 3)(4) preslika z v tretjega soseda, {2,4}, vozlisča v. Zato je zGvu = {z, {2, 4}}, in zato
|G| = 30 ■ |Gvu| = 30 ■ |Gvuz||zGvu| = 60 ■ |Gvuz|.
Nazadnje poglejmo se orbito wGvuz vozlisča w = {1,2}. Ker je w sosed točke z, se z elementom iz Gvuz preslika bodisi v samega sebe bodisi v {0, 2}, ne pa tudi v tretjega soseda, u, točke z, saj se v u preslika ze u sam. Po drugi strani pa res obstaja permutačija a = (0,1)(2)(3)(4) G S5, za katero je a G Gvuz in je wa = {0, 2}. Zato je
|G| = 60 ■ |Gvuz | = 60 ■ |Gvuzw ||wGvuz | = 120 ■ |Gvuzw |.
Nazadnje pa premislimo se, da je Gvuzw trivialna grupa. Namreč poljuben avtomorfizem Petersenovega grafa, ki pribije točke u, v, z in w pribije tudi peto točko, t = {4, 5} petčikla uvzwt. Vsaka od preostalih petih točk pa je sosednja kaki izmed petih ze pribitih točk tega petčikla. Zato taksno točko element iz Gvuzw tudi pribije. S tem smo dokazali, da je |G| = 120 in zato
Aut(Pet) = S5.
10 Drevesa
V povezanem grafu med poljubnima dvema tockama obstaja vsaj ena pot. Grafu, v katerem med poljubnima dvema tockama obstaja natanko ena pot, recemo drevo.
Trditev 10.1 Za graf r so ekvivalentne naslednje trditve:
(1)	r je drevo;
(2)	r je povezan, ampak z odstranitvijo poljubne povezave postane nepovezan;
(3)	r je povezan in |E(r)| = |V(r)| - 1.
(4)	r ne vsebuje cikla in |E(r)| = |V(r)| - 1.
(5)	r je povezan in ne vsebuje cikla.
Dokaz: Dokaz poteka z indukcijo na stevilo tock. Trditev ocitno drzi za vse grafe na dveh tockah (taksna grafa sta samo dva, K2 in njegov komplement). Denimo, da trditev drzi za vse grafe na manj kot n tockah. Dokazimo, da tedaj velja tudi za graf r na n tockah.
(1)	^ (2): Denimo, da je r drevo. Tedaj je povezan po deficiji. Naj bo e = uv poljubna povezava grafa r. Tedaj je (u, v) edina pot med u in v. To pa pomeni, da v grafu r — e ni nobene poti, kar pomeni, da r ni povezan.
(2)	^ (3): Predpostavimo, daje r povezan, odstranitev poljubne povezave pa ga razbije. Dokazujemo enakost |E(r)| = |V(r)| — 1. Izberi povezavo e. Tedaj je r — e unija povezanih komponent X in Y (premisli, da sta povezani komponenti dve in ne morda tri ali vec). Grafa X in Y sta povezana, ce pa odstanimo kak sno povezavo, razpadeta (saj ce ne bi razpadla, ne bi ob odstranitvi te iste povezave razpadel niti graf r). Uporabimo indukcijo in dobimo |E(X)| = |V(X)| — 1 and |E(Y)| = |V(Y)| — 1. Tedaj
|E(r)| = |E (X )| + |E (Y )| + 1 = (| V (X )| — 1) + (|V (Y)| —1) + 1 = |V(r)| — 1.
(3)	^ (4): Predpostavljamo, da je r povezan in da zado sca pogoju |E(r) = |V(r)| — 1. Dokazujemo, da r nima ciklov. Pa recimo, da obstaja cikel C. Za vsak v G V (r) poiscemo prvo povezavo ev na kaki najkrajsi poti med v in C. Premislek pokaze, da je ev = eu za poljubni razlicni tocki u,v G V (r) \ V (C). Zato je
|E(r) > |E(C )| U |{ev : v G V (r) \ V (C )}| = V (r),
kar je protislovje.
(4)	^ (5): Predpostavljamo, da je r brez čiklov in da velja|E(r)| = | V(r)| — 1. Dokazati moramo, da je r povezan. Naj bodo X1,..., Xk komponente za povezanost in denimo, da je k > 2. Vsak izmed grafov Xi zadosča (5), zato po indukčijski predpostavki Xi zadosča tudi (4). Tedaj pa je |E(Xi)| = |V(Xi)| — 1. Po drugi strani:
kk |E(r)| = £ |E(Xi)| = £ |V(Xi)|— k.
i=1 i=1
Ker je |E(r)| = |V(r)| — 1, sledi k = 1, in r je povezan.
(5)	^ (1): Predpostavljamo, da je r povezan in brez čiklov. Dokazujemo, da obstaja med poljubnima točkama natanko ena pot. Zaradi povezan-oti obstaja vsaj ena pot. Ce bi bili dve, bi dobili čikel - protislovje. I
Posledica 10.2 Drevo z vsaj dvema točkama vsebuje dve tocki stopnje 1.
Dokaz: Naj bo r graf, v katerem ima vsaj |V(r)| — 1 točk stopnjo vsaj 2 (označimo mnozičo teh točk z U). Preostala točka ima stopnjo vsaj
1,	saj bi sičer tvorila komponentno za povezanost. Tedaj je
|E(r)| = 2(£ deg(v) + 1) > 1(|V(r)| ■ 2 +1) = |V(r)| +1.
veu
Pri tem smo pri prvi neenakosti uporabili lemo o rokovanju. Sedaj pa iz trditve 10.1 sledi, da r ni drevo, kar je protislovje	I
Opomba. Točki stopnje 1 rečemo tudi list grafa. Zgornja poslediča torej pravi, da ima drevo vsaj dva lista. Ce ima drevo natanko dva lista, potem se neenakost v dokazu zgornje trditve izide le, če ima vsaka druga točka stopno natanko 2. Ni se težko prepričati, da je povezan graf, ki ima dva lista, ostale točke pa imajo stopnjo
2,	izomorfen poti.
10.1 Vpeta drevesa
Vpet podgraf grafa r, ki je drevo, se imenuje vpeto drevo grafa r.
Trditev 10.3 Graf je povezan, ce in samo ce vsebuje vpeto drevo.
Dokaz: C e graf r vsebuje vpeto drevo, obstaja pot med poljubnima dvema tockama ze v drevesu. Zato je r povezan. Naj bo sedaj r povezan graf. Ce je r drevo, je trditev dokazana. Sicer obstaja povezava e, za katero je r — e povezan. Odstranimo e iz r in postopek nadaljujemo, dokler ne dobimo (vpetega) drevesa.	I
Povezan graf, ki ni drevo, ima vec kot eno vpeto drevo. Stevilo vpetih dreves v grafu r oznacimo s t (r).
Pri racunanju stevila t (r) je prirocno razsiriti nas horizont na druzino multigrafov. Za povezavo e multigrafa r na r — e oznacuje multigraf, ki ga dobimo iz r z odstranitvijo povezave e, r/e pa multigraf, ki ga dobimo iz r, ce povezavo e skrčimo, tj. identificiramo njeni krajisci, zanko, ki nastane iz e ob tako nastali novi tocki, pa odstranimo. Nasploh lahko v naslednjem izreku v multigrafih, ki nastopajo, bri semo vse zanke, ki se morebiti pojavijo.
Trditev 10.4 Naj bo e poljubna povezana multigrafa r. Tedaj velja
t (r) = t (r — e) + t (G/e).
Dokaz: Vpetih dreves multigrafa r, ki povezave e ne vsebujejo, je natanko toliko kot vpetih dreves multigrafa r — e. Po drugi strani pa iz vpetega drevesa multigrafa r, ki vsebuje povezavo e, s skrcitvijo te povezave dobimo vpeto drevo multigrafa r/e. Ta postopek nam ocitno da bijekcijo med vpetimi drevesi multigrafa r, ki vsebujejo povezavo e, z vpetimi drevesi multigrafa r/e.	I
opomba. Stevilo vpetih dreves pa lahko izracunamo tudi s pomocjo linearne algebre, natancneje, s pomocjo Laplaceove matrike grafa.
Definicija 10.5 Laplacova matrika L(T) (multi)grafa r je kvadratna matrika, katere stoplci in vrstice so indeksirane s točkami grafa, v presečišču vrstice u in stoplca v lezi negativno stevilo povezav med u in v, diagonalni element točke v pa je enak stopnji tocke v.
Trditev 10.6 Stevilo vpetih dreves (multi)grafa r je enako absolutni vrednosti determinante matrike, ki jo dobimo iz L(T) tako, da odstanimo poljubno vrstico in poljuben stolpec.
S pomocjo te trditve (in nekaj spretnosti pri racunanju determinant) lahko dokazemo tako imenovano Cayleyjevo formulo za stevilo vpetih dreves polnega grafa, ki pravi t(Kn) = nn-2.
11 Eulerjevi in hamiltonovi grafi
opomba. Ta razdelek v veliki meri sledi Cetrtemu poglavju knjige [3].
11.1	Eulerjevi grafi
Sprehod v grafu (ali multigrafu) je enostaven, Ce vsebuje vsako povezavo grafa najveC enkrat. Enostaven sprehod, je eulerjev, Ce vsebuje vse povezave grafa (vsako natanko enkrat). Multigraf je eulerjev, Ce vsebuje eulerjev obhod, torej sklenjen sprehod, ki vsebuje vsako povezavo multigrafa natanko enkrat. Eulerjevih multigrafov ni tezko prepoznati.
Izrek 11.1 Multigraf r brez izoliranih točk je eulerjev, če in samo ce je povezan in so vse njegove točke sode stopnje.
Dokaz: Naj bo r graf brez izoliranih toCk. Denimo, da je r eulerjev. Tedaj je oCitno povezan, saj vsaka toCka lezi na eulerjevem sprehodu. (Tu smo uporabili dejstvo, da r nima izoliranih toCk.) VsakiC, ko eulerjev sprehod obisCe kako toCko, porabi dve povezavi - eno za vstop v toCko, drugo za izhod iz nje. Ker eulerjev obhod pri vsaki toCki porabi vse povezave, mora biti stopnja vsake toCke soda.
Denimo sedaj, daje r povezan, vsaka njegova toCka pa ima sodo stopnjo. Naj bo W najdaljsi med enostavnimi obhodi v r in naj bo r' multigraf, ki ga dobimo iz r, Ce odstranimo vse povezave obhoda W. C e r ni eulerjev, potem r' premore kaksno povezavo. Po drugi strani ima vsaka toCka multigrafa r' sodo stopnjo, saj smo stopnjo toCke z odstranjevanjem povezavav iz W zmanjsali za sodo stevilo. Se veC, ker je r povezan, ima vsaj ena toCka na sprehodu W v grafu r' stopnjo veCjo ali enako 2. V tak s ni toCki lahko torej zaCnemo sprehod v grafu r', ki ga nadaljujemo poljubno ter konCamo sele, ko se vrnemo v zaCetno toCko (ker ima v grafu r' vsaka toCka sodo stopnjo, taksen sprehod resniCno slej ko prej zopet vrne v zaCetno toCko). C e ta novi sklenjeni sprehod vrinemo v sprehod W, dobimo sklenjeni sprehod v r, ki je dalj s i od W. To pa je protislovje.	I
11.2	Hamiltonovi grafi
Pot P v grafu r je hamiltonova, Ce velja V (P) = V (r). Cikel C v grafu r je hamiltonov, Ce velja V (C) = V (r). Hamiltonova pot in Cikel sta torej vpeta pot oziroma vpet Cikel. Graf je hamiltonov, Ce ima hamiltonov Cikel.
Znan ni noben preprost, hitro preverljiv potreben in hkrati zadosten pogoj za hamiltonost grafa. Preprost potreben pogoj je podan v naslednji trditvi. Pri njej je uporabljena oznaka Q(A) za stevilo povezanih komponent grafa A.
Trditev 11.2 Naj bo S C V (r) neprazna mnoZica točk grafa r. Ce je Q(r — S) > |S |, potem r nima hamiltonovega cikla.
Dokaz: Naj bodo r1,..., Tk povezane komponente grafa r — S in naj bo C = v0v2 ...vn-1v0 hamiltonov čikel grafa r. Dokazati moramo, da je |S| > k. Brez skode za splosnost lahko privzamemo, da vn-1 G S.
Za i = 1,... ,k naj bo ni največji indeks, za katerega je vni G V(ri). Točka vni je torej zadnja točka na čiklu C, ki se lezi v komponenti ri. Naslednja točka, vi+1, je element mnoziče S. Točke vni+1, vn2+1,..., vnk+1 so torej (paroma različni) elementi mnoziče S, in zato |S| > k.	I
Zgornji potrebni pogoj za hamiltonost grafa zal ni tudi zadostni, kot kaze primer Petersenovega grafa. V Petersenovem grafu Pet za vsako neprazno mnozičo S C V (Pet) velja Q(r — S) < |S |, vendar graf vseeno ni hamiltonov.
Dobrih zadostnih pogojev za hamiltonost grafa ni enostavno najti. Naved-imo jih nekaj.
Trditev 11.3 Naj bosta u in v taksni nesosednji točki grafa r, da velja deg(u) + deg(v) > |V(r)|. Ce je graf r+uv hamiltonov, potem je hamiltonov tudi graf r.
Dokaz: Naj bo n = |V(r)|. Denimo, da je graf r + uv hamiltonov. Potem obstaja hamiltonova pot uv1v2 ... vn-2v v grafu r. Naj bo U mnoziča indeksov sosed točke u ter V mnoziča indeksov sosed točke v v grafu r. Ce je za kak i G U velja i — 1 G V, tedaj je v0v1... vi-1 vn-1vn-2 ... viv0 hamiltonov čikel v grafu r. Predpostavimo torej lahko, da taksnega indeksa i ni. Z drugimi besedami, V C {0,1,..., n — 2} \ (U — 1), kjer smo z U — 1 označili mnozičo {i — 1 : i G U}. Od tod sledi neenakost deg(v) = |V| < n — 1 — |U| = n — 1 — deg(u), kar je v prostislovju z naso predpostavko o vsoti stopenj točk u in v.	I
Od tod z lahkoto izpeljemo naslednji poslediči.
Izrek 11.4 (Ore). Ce za vsak par nesosednjih točk u,v grafa r velja deg(u)+ deg(v) > |V (r)|, potem je graf r hamiltonov.
Izrek 11.5 (Dirač). Ce ima graf r vsaj 3 točke in velja č(r) > l^ff)!, potem je graf G hamiltonov.
12 Povezanost in Mengerjev izrek
opomba. Ta razdelek v veliki meri sledi petemu poglavju knjige [3].
Tocka v grafa r je prerezna točka, ce ima graf r — v vec komponent kot graf r. Podobno je povezava e G E (r) prerezna povezava, ce ima graf r — e vec komponent kot graf r. Prerezni povezavi pravimo tudi most.
Graf r je k-povezan, ce ima vsaj k + 1 tock, za vsako mnozico tock U C V (r), ki ima manj kot k tock, pa je graf G — U povezan. Ce je graf r k-povezan, je tudi £-povezan za vsako stevilo £ < k. Najvecje stevilo k, za katero je graf r k-povezan, imenujemo povezanost grafa r in ga oznacimo s
K(r).
•	^(cn,) = 2
•	«(Kn) = n — 1
•	K(Km,n) = min{m, n}.
•	Za vsak graf r je K(r) < č(G).
12.1 Mengerjev izrek
Vzemimo A, B C V (r). Poti v grafu r, ki se zacne v tocki iz A in konca v tocki iz B, pravimo (A, B)-pot. Mnozica S C V (r) je (A, B)-prerez v r, ce vsaka (A, B)-pot vsebuje kako tocko iz S. Ce (A, B)-prerez odstranimo iz grafa r, se preostanek mnozice A (ce ga je kaj) znajde v drugi povezani komponenti kot preostanek mnozice B. Vsak (A, B)-prerez vsebuje vse tocke iz A n B.
Izrek 12.1 (Menger). Naj bo r graf in A, B C V (r). Najvecje stevilo disjunktnih (A, B)-poti v r je enako najmanjši moci (A, B)-prereza v r.
Mnozica S loči tocki u, v G V (r), ce u in v lezita v razlicnih komponentah grafa r — S. Velikokrat srecamo Mengerjev izrek v naslednji obliki:
Posledica 12.2 Naj bosta u, v G V (r), u = v, nesosednji tocki grafa r. Potem je najvecje stevilo notranje disjunktnih (u, v)-poti v r enako naj-manjsi moci mnozice, ki loci tocki u in v.
Mengerjev izrek nam omogoca tudi drugacen pogled na k-povezanost.
Posledica 12.3 (Opis k-povezanih grafov). Naj bo r graf z vsaj k + 1 tockami. Graf r je k-povezan natanko tedaj, ko za vsak par razlicnih tock u, v G V (r) obstaja vsaj k notranje disjunktnih (u, v)-poti.
12.2 2-povezani grafi in bloki
Blok grafa r je maksimalen povezan podgraf brez prereznih toCk (t.j. povezan podgraf brez prereznih toCk, ki ni vsebovan v nobenem veCjem taksnem pod-grafu). Blok grafa je bodisi izolirana toCka bodisi prerezna povezava (skupaj s krajisCema) bodisi maksimalen 2-povezan podgraf.
Trditev 12.4 (Opis 2-povezanih grafov). Naj bo r graf z vsaj tremi točkami. Naslednje trditve so enakovredne:
1.	r je 2-povezan.
2.	r ima en sam blok.
3.	Vsak par točk grafa r lezi na skupnem ciklu (oziroma med vsakim parom točk grafa r obstaja par notranje disjunktnih poti).
4.	č(r) > 1 in vsak par povezav grafa r lezi na skupnem čiklu.
RazliCna bloka grafa imata skupno najveC eno toCko, ki mora biti prerezna toCka grafa. RazliCni povezavi e1,e2 grafa pripadata istemu bloku natanko tedaj, ko lezita na skupnem Ciklu.
Grafu r priredimo graf blokov B(r) takole: Naj bodo B1,..., Bk bloki grafa r in v1,..., vp prerezne toCke v r. Potem vzamemo
V (B(r)) = (Bi,...,Bfc ,vi,...,vp} in E (B(r)) = {^B, | v* G V (B,)} .
C e je graf r povezan, je B (r) drevo.
13 Ravninski grafi in Eulerjeva formula
Kot smo ze omenili v uvodu, grafe radi risemo v ravnini tako, da vozli sce grafa predstavimo kot tocko ravnine, povezo med vozliscema pa kot ravno (ali pa tudi krivo) crto s krajisci v tockah, ki ustrezata krajiscema povezave. Pri tem pazimo, da povezava (oziroma, natancneje, crta, ki ponazarja povezavo) ne seka same sebe in ne poteka skozi nobeno drugo vozlisce kot le svoje krajisce. Seveda ima lahko dani graf vec razlicnih risb.
Ce obstaja risba grafa, pri kateri se nobeni dve povezavi med seboj ne sekata (razen morda v svojih krajiscih), recemo, da je graf ravninski, tak s ni risbi pa ravniska risba grafa. Tako so, na primer, ravninski vsi cikli Cn, vse poti Pn, vsa drevesa, pa tudi polni grafi K3 in K4 ter polni dvodelni grafa K2,n, n G N. Kasneje pa bomo videli, da polni grafi Kn za n > 5 in polni dvodelni grafi Km,n za m,n > 3 niso ravninski.
Opomba. Formalno definicijo risbe in ravninskosti grafa lahko opisemo takole: Vložitev multigrafa r v metricni prostor S je dolocena z injektivno preslikavo f: V (r) ^ S, ki vsaki tocki multigrafa priredi tocko prostora S, in tako druzino zveznih preslikav f e : [0,1] ^ S (tu smo povezavo e predstavili z zaprtim intervalom [0,1]), da velja: f e(0) je slika enega, fe(1) pa slika drugega krajisca povezave e, fe|(o,i) je injektivna in njena slika ne vsebuje nobene tocke, ki bi bila slika tocke grafa ali pa del slike kake druge povezave grafa. Graf, ki premore vlozitev v ravnino, se imenuje ravninski graf.
Dokazati, daje neki graf ravninski, je naceloma enostavno - najti moramo njegovo ravninsko risbo. Precej tezje pa je dokazati, da graf ni ravninski, saj bi morali pregledati vse mozne njegove risbe in preveriti, da nobena ni ravninska. Ker je to seveda nemogoce, je za dokazovanje neravninskosti grafov potrebno razviti kaksne drugacne prijeme. Eden taksnih je Eulerjeva formula.
13.1 Eulerjeva formula
Zamislimo si ravninsko risbo ravninskega grafa r. Ce iz ravnine izrezemo vse crte in tocke, ki predstavljajo povezave in vozlisca grafa, dobimo nekaj med seboj locenih povezanih obmocij, ki jih imenujemo lica. Eno od teh obmocij je neomejeno in obdaja celotno risbo grafa, ostala obmocja pa so omejena. Mnozico vsej lic tako narisanega grafa r oznacimo z F (r).
Na prvi pogled ni videti nobenega razloga, zakaj bi stevilo lic grafa ne bilo odvisno od konkretne ravniske risbe le-tega. Zato je toliko presenetljivej sa naslednja trditev, iz katere med drugim sledi, da je stevilo lic ravninskega grafa neodvisno od konkretne ravninske risbe.
Izrek 13.1 (Eulerjeva formula) Naj bo r ravninski graf z mnozico vozličč V in mnozico povezav E. Naj bo F mnočica lic kake ravninske slike grafa r in Q mnozica komponent za povezanost grafa r. Tedaj velja naslednja enakost:
| V | —|E| + |F | = 1 + |Q|.
Zgornji izrek navadno dokazujemo z indukčijo na stevilo povezav grafa. Pri tem si pomagamo tudi s formulo o stevilu povezav v drevesu z n točkami. Podrobnosti dokaza bomo izpustili. Namesto tega raje izpeljimo naslednjo pomembno posledičo Eulerjeve formule.
Trditev 13.2 Naj bo r povezan ravninski graf z vsaj tremi točkami. Tedaj je
|e(r)| < 3|v(r)| — 6.
Dokaz: Izberimo kako ravninsko sliko grafa r in z F označimo mnozičo pripadajočih lič, z E pa mnozičo vseh usmerjenih povezav grafa r (tj. mnozičo vseh parov (u, v), u, v G V (r), za katere je u ~ v).
Ce rob liča prehodimo v smeri urinega kazalča, dobimo sklenjen sprehod v grafu, ki ga bomo imenovali kar usmerjeni rob lica. Za razliko od omejenih lič se domenimo, da je usmerjeni rob neomejenega liča obhod, ki ga dobimo, če robne povezave zunanjega liča prehodimo v smeri, ki je nasprotna urinemu kazalču. Opazimo, da vsaka usmerjena povezava lezi na natanko enem robu liča (namreč na robu tistega liča, ki lezi desno od nje, če gledamo v smeri usmeritve povezave). Hkrati pa vsak rob liča vsebuje vsako usmerjeno povezavo največ enkrat.
Stevilo usmerjenih povezav, ki jih vsebuje rob liča f G F, označimo z deg(f). Enostaven premislek pokaze, da iz deg(f) < 2 sledi, da je graf r izomorfen K1 ali K2, kar pa je v protislovju s predpostavko, daje |V (r)| > 3. Zato je deg(f) > 3 za vsak f G F.
Oglejmo si mnozičo parov M = {(e, f) : e G E, f G F, e lezi na robu f}. Elemente mnoziče M prestejmo na dva načina:
|M| = £ 1 = |E | = 2|E|.
eeE
Po drugi strani:
|M| = £ deg(f) > £ 3 = 3|F|. feF	/eF
Od tod sledi |F| < §|E|. Vstavimo to v enakost |F| =2 — |V| + |E|, ki sledi iz Eulerjeve fornule. Dobimo 2 — |V| + |E| < ||E|, od koder dobimo
1 |E| < |V| — 2. To neenakost se pomnozimo s 3 in dobimo, kar smo trdili.
■
Podobno kot zgornjo trditev lahko dokazemo tudi naslednje.
Trditev 13.3 Naj bo r povezan ravninski graf z vsaj štirimi točkami. Ce r ne vsebuje čikla dolzine 3, tedaj je
|e(r)| < 2|v(r)| — 4.
Iz zgornjih dveh rezultatov neposredno sledi naslednje.
Trditev 13.4 Grafa K5 in K3,3 nista ravninska.
Dokaz: Graf K5 ima 5 vozlisC in 10 povezav. Ce bi bil ravninski, bi veljalo 10 < 3 ■ 5 — 6, kar pa oCitno ni res. Zato graf K5 ni ravninski. Podobno, graf K3,3 ima 6 vozlisC in 9 povezav ter ne vsebuje Ciklov dolzine 3. Ce bi bil ravninski, bi veljalo 9 < 2 ■ 6 — 4. Ker to ni res, graf K3,3 ni ravninski.
13.2 Izreka Wagnerja in Kuratowskega
V	tem razdelku si bomo ogledali nekaj operaCij na grafih, ki ohranjajo lastnost "biti ravninski". Prva od takih operaCij je operaCija "podgraf". OCitno namreC velja naslednje:
Trditev 13.5 Ce je graf r ravninski, tedaj je ravniski tudi vsak njegov podgraf r'.
Naslednja operaCija, ki ohranja ravninskost, je operaCija subdivizije, ki jo bomo sedaj opisali. Naj bo e = u0v0 poljubna povezava grafa r. Z r' oznaCimo graf, ki ga dobimo iz r tako, da na sredi povezave e dodamo novo toCko (stopnje 2). (Formalno bi lahko r' definirali kot graf z mnoziCo toCk
V	(r) U {e}, kjer sta dve toCki u, v G V (r), uv = e, sosednji v r', Ce sta bili sosednji v r, "nova toCka" e je sosednja svojima kraji sCema u0 in v0 v grafu r, toCki u0 in v0 pa v grafu r' nista sosednji.) Grafu r' tedaj reCemo graf, dobljen iz r s subdivizijo povezave e. Vsakemu grafu, ki ga dobimo iz r z zaporednim subdividiranjem povezav, reCemo subdivizija grafa r. Ni se tezko prepriCati, da velja naslednje.
Trditev 13.6 Naj bo r' poljubna subdivizija grafa r. Tedaj je r ravninski, če in samo če je ravninski r'.
Ce zduzimo zgornji dve trditvi s Trdtivijo 13.4, ugotovimo, da r, ki vsebuje kak podgraf r', ki je subdivizija grafa K5 ali pa grafa K3,3, ni ravninski. Presenetljivo pa je, da je ta potrebni pogoj za ravninskost hkrati tudi zadostni. Velja namrec naslednji globok in netrivialen izrek, ki nosi ime poljskega matematika Kazimierza Kuratowskega.
Izrek 13.7 (Kuratowski) Graf r je ravninski, ce in samo ce noben od njegovih podgrafov ni subdivizija niti grafa K5 niti grafa K3,3.
Za konec definirajmo se tretjo operacijo, ki ohranja ravninskost. Naj bo r' graf, dobljen iz kakega podgrafa grafa r z odstranjevanjem in krcenjem povezav (na vsakem koraku lahko odstranimo dobljene zanke, vzporedne povezave pa zdruzimo v eno samo povezavo - tako ves cas ostajamo v razredu enostavnih grafov). Tedaj grafu r' recemo minor grafa r. Ni se tezko prepricati, da velja naslednje.
Trditev 13.8 Ce je graf r ravninski, tedaj je ravninski tudi vsak njegov minor r'.
S pomocjo Trditve 13.4 lahko zato sklenemo, da graf, ki premore kak minor, izomorfen grafu K5 ali grafu K3,3, ni ravninski. Podobno kot v primeru subdivizij, pa velja ta implikacija tudi v obratni smeri. Karakteri-zaciji ravninskih grafov, ki jo tako dobimo, recemo Wagnerjev izrek.
Izrek 13.9 (Wagner) Graf r je ravninski, ce in samo ce ne premore minorja, izomorfnega K5 ali K3,3.
14 Barvanja grafov
opomba. Ta razdelek v veliki meri sledi sedmemu poglavju knjige [3].
Preslikavi c: V (r) ^ {1,2,..., k} pravimo k-barvanje tock grafa r. Barvanje tock c je dobro (tudi pravilno), ce so sosednje tocke obarvane z ra-zlicnimi barvami, tj. u — v ^ c(u) = c(v). Najmanjse stevilo k, za katero obstaja dobro k-barvanje tock grafa r, imenujemo kromatično število (tudi barvnost) grafa G; oznaka x(r).
Podobno preslikavi c': E (r) ^ {1,2,..., k} pravimo k-barvanje povezav multigrafa brez zank r. Barvanje povezav c' je dobro (tudi pravilno), ce so povezave, ki imajo kako skupno krajisce, obarvane z razlicnimi barvami. Najmanjse stevilo k, za katero obstaja dobro k-barvanje povezav multigrafa brez zank r, imenujemo kromatični indeks multigrafa r; oznaka x'(G).
14.1 Barvanje točk
C e je r' C r, potem je x(r') < x(r). Naj bo w(r) velikost najvecjega polnega podgrafa grafa r (velikost maksimalne klike) in A(r) maksimalna stopnja kakega vozlisca v r. Tedaj velja w(r) < x(r) < A(r) + 1. Spodnja meja je ocitna, saj za pravilno barvanje tock polnega grafa na n tockah potrebujemo n barv, zgornjo mejo pa z lahkoto dokazemo, ce poskusimo tocke pobarvati kar po pozresni metodi.
Nekoliko tezje pa je dokazati, da je ta zgornja meja dosezena le pri lihih ciklih in polnih grafih. Prav to pravi Brooksov izrek.
Izrek 14.1 (Brooks). Naj bo r povezan graf. Ce r ni lih cikel in ni poln graf, potem je x(r) < A(r).
Dolocanje kromaticnega stevila konkretnega grafa je obicajno sestavljeno iz dveh delov: iskanja spodnje meje (pri preprostih nalogah najdemo pod-graf, za katerega poznamo kromaticno stevilo, npr. x(Kn) = n, x(Cn) = 2 za sode n in 3 za lihe n, x(r) < 2 natanko tedaj, ko je r dvodelen graf, itn.) in konstrukcije barvanja, ki dokaze, da je spodnjo mejo res moc doseci (veckrat si lahko pomagamo tudi z Brooksovim izrekom).
Vcasih si delo lahko poenostavimo z naslednjim znamenitim izrekom:
Izrek 14.2 (Izrek s tirih barv). Za vsak ravninski graf r je x(r) < 4.
Zgled. Poišči kromatično .število Petersenovega grafa Pet.
ReSitev: Ker Pet vsebuje čikel dolzine 5, je x(Pet) > x(C5) = 3. Ker je Pet kubičen graf, iz Brooksovega izreka dobimo x(Pet) < 3. Torej x(Pet) = 3.
14.2 Barvanje povezav
Tudi za barvanja povezav velja, da iz r' C r sledi x'(r) < x'(r). Na-jpomembnejsi izrek o barvanju povezav grafov je:
Izrek 14.3 (Vizing). Za vsak graf G velja A(r) < x'(r) < A(r) + 1.
Graf r je razreda 1, če je x'(r) = A(r), sičer je razreda 2. Ce je n sod, sta grafa Cn in razreda 1, za lihe n-je pa sta razreda 2. Pomembna druzina grafov razreda 1 so dvodelni grafi. Natančneje:
Izrek 14.4 (Konig). Za dvodelni multigraf r velja x'(r) = A(r).
Za multigrafe je kromatični indeks lahko večji od maksimalne stopnje točk plus ena.
Izrek 14.5 (Vizing; Shannon). Naj bo r multigraf brez zank, v katerem ne obstaja več kot ^ paroma vzporednih povezav (za grafe vzamemo ^ = 1). Potem je A(r) < x'(r) < min{A(r) + §A(r)}.
Literatura
[1]	V. Batagelj: Kombinatorika, samozalozba, Ljubljana, 1997.
[2]	V. Batagelj, S. Klavzar: DS2, algebra in teorija grafov, naloge, DM-FAS, Ljubljana, 1992.
[3]	M. Juvan, P. PotoCnik: Kombinatorika s teorijo grafov: primeri in rešene naloge, DMFAS, Ljubljana, 2000.
[4]	J. H. van Lint, R. M. Wilson: A Course in Combinatorics, Cam-bridge University Press, Cambridge, 1993.
[5]	D. Veljan: Kombinatorika s teorijom grafova, Skolska knjiga, Zagreb, 1989.
[6]	R. J. Wilson, J. J. Watkins: Uvod v teorijo grafov, DMFAS, Ljubljana, 1997.