Primož Potočnik Zapiski predavanj iž Algebre in Diskretne Matematike Ljubljana, marec 2011 Naslov: Zapiski predavanj iz Algebre in Diskretne Matematike 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 511.2(0.034.2) 519.172(0.034.2) POTOČNIK, Primoz, 1971 - Zapiski predavanj iz Algebre in Diskretne matematike [Elektronski vir] Primoz Potočnik. - 1. izd. - El. knjiga. - Ljubljana : samozal., 2011 Način dostopa (URL): http://www.fmf.uni-lj.si/~potocnik/Ucbeniki/ADM-Zapiski.pdf ISBN 978-961-93056-2-1 255520000 Izdano v samozalozbi marca 2011. Avtor si pridrzuje vse pravice. Kazalo 1 Izjave ............................... 1 1.1 Logične operacije..................... 2 1.2 Pravilnostne tabele sestavljenih izjav.......... 5 1.3 Tavtologije, protislovja in enakovrednost izjav..... 6 1.4 Izbrane oblike izjav.................... 8 1.5 Polni nabori logičnih operacij.............. 11 2 Sklepanje in dokazovanje v izjavnem računu.......... 12 2.1 Veljavni in neveljavni sklepi............... 12 2.2 Dokaz........................... 13 3 Predikati in kvantifikatorji........................................16 3.1 Izjavne sheme....................... 17 3.2 Interpretacije izjavnih shem............... 18 3.3 Osnovne enakovrednosti izjavnih shem......... 20 4 Osnovno o mnozicah....................... 23 4.1 Relacije vsebovanosti in enakosti............ 23 4.2 Operacije z mnozicami.................. 24 4.3 Presek in unija druzine mnozic............. 25 4.4 Intervali v R ....................... 25 4.5 Potencna mnozica.................... 26 4.6 Urejeni pari in kartezicni produkt............ 26 5 Relacije .............................. 28 5.1 Operacije na relacijah.................. 29 5.2 Lastnosti relacij ..........................................31 5.3 Ekvivalencna relacija in relacije urejenosti....... 32 5.4 Funkcije.......................... 33 6 Osnovno o grafih..................................................35 6.1 Definicija in osnovni pojmi ..............................35 6.2 Metricne lastnosti ........................................37 6.3 Nekatere družine grafov..................................38 7 Drevesa............................................................41 7.1 Vpeta drevesa ............................................42 8 Eulerjevi in hamiltonovi grafi....................................44 8.1 Eulerjevi grafi..............................................44 8.2 Hamiltonovi grafi..........................................44 9 Ravninski grafi in Eulerjeva formula............................47 9.1 Eulerjeva formula..........................................47 9.2 Izreka Wagnerja in Kuratowskega........................49 10 Barvanja grafov....................................................51 10.1 Barvanje toCk..............................................51 10.2 Barvanje povezav..........................................52 11 Algebrske strukture................................................53 11.1 Operacije ..................................................53 11.2 Algebrske strukture z eno operacijo ......................56 11.3 Algebrske strukture z dvema operacijama ..............57 12 Teorija stevil......................................................59 12.1 Delitelji in večkratniki....................................59 12.2 Prastevila..................................................60 12.3 Diofantske enačbe ........................................62 12.4 Razsirjeni Evklidov algoritem............................64 12.5 Modularna aritmetika ....................................66 12.6 Kolobar ostankov ..........................................67 12.7 Obrnljivi elementi v Zn..................................68 12.8 Eulerjeva funkcija ........................................70 12.9 Mali Fermatov izrek in Eulerjev izrek ..................70 12.10 Kriptografski sistem RSA................................72 13 Izbori ..............................................................75 13.1 Urejeni izbori s ponavljanjem............................76 13.2 Urejeni izbori brez ponavljanja..........................77 13.3 Neurejeni izbori brez ponavljanja........................78 13.4 Neurejeni izbori s ponavljanjem..........................79 13.5 Permutacije multimnozic ................................82 13.6 Binomski simboli in Pascalov trikotnik..................83 14 Razbitja mnozic in razčlenitve stevil............................88 14.1 Stirlingova stevila druge vrste............................88 14.2 Lahova stevila ............................................89 14.3 Stirlingova stevila prve vrste ............................91 14.4 Stevilo razbitij naravnega stevila........................92 15 Nacelo vkljucitev in izkljucitev ..................................94 15.1 Unija dveh mnozic ........................................94 15.2 Unija poljubno mnogo mnozic ............................94 16 Dirichletovo nacelo in sorodni izreki ............................96 16.1 Dirichletovo nacelo........................................96 16.2 Ramseyev izrek............................................97 Matematična logika Za strogo obravnavo matematicnih teorij naravni jeziki niso najprimernejsi. Zato smo matematiki zgradili svoje jezike, ki jim pravimo formalni matematični jeziki . S formalnimi matematicnimi jeziki se ukvarja veja matematike, ki ji pravimo matematična logika. Matematicna logika doloca poleg slovnice formalnega jezika tudi pravila sklepanja,, ki nam omogocajo iz ze dokazanih trditev izpeljevati nove trditve. 1 Izjave V logiki razumemo izjavo kot tisto kar neki (smiselen) povedni stavek trdi o objektih dane teorije. Poudariti velja, da lahko sicer razlicni stavki trdijo isto. Izjava je torej tisto, kar je vsem povednim stavkom z enakim "pomenom" skupnega. Vsaka izjava je bodisi pravilna bodisi nepravilna. Pravimo tudi, da vsaka izjava zavzame eno od dveh logičnih vrednosti: 1 ali 0. Pri tem simbol 1 predstavlja logicno vrednost "pravilno", simbol 0 pa logicno vrednost "nepravilno". Navedimo nekaj stavkov, ki so izjave: • Stevilo 5 je večje od .Števila 3. (pravilna izjava) • Vsaka zvezna funkcija je odvedljiva. (nepravilna izjava) • Ce je neko .Število večje ali enako drugemu, drugo pa večje ali enako prvemu, potem sta ti dve Števili enaki. (pravilna izjava) In se nekaj stavkov, ki niso izjave: • Koliko je 3 plus 5 ? (ni povedni stavek) • Sestej 3 in 5! (ni povedni stavek) • Zelena funkcija je čla na dopust. (nesmiselen stavek) 1.1 Logične operacije Iz izjav lahko tvorimo nove izjave s pomočjo logičnih operacij ali, kot jim tudi pravimo, logičnih veznikov oz. logičnih povezav. Na tak način dobimo sestavljene izjave. Naj bosta, na primer, A in B izjavi: A = "Sonce sije." B = "Pada dez." Vsaka od teh dveh izjav je sama po sebi bodisi pravilna bodisi nepravilna; odvisno od dejanskih vremenskih razmer v trenutku, ko sta izreceni. Iz njiju lahko sestavimo vec sestavljenih izjav: • A A B = "Sonce sije in pada dez." • A V B = "Sonce sije ali pada dez." • -B = "Ne pada dez." • A ^ -B = "Ce sonce sije, potem ne pada dez." Prva izjava je pravilna, ce in samo ce sta pravilni A in B hkrati. Druga je pravilna, ce in samo ce je vsaj ena od izjav A in B pravilna. Tretja je pravilna, ce in samo ce je B nepravilna. Za pravilnost cetrte izjave se v matematiki domenimo, da je pravilna v vsakem primeru, razen, ce je A pravilna, -B pa nepravilna, torej, ce sonce sije, hkrati pa ni res, da ne bi padal dez. Za sestavljene izjave je znacilno, da je njihova logicna vrednost odvisna le od logicnih vrednosti izjav, ki jih sestavljajo. Na kaksen nacin je logicna vrednost sestavljene izjave odvisna od logicnih vrednosti sestavljenih izjav, lahko povemo s pomocjo pravilnostne tabele. V pravilnostni tabeli na levi strani v vrsticah navedemo vse mozne nabore logicnih vrednosti sestavljajocih izjav (ce je izjav n, je taksnih naborov 2n), na desni strani pa v vsaki vrstici navedemo pripadajoco logicno vrednost sestavljene izjave. Nabor logicnih vrednosti sestavljajocih izjav imenujemo tudi določilo sestavljene izjave. Opisimo nekaj najpomembnejsih logicnih operacij in pri vsaki navedimo njeno pravilnostno tabelo. Negacija (oznaka: -). Negacija je enomestna operacija, ki dano izjavo spremeni v njej nasprotno izjavo. Izjava -A je torej pravilna, ce in samo ce je izjava A nepravilna. Pravilnostna tabela za negacijo: Logične operacije 3 A -A 0 1 1 0 Konjunkcija (oznaka: A). Konjunkcija izjav A in B je pravilna izjava, ce in samo ce sta pravilni obe izjavi A in B. Oznacimo jo z A A B in preberemo "A in B". Pravilnostna tabela za konjunkcijo: A B A A B 0 0 0 0 1 0 1 0 0 1 1 1 Disjunkcija (oznaka: V). Disjunkcija izjav A ce in samo ce je pravilna vsaj ena od izjav A in B obe). Oznacimo jo z A V B in preberemo "A ali B" disjunkcijo: A B A V B 0 0 0 0 1 1 1 0 1 1 1 1 Ekvivalenca (oznaka: Ekvivalenca dveh izjav A in B je izjava, ki je pravilna natanko tedaj, ko imata izjavi A in B enaki logicni vrednosti. Pravilnostna tabela za ekvivalenco: A B A ^ B 0 0 1 0 1 0 1 0 0 1 1 1 Implikacija (oznaka: Implikacija je zelo pomembna logicna operacija, na kateri temelji logicno sklepanje. Ce sta A in B poljubni izjavi, potem je izjava A ^ B pravilna v vseh primerih, razen v primeru, ko je A pravilna, B pa nepravilna. Pravilnostna tabela za implikacijo je torej: A B A ^ B 0 0 1 0 1 1 1 0 0 1 1 1 in B je pravilna izjava, (lahko sta pravilni tudi . Pravilnostna tabela za 4 izjave Izjavo A ^ B preberemo tudi "Iz A sledi B," ali pa "Ce A, potem B." Poleg zgornjih logicnih operacij, ki jih najpogosteje uporabljamo v matematiki, so pomembne se tri, prva zaradi uporabe v racunalnistvu, drugi dve pa zaradi pomena v logiki. Ekskluzivna disjunkcija (oznaka: V). Ekskluzivna disjunkcija dveh izjav A in B je pravilna izjava natanko tedaj, ko imata A in B razlicni logicni vrednosti, torej tedaj, ko je pravilna natanko ena od izjav A in B. V slovenskem jeziku bi ekskluzivno disjunkcijo A V B prebrali "bodisi A bodisi B." Ta logicna operacija je pogosto uporabljana v racunalnistvu, kjer jo oznacujejo tudi z "Xor". Pravilnostna tabela za ekskluzivno disjunkcijo: A B A v B 0 0 0 0 1 1 1 0 1 1 1 0 Koliko razlicnih dvomestnih logicnih operacij pa sploh obstaja? Dve logicni operaciji sta različni natanko tedaj, ko imata razlicna stolpca logicnih vrednosti. Stolpec vsebuje 4 mesta in na vsakem mestu lahko izbiramo med dvema logicnima vrednostma. Skupaj imamo torej 24 = 16 dvomestnih logicnih operacij. Pravilnostne tabele, oznake in imena dvomestnih logicnih operacij smo zdruzili v naslednji tabeli. pravilnostne tabele sestavljenih izjav 5 p 0 0 1 1 q 0 1 0 1 0 0 0 0 p0q protislovje 0 0 0 1 p A q konjunkcija 0 0 1 0 -(p ^ q) negacija implikacije 0 0 1 1 P projekcija na prvi faktor 0 1 0 0 —(q ^ p) negacija obrnjene implikacije 0 1 0 1 q projekcija na drugi faktor 0 1 1 0 p V q ekskluzivna disjunkcija 0 1 1 1 p V q disjunkcija 1 0 0 0 p i q Lukasiewicz-Pierceova operacija 1 0 0 1 p ^ q ekvivalenca 1 0 1 0 —q negacija projekcije na drugi faktor 1 0 1 1 q ^ p implikacija 1 1 0 0 —p negacija projekcije na prvi faktor 1 1 0 1 p ^ q implikacija 1 1 1 0 p t q Shefferjeva operacija 1 1 1 1 p1q tavtologija 1.2 Pravilnostne tabele sestavljenih izjav Pravilnostne tabele smo v prejsnjem razdelku uporabili za definicijo nekaterih logicnih operacij. Tako definirane logicne operacije lahko, skupaj z oklepaji, uporabimo za gradnjo novih sestavljenih izjav. Na primer, iz izjav A, B in C lahko tvorimo sestavljeno izjavo (A V B) ^ C. Pravilnostno tabelo za tako sestavljeno izjavo dobimo s postopnim ra-cunanjem logicnih vrednosti sestavljajocih izjav (ob upostevanju vrstnega reda, ki ga dolocajo oklepaji). A B C (A V B) ^ C 1 1 1 1 1 1 1 1 0 1 0 0 1 0 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 1 0 1 0 1 0 0 0 0 1 0 1 1 0 0 0 0 1 0 Naboru logicnih vrednosti sestavljajocih izjav A, B in C (recimo A = 1, B = 0, C = 1), recemo tudi določilo sestavljene izjave. Vsaka vrstica zgornje tabele tako predstavlja eno dolocilo. Da zmanjsamo stevilo potrebnih oklepajev, podobno kot pri obicajnih racunskih operacijah (+, —, x, : ) uvedemo pravila prednosti logicnih operacij. Najtesneje naj izjave veze operacija —, nato pa po vrsti: A, t, -i, V, v Za konec se se dogovorimo, da bomo sestavljene izjave oznacevali z velikimi tiskanimi crkami: A, B, C,..., izjave, ki niso sestavljene, pa z malimi tiskanimi crkami p, q, r,.... Ce je neka izjava A sestavljena iz nesestavljenih (atomarnih) izjav p, q, r,..., bomo to poudarili z zapisom A = A(p, q, r,...). 1.3 Tavtologije, protislovja in enakovrednost izjav Sestavljeni izjavi, ki je pravilna pri vsakem naboru logicnih vrednosti ses-tavljajocih izjav, pravimo tavtologija. Kadar je neka izjava A tavtologija, zapisemo h A. Dve (sestavljeni) izjavi A in B sta enakovredni natanko tedaj, ko je izjava A ^ B tavtologija: (A ~ B) natanko tedaj, ko h A ^ B. Ker je izjava A ^ B pravilna natanko tedaj, ko imata A in B isto logicno vrednost, je zgornja zahteva ekvivalentna zahtevi, da imata A in B pri vsakem naboru logicnih vrednosti sestavljajocih atomarnih izjav (dolocilu) isto logicno vrednost. Ali sta dve izjavi enakovredni ali ne, torej lahko ugotovimo iz pravilnos-tnih tabel obeh izjav. Zgled. Ali sta izjavi p q in —q ^ —p enakovredni? Sestavimo njuni pravilnostni tebeli: p q p ^ q —q —p 0 0 1 1 1 1 0 1 1 0 1 1 1 0 0 1 0 0 1 1 1 0 1 0 Tavtologije, protislovja in enakovrednost ižjav 7 Vidimo, da sta stolpca z logicnimi vrednostmi pri obeh izjavah enaka, zato lahko zatrdimo, da sta izjavi enakovredni. ■ Podobno definiramo logicno posledico dane izjave. Namrec, izjava B je logična posledica izjave A, ce in samo ce je izjava A ^ B tavtologija: (A ^ B) natanko tedaj, ko = A ^ B. Zapisimo nekaj pomembnih parov enakovrednih izjav: ...... pravilo dvakratne negacije ...... idempotentnost konjunkcije ...... idempotentnost disjunkcije ...... komutativnost konjunkcije ...... komutativnost disjunkcije ...... asociativnost konjunkcije ...... asociativnost disjunkcije r) ...... distributivnost r) ...... distributivnost ...... 1. de Morganov zakon ...... 2. de Morganov zakon ...... definicija implikacije ...... pravilo kontrapozicije ...... komutativnost ekvivalence ...... neobcutljivost ekvivalence na negacijo ...... pravilo negacije ekvivalence ...... 1. absorbcijsko pravilo ...... 2. absorbcijsko pravilo ...... konjunkcija s protislovjem ...... konjunkcija s tavtologijo ...... disjunkcija s protislovjem ...... disjunkcija s tavtologijo ...... zakon izkljucene tretje moznosti ...... zakon protislovja -(-p) rsj p p A p rsj p p V p rsj p p A q rsj q A p p V q rsj q V p (p A q) A r rsj p A (q A r) (p V q) V r rsj p V (q V r) (p V q) A r rsj (p A r) V (i (p A q) V r rsj (p V r) A (i -(p A q) rsj -p V -q -(p V q) rsj -p A -q p ^ q rsj -p V q p ^ q rsj -q ^ -p p ^ q rsj q ^ p p ^ q rsj -p ^ -q -(p ^ q) rsj p ^ -q p V (p A q) rsj p p A (p V q) rsj p p A 0 rsj 0 p A 1 rsj p p V 0 rsj p p V 1 rsj 1 p V -p rsj 1 p A -p rsj 0 S pomocjo osnovnih logicnih enakovrednosti lahko dokazujemo tudi nekoliko zapletenejse enakovrednosti. Spodnji zgled pokaze, kako lahko relativno zapleteno izjavo poenostavimo v preprostejso, njej enakovredno izjavo. Zgled. Dokači enakovrednost izjave (A ^ B) ^ (B ^ C) z izjavo B ^ C. Z zaporedno uporabo enakovrednosti iz zgornje tabele dobimo verigo naslednjih enakovrednosti: 8 izjave —I (A ^ B) ^ (B ^ C) (-A V B) ^ (-B V C) -(-A V B) V (-B V C) (a A -b) V (-B V C) ((A A -B) V -B) V C definicija implikacije definicija implikacije 2. de Morganov zakon asociativnost disjunkcije 1. asimilacijsko pravilo definicija implikacije. BC BC 1.4 Izbrane oblike izjav V prejsnjem razdelku smo videli, kako dani izjavi priredimo pravilnostno tabelo. Kaj pa ce pravilnostno tabelo imamo, pa bi radi poiskali primerno sestavljeno izjavo? Na primer, radi bi nasli izjavo A, sestavljeno iz atomarnih izjav pi,p2 in p3, katere logicna vrednost je odvisna od logicnih vrednosti izjav p1,p2 in p3 takole: V nadaljevanju bomo opisali dva postopka za resevanje tovrstnih nalog. Izbrana disjunktivna oblika izjave Vzemimo poljubno dolocilo P (nabor logicnih vrednosti izjav p1,p2 in p3) in sestavimo izjavo Pi P2 P3 A 0 0 0 1 0 0 10 0 10 0 0 110 10 0 1 10 10 110 1 1111 qi A q2 A y, • R(x, y, z) = tocka x lezi na daljici s krajisci v tockah y in z. Stevilu logicnih spremenljivk, ki slediju danemu predikatu, recemo mest-nost predikata. Zgornja predikata P in Q sta tako enomestna, predikat V je dvomesten, predikat R pa celo tromesten. Izjavne formule lahko s pomocjo logicnih operacij (veznikov) zdruzujemo v nove izjavne formule. Na primer, izjavni formuli "P(x) = x je zenskega spola" in "T(x) = x je lepa" lahko zdruzimo v izjavne formule P(x) A T(x), P(x) ^ T(x), —P(x) in tako dalje. 3.1 Izjavne sheme Oglejmo si poblize izjavno formulo VxP (Sokrat, x), (S) V njej nastopa vec raznorodnih znakov: predikat P, logicna spremenljivka x, konstanta Sokrat, kvantifikator V in oklepaji ter zaklepaji. Brz ko se domenimo, katere objekte lahko oznacujejo logicne spremenljivke, kateri konkretni objekt imamo v mislih, ko govorimo o Sokratu, in katero konkretno relacijo med objekti oznacuje predikat P, nam zgornja formula preide v izjavo. Na primer, ce se domenimo, da logicne spremenljivke oznacujejo poljubne anticne filozofe, da predikat P(x,y) pomeni "x je pametnejsi od y", konstanta Sokrat pa oznacuje dobro znanega filozofa iz Aten, rojenega leta 470 pr. n. st., potem zgornja formula preide v trditev: Sokrat je pametnejsi od vseh antičnih filozofov. Zgornjemu dogovoru o pomenu posameznih sestavnih delov formule (S) pravimo interpretacija, sami formuli pred tem dogovorom pa izjavna shema. Izjavna shema je torej zapis, ki ima obliko izjave, pri katerem pa kontekst in pomeni oznak za predikate in konstante se niso doloceni. Preden si ogledamo nekaj zgledov izjavnih shem in njihovih interpretacij, se pomudimo se pri rabi kvantifikatorjev in logicnih spremenljivk. Par oklepajev, ki sledi kvantifikatorju, doloca doseg kvantifikatorja. Vsak kvan-tifikator veze le tiste pojavitve pripadajoce logicne spremenljivke, ki lezijo znotraj dosega kvantifikatorja. Pojavitve logicne spremenljivke, ki niso vezane s kvantifikatorjem, pravimo, da so proste. Tako v formuli (**) kvan-tifikator 3 veze obe pojavitvi spremenljivke x, zato prostih pojavitev spremenljivk ni vec. Ce pa bi namesto (**) pisali 3x(P(x)) A R(x), bi druga pojavitev spremenljivke x ostala prosta. Zato zgornja formula ni izjavna shema, saj prostih pojavitev logicnih spremenljivk v izjavni shemi ne sme biti. Vcasih par oklepajev za kvantifikatorjem v zapisu izjavne sheme tudi izpustimo. V tem primeru za doseg kvantifikatorja vzamemo najkrajsi mozni niz znakov, ki kvantifikatorju sledijo, za katerega ima izjavna shema se smisel. Na primer, ce pisemo VxP(x) A R(x), v resnici mislimo Vx(P(x)) A R(x). 3.2 Interpretacije izjavnih shem Vrnimo se sedaj k interpretacijam izjavnih shem. Formalno lahko interpretacijo definiramo kot par (U, ^>), kjer je U poljubna mnozica, ki ji recemo področje pogovora, ^ pa preslikava, ki konstante formalnega jezika slika v objekte s podrocja pogovora, n-mestne predikate pa v n-mestne relacije med objekti podrocja pogovora. Pri interpretaciji dane sheme moramo torej podati tri stvari: • podrocje pogovora, tj. mnozico objektov, od koder bomo jemali nase logicne konstante in vrednosti logicni spremenljivk; • pomen vsakega predikata, ki nastopa v shemi, pri cemer enomestnemu predikatu priredimo lastnost, smiselno za objekte s podrocja pogovora, dvomestnemu predikatu relacijo med objekti podrocja pogovora itd.; • pomene konstant, ki nastopajo v shemi, pri cemer vsaki konstanti priredimo en sam objekt podrocja pogovora. Ko je interpretacija izjavne sheme dolocena, lahko ugotavljamo, ali preide v pravilno ali nepravilno izjavo. Pri tem se drzimo pravila, ki pravi, da je izjava VxP (x) pravilna, ce in samo ce je izjava P (a) pravilna za prav vsak objekt a G U, izjava 3xP(x) pravilna, ce in samo ce obstaja kak objekt a G U, za katerega je izjava P (a) pravilna. Interpretacije izjavnih shem 19 Zgled. Poiscimo nekaj interpretacij izjavne sheme VyžlxP(x,y). Pri prvi interpretaciji bomo za podrocje pogovora vzeli mnozico vseh realnih stevil, predikat P naj preide v relacijo "biti manjsi", torej P(x,y) = x < y. Pri tej interpretaciji zgornja izjavna shema preide v pravilen stavek, ki trdi, da za vsako realno stevilo obstaja neko drugo realno stevilo, ki je od prvega manjse. Druga interpretacija naj bo enaka prvi, le da za podrocje pogovora vzamemo mnozico naravnih stevil namesto mnozice realnih stevil. Pri tej interpretaciji izjavna shema preide v nepravilno izjavo, saj obstaja naravno stevilo (namrec stevilo 1), za katerega ni prav nobenega strogo manjsega naravnega stevila. Tretja dobro znana interpretacija zgornje izjavne sheme se nanasa na neko izbrano funkcijo f: R ^ R in tocko a G R. Podrocje pogovora naj bo mnozica pozitivnih realnih stevil, predikat P(5, e) pa naj pomeni "Za vsako realno stevilo x, ki je od stevila a oddaljeno za manj kot 5, velja, da je vrednost f (x) oddaljena od vrednosti f (a) za manj kot e." Kot vemo, je izjava, ki jo dobimo iz sheme Vežl5P(5, e) pri tej interpretaciji, pravilna, ce in samo ce je funkcija f zvezna v tocki a. ■ Kot vidimo, lahko posamezna izjavna shema v neki interpretaciji preide v pravilno izjavo, v kaki drugi interpretaciji pa v nepravilno izjavo. Za izjavno shemo S, ki preide v pravilno izjavo pri prav vsaki interpretaciji, recemo, da je splošno veljavna. Pri tem pi semo h S. C e zelimo torej dokazati, da kaka izjavna shema ni splos no veljavna, moramo najti interpretacijo, pri kateri preide v nepravilno izjavo. Taksni interpretaciji recemo protiprimer za dano izjavno shemo. Zgled. S protiprimerom dokazi, da izjavna shema VxVy(P(x, y) ^ P(y, x)) ni splosno veljavna. Podati moramo interpretacijo, pri kateri zgornja shema preide v nepravilno trditev. Za podrocje pogovora vzemimo, na primer, mnozico naravnih stevil, predikat P(x,y) pa interpretirajmo kot "x < y", oziroma v sloven scini, "stevilo x je manjse ali enako stevilu y". Tedaj shema preide v trditev, ki trdi, da za poljubni naravni stevili x in y, za kateri je x < y, velja tudi y < x. Ta trditev je ocitno napacna, saj za x = 2 in y = 3 velja x < y, vendar ne velja y < x. ■ 3.3 Osnovne enakovrednosti izjavnih shem Ce za kaki izjavni shemi S in T velja = S ^ T, recemo, da sta enakovredni, in pisemo S ~ T. Podobno, ce velja = S ^ T, recemo, da je shema T logicna posledica sheme S, in pisemo S ^ T. Nastejmo nekaj enakovrednsti in logicnih posledic izjavnih shem. Zgornje formule nekoliko pokomentirajmo: Formuli (1) in (2) nekoliko spominjata na deMorganova zakona in pojasnita, kako znak za negacijo nesemo preko kvantifikatorja. Premislimo, kdaj bo (pri poljubni interpretaciji) izjava -VxP(x) pravilna. Natanko tedaj, ko bo izjava VxP(x) nepravilna. To pa se zgodil, ce in samo ce najdemo kak objekt a s podrocja pogovora, za katerega je P (a) nepravilna izjava (saj bi v nasprotnem veljalo P (a) za prav vse objekte, in zato tudi VxP (x)). To pa pomeni, da je izjava -P(a) za taksen objekt a pravilna, kar po drugi strani pomeni, da je pravilna tudi izjava žte-P(x). Podobno se lahko prepricamo v veljavnost tocke (2). Formuli (3) in (4) nista kdo ve kako zanimivi, saj pravita le, da je vseeno ali recemo "za vsak x in za vsak y" ali "za vsak y in za vsak x". V slovescini ti dve besedni zvezi navadno poenostavimo kar v "za vsaka x in y". Tudi simbolni zapis ponavadi poenostavimo in pisemo Vx, y : P(x, y) (v zapis smo dodali locilo ":", da nakazemo, kje smo prenehali nastevati logicne spremenljivke, ki so "kvantificirane". Mnogo zanimivejsa je formula (5). Poglejmo, kaj (pri poljubni interpretaciji) pravi leva stran formule, 3xVyP(x,y). Ce naj bo to pravilna trditev, potem mora na podrocju pogovora obstajati nek objekt a, za katerega -VxP (x) ~ 3x-P (x) -3xP (x) ~ Vx-P (x) 3x3yP (x,y) ~ 3y3xP (x,y) VxVyP (x, y) ~ VyVxP (x, y) 3xVyP (x, y) ^ Vy3xP (x, y) Vx(P(x) A Q(x)) ~ VxP(x) A VxQ(x) 3x(P(x) V Q(x)) ~ 3xP(x) V 3xQ(x) (1) (2) (3) (4) (5) (6) (7) Osnovne enakovrednosti izjavnih shem 21 pri poljubnem drugem objektu y velja P (a, y). To pa med drugim pomeni, da lahko za poljuben objekt y najdemo objekt x (namrec kar objekt x = a), za katega velja P (a, y). To pa z znaki lahko zapisemo kot Vy3xP (x,y). Ta premislek pokaze, da pri poljubni interpretaciji iz trditve 3xVyP(x, y) sledi trditev Vy3xP(x,y), kar smo tudi zeleli pokazati. Na tem mestu se pojavi naravno vprasanje, ali velja tudi obratna implikacija: ali pri poljubni interpretaciji iz Vy3xP(x,y) sledi 3xVyP(x,y). Odgovor je negativen, kot smo v resnici videli ze v enem od prejsnih zgledov. Namrec, ce za podrocje pogovora vzamemo mnozico naravnih stevil, za predikat P(x, y) pa relacijo y < x, tedaj je trditev Vy3xP(x, y) pravilna (saj pravi, da za vsako naravno stevilo obstaja neko drugo, ki je od njega vecje), trditev 3xVyP(x,y) pa nepravilna (saj pravi, da obstaja neko naravno stevilo, ki je vecje od vsakega drugega naravnega stevila). Nazadnji si oglejmo s e formuli (6) in (7). Premislimo, kaj v resnici (pri poljubni interpretaciji) trdi izjava Vx(P(x) A Q(x)). Pravi, da za vsak objekt a s podrocja pogovora velja tako P(a) A Q(a), in zato, seveda tako P (a) kot Q(a). To pa pomeni, da velja tako VxP (x) kot VxQ(x), in zato tudi VxP(x) A VxQ(x). S e lazje se prepricamo, da iz VxP(x) A VxQ(x) sledi Vx(P(x) A Q(x)), in s tem, da sta ti dve izjavni shemi enakovredni. V pravilnost formule (7) se prepricamo na podoben nacin. Pri tem naj poudarimo, da sorodni shemi 3x(P(x) A Q(x)) in 3xP(x) A 3xQ(x) nista enakovredni, saj prva trdi, da lahko najdemo objekt a, za katerega velja tako P (a) kot Q(a), medtem ko druga pravi le, da lahko najdemo nek objekt, recimo a, za katerega velja P (a), in morda nek drug objekt, recimo b, za katerega velja Q(b). Ti dve izjavi pa vsaj pri kaksni interpretaciji ocitno nista enakovredni (poisci kako tako interpretacijo!). Ni pa tezko videti, da velja 3x(P(x) A Q(x)) ^ 3xP(x) A 3xQ(x). Podobno vidimo, da nista enakovredni niti shemi Vx(P(x) VQ(x)) in VxP(x) V VxQ(x), da pa velja VxP(x) V VxQ(x) ^ Vx(P(x) V Q(x)). Za konec se domenimo se naslednje: Ce je A poljubna mnozica s podrocja pogovora in P poljuben predikat, potem smemo zapis Vx(x G A ^ P(x)) skraj s ati in pisati (Vx G A)P(x) in brati: "Za vsak x iz A velja P(x)". Podobno skrajsamo zapis 3x(x G A ^ P(x)) v (3x G A)P(x) in beremo: "Obstaja x iz A, za katerega velja P(x)". Premisli, da v teh skrajsanih zapisih deMorganova zakona preideta v —(Vx G A)P(x) ~ (3x G A)—P(x) in (3x G A)P(x) ~ (Vx G A)—P(x). Množice in relacije 4 Osnovno o množicah 4.1 Relacije vsebovanosti in enakosti Za nas e potrebe mnozica pomeni skupino (zbirko, dručino, nabor,...) nekih objektov. Ce mnozica A vsebuje objekt x, pravimo, daje x element mnozice A in zapi semo x G A. Dve mnozici sta enaki natanko tedaj, ko vsebujeta iste elemente. To zapisemo takole: A = B = Vx(x G A ^ x G B). C e mnozica A vsebuje vse elemente mnozice B (in morda se kaksnega za povrh), pravimo, da je B podmnozica mnozice A in to zapi semo kot B C A: B C A = Vx(x G B ^ x G A). Mnozici A in B sta torej enaki natanko tedaj, ko velja tako A C B kot B C A. S simboli to zapisemo kot VAVB(A = B ^ A C B A B C A). Končno mnozico lahko dolocimo tako, da nastejemo vse njene elemente. Na primer, A := {2,3, 5, 7} ali X := {Sonce, Zemlja, Mesec}. V splosnem mnozice podamo tako, da podamo pogoj za pripadnost. Na primer, P := {x | x je naravno stevilo, deljivo le z 1 in samim seboj}. 4.2 Operacije z mnoZicami Za dani dve mnozici A in B lahko definiramo njuno unijo in presek: A U B = {x | x G A V x G B} , A n B = {x | x G A A x G B}. Ce mnozici A in B nimata nobenega skupnega elementa, je njun presek mnozica, ki ne vsebuje nobenega elementa. Taksni mnozici pravimo prazna mnozica in jo oznacimo s simbolom 0. Za vsako mnozico A velja 0 C A, A U 0 = A in A n0 = 0. Poleg operacij unije in preseka omenimo se operaciji razlike in simetrične razlike mnozic A - B = {x | x G A A x G B} , A © B = (A U B) - (A n B). Mnogokrat je udobno vnaprej izbrati mnozico vseh objektov, o katerih zelimo govoriti. Taksni mnozici recemo univerzalna množica in jo oznacimo z U. Vse ostale mnozice so tedaj podmnozice mnozice U. S pomocjo univerzalne mnozice definiramo operacijo komplementa. Komplement mnozice A vsebuje natanko tiste elemente univerzalne mnozice, ki jih A ne vsebuje: A = {x | x G A}. Navedimo nekaj zanimivih lastnosti zgoraj definiranih operacij: A n B = B n A komutativnost preseka A U B = B U A komutativnost unije (A n B) n C = A n (B n C) asociativnost preseka (A U B) U C = A U (B U C) asociativnost unije A n (B U C) = (A n B) U (A n C) distributivnost preseka A U (B n C) = (A U B) n (A U C) distributivnost unije (A n B) = A U B 1. de Morganov zakon (A U B) = A n B 2. de Morganov zakon A n (A U B) = A 1. absorbcijsko pravilo A U (A n B) = A 2. absorbcijsko pravilo A n A = A idempotentnost preseka A U A = A idempotentnost unije A n 0 = 0 presek s prazno mnozico A U 0 = A unija s prazno mnozico Presek in unija druZine mnoZic 25 4.3 Presek in unija druZine mnoZic Poleg preseka in unije dveh mnozic v matematiki pogosto uporabljamo presek in unijo družine mnozic. Naj bo D mnozica, katere elementi so mnozice (taks ni mnozici ponavadi recemo druzina mnozic. Tedaj unijo druzine D definiramo kot mnozico vseh tistih objektov, ki se pojavijo v vsaj eni od mnozic iz D: U D = y A = {x | 3A(A G D A x G A)}. AeD Presek druzine D pa definiramo kot mnozico vseh tistih objektov, ki so vsebovani v prav vsaki mnozici iz druzine D: p| D = f A = {x | VA(A gD4 x G A)}. AeD Zgled. Naj bo D = {{1,2, 3}, {2,3,4}, {3,4, 5}}. Tedaj je f D = {3} in U D = {1, 2, 3, 4, 5}. Dalje, za naravno stevilo n definirajmo An = {x | x G N A x > n}. Tedaj je f An = 0 in U An = N. n€N n€N 4.4 Intervali v R V matematicni analizi igrajo pomembno vlogo mnozice realnih stevil, ki lezijo med dvema predpisanima realnima steviloma. Tak snim mnozicam pravimo intervali. Definiramo vec vrst intervalov, ki se locijo glede na to, ali vsebujejo svoja mejna stevila ali ne. Naj bosta a in b realni stevili in naj bo a < b. Tedaj definiramo: [a, b] = {x | x G R A a < x < b} zaprti interval (a, b) = {x | x G R A a < x < b} odprti interval (a, b] = {x | x G R A a < x < b} navzgor polzaprti interval [a, b) = {x | x G R A a < x < b} navzdol polzaprti interval [a, to) = {x | x G R A a < x} navzgor neomejeni zaprti interval (a, to) = {x | x G R A a < x} navzgor neomejeni odprti interval (-to, b] = {x | x G R A a < x} navzdol neomejeni zaprtii interval (-to, b) = {x | x G R A a < x} navzdol neomejeni odprtii interval Zgled. Preveri, da velja n t0,1)={^ in n t0, n=0. n€N n€N Zgled. Preveri, da velja U t1, 1] = (0,1]. n€N 4.5 Potencna množica Naj bo A dana mnozica. Mnozici, katere elementi so natanko vse podmnozice mnozice A (vkljucno s podmnozicama A in 0) recemo potencna mnozica mnozice A. Oznacimo jo z oznako P A. Na primer, ce je A = {1,2}, potem je P A = {0, {1},{2},{1,2}}. Ni se tezko prepricati, da potencna mnozica mnozice z n elementi steje natanko 2n elementov. 4.6 Urejeni pari in kartezicni produkt Naj bosta a in b dva objekta. Tedaj njun urejeni par oznacimo s simbolom (a, b). Dva urejena para (a, b) in (c, d) sta enaka, ce in samo ce je a = c in b = d. Mnozico vseh urejenih parov (a,b), kjer a pretece neko mnozico A, b pa neko mnozico B, oznacimo z A x B in ji recemo kartezicni produkt mnozic A in B. A x B = {(a, b) : a G A, b G B}. Zgled. Nastej elemente kartezicnega produkta A x B, kjer je A = {1,2,3} in B = {3,4}. A x B = {(1, 3), (1, 4), (2, 3), (2, 4), (3, 3), (3, 4)}. Urejeni pari in karteziCni produkt 27 Trditev 4.1 Ce množica A šteje n elementov, množica B pa m elementov, tedaj množica A x B šteje nm elementov. Podobno kot kartezicni produkt dveh mnozic lahko definiramo tudi kartezicni produkt poljubnega stevila mnozic A1, A2,..., An. Elementi taksnega produkta niso vec urejeni pari, temvec urejene n-terice (a1, a2,..., an): A1 x A2 x ... x An = {(a1, a2,..., an) : a1 G A1, a2 G A2,..., an G An}. 5 Relacije V matematiki (in tudi zunaj nje) imamo velikokrat opravka s pojmom relacija. Na primer, v mnozici stevil lahko vpeljemo relacijo <, ali pa relacijo =, ali denimo = (mod3), itd. V geometriji lahko vpeljemo relacije vzporednosti, skladnosti in podobno. Tudi v vsakdanjem zivljenju si lahko mislimo relacije kot so: "x je oce y", "x ima rad y", "x je starej si od y", itd. Kako ta intuitiven pojem vpeljati na korekten nacin? Denimo, da imamo neko relacijo R med objekti mnozice A. Ta relacija doloca mnozico {(x, y) | x je v relaciji R z y} C A x A. Ocitno je zgornja mnozica z relacijo R natanko dolocena. Velja pa tudi obratno. Vsaka podmnozica R C A x A doloca neko relacijo, namrec tisto, za katero velja: x je v relaciji z y natanko tedaj, ko je (x, y) G R. V tem smislu lahko pojem relacije in podmnozice mnozice Ax A kar enacimo. V resnici na ta nacin dobimo tako imenovane dvomestne relacije. Seveda pa poznamo relacije, ki povezujejo vec kot dva objekta, na primer, v geometriji lahko vpeljemo "premica x je v relaciji s premicama y in z, ce seka y in z pod istim kotom", ali pa v teoriji stevil, "x, y in z so v relaciji, ce je x+y = z", itd. Tak sne trimestne relacije lahko predstavimo s podmnozicami kartezicnega produkta A x A x A. Definicija 5.1 Naj bo n naravno stevilo. Podmnozici R mnozice An = A x A x ... x A pravimo n-mestna relacija na mnozici A. Ce je (xi, x2,..., xn) G R. recemo, da so elementi x1 , x2,... ,xn v relaciji R. Ce je n = 2, dejstvo (x1,x2) G R zapisemo tudi kot x1Rx2. Od sedaj dalje se bomo ukvarjali le z dvomestnimi relacijami. Ce je mnozica A, na kateri je relacija definirana, koncna (in ne prevelika), si lahko dvomestno relacijo predstavimo tudi s pomocjo grafa relacije, ki ga dobimo takole: Vsak element mnozice A predstavimo kot tocko v ravnini, za vsak par elementov a, b G A, za katera velja aRb, pa narisemo usmerjeno daljico od a do b. C e je a = b (in torej aRa), potem namesto usmerjene daljice nari s emo zanko skozi a (ukrivljeno crto, ki se pricne in konca v a). Operacije na relacijah 29 Zgled. Narisi graf relacije R na mnozici {2,3, 4, 5, 6, 7,8,9} definirani s predpisom xRy = x deli y. Nari semo osem tock v ravnini (denimo enakomerno razporejenih na obodu kroga), jih oznacimo s stevili 2, 3,..., 9, nari s emo usmerjene daljice ^t, 2(6, 28,36, Š2), 48 in dodamo se zanko na vsako od osmih tock. ■ Naj bo R dvomestna relacija na mnozici A. Tedaj mnozici Dr = {x | 3y(xRy)} recemo domena realcije R, mnozici Zr = {y | 3x(xRy)} pa zaloga vrednosti realcije R. Ocitno velja R C DR x ZR. Unija DR UZR se imenuje polje relacije R. Na grafu domeno relacije prepoznamo kot mnozico tock, iz katerih kaze vsaj ena usmerjena daljica (ali zanka), zalogo vrednosti pa kot mnozcio tock, v katero kaze vsaj ena usmerjena daljica (ali zanka). 5.1 Operacije na relacijah Iz danih relacij R in T na mnozici A lahko tvorimo nove relacije na mnozici A. Oglejmo si nekaj nacinov: Komplementarna relacija: Elementa x,y G A sta v komplementarni relaciji R natanko tedaj, ko nista v relaciji R: x R y ^ —(x R y). Graf komplementarne relacije narisemo tako, da narisemo usmerjene daljice povsod, kjer jih prej ni bilo, stare pa zbrisemo. Zgledi: Ce je R relacija "biti vecji ali enak" na mnozici naravnih stevil, je komplementarna relacija R relacija "ne biti vecji ali enak", kar je na mnozici naravnih stevil isto kot "biti strogo manj si". Komplementarna relacija relacije "biti sin od" je "ne biti sin od". Podobno, ce je R relacija "biti vzporeden" na mnozici vseh premic v ravnini, potem sta dve premici v komplementarni relaciji R, ce in samo ce nista vzporedni. Inverzna relacija: Elementa x, y G A sta v inverzni relaciji R-1, natanko tedaj, ko sta v obratnem vrstnem redu, y, x, v relaciji R: x R 1 y ^ y R x. Velja: Dr-i = ZR in Zr-i = Dr. Ocitno tudi: (R 1) 1 = R. Graf inverzne relacije dobimo tako, da spremenimo usmeritev vsem usmerjenim daljicam. Zgledi: Inverz relacije < na mnozici R je relacija >. Inverz relacije "moz" na mnozici drzaljanov RS je "zena". Inverz relacije "je sosed ali soseda" pa je kar relacija "je sosed ali soseda". Kompozitum relacij: Elementa x in z sta v sestavljeni relaciji T o R, ce lahko najdemo kak element (recimo y), za katerega velja xRy in yRz. S simboli: x (T o R) z ^ 3y (x R y A y R z). Graf kompozita T o R dobimo tako, da na isto sliko narisemo grafa relacij T in R, prvega z modro barvo, drugega z rdeco, nato pa vsak zaporedni par rdece in modre usmerjene daljice (v tem vrstnem redu) nadomestimo z novo (crno) usmerjeno daljico. Stare (rdece in modre) daljice seveda zbrisemo. Zgled. Kakčne relacije na mnočici ljudi predstavljajo naslednji kompoziti: 'je brat" o "je sin"; "je sin" o "je brat"; "je sin" o "je oče"; "je oče" o "je sin". Pri tem zaradi enostavnosti predpostavimo, da ima vsaka oseba otroke z največ eno drugo osebo, le-ta pa je nasprotnega spola. • x ("je brat" o "je sin") y ^ x "je necak (po ocetovi strani)" y; • x ("je sin" o "je brat") y ^ x "je sin" y A x ima brata; • x ("je sin" o "je oce") y ^ (x = y A x ima sina) V(x je moski in ima sina z y); • x ("je oce" o "je sin") y ^ x = y V x je brat ali sestra y. ■ Zgornji zgledi kazejo, da v splosnem ne velja komutativnostni zakon R o T = ToR. Velja pa asociativnostni zakon, Ro(ToS) = (RoT)oS, in obicajno pravilo za racunanje inverza sestavljene relacije, (R o T)-1 = T-1 o R-1. Na vsaki mnozici A z vsaj dvema elementoma imamo vedno vsaj tri relacije: univerzalno relacijo U = A x A, prazno relacijo 0 in identiteto ! = {(x,x) | x G A}. Ocitno za poljubno relacijo R velja: • R o I = I o R = R, • R o 0 = 0 o R = 0, Lastnosti relacij 31 • x R o U y ^ (3-u)(uRy), • x U o R y ^ (3v)(xRv). 5.2 Lastnosti relacij Naj bo R dvomestna relacija na mnozici A. Tedaj pravimo: • R je refleksivna ^ (Vx G A)(xRx); • R je irefleksivna ^ (Vx G A)(xRx); • R je simetricna ^ (Vx G A)(Vy G A)(x R y ^ yRx); • R je asimetricna ^ (Vx G A)(Vy G A)(x R y ^ y R x); • R je antisimetricna ^ (Vx G A)(Vy G A)(xRy A yRx ^ x = y); • R je tranzitivna ^ (Vx G A)(Vy G A)(Vz G A)(xRy A y R z ^ x Rz); • R je sovisna ^ (Vx G A)(Vy G A)(x = y ^ (xRy V yR x)); • R je strogo sovisna ^ (Vx G A)(Vy G A)(x R y V y R x). Zgornje lastnosti relacij se seveda odrazajo tudi na grafu relacije. Tako je, na primer, relacija refleksivna, ce skozi vsako tocko poteka zanka, simetricna, ce graf z vsako usmerjeno daljico vsebuje tudi njej nasprotno usmerjeno daljico (v tem primeru taksen par navadno nadomestimo z eno samo, neusmerjeno daljico), tranzitivna, ce z vsakim parom zaporednih usmerjenih daljic graf premore tudi usmerjeno daljico od prve do tretje tocke v taksnem zaporedju itd. Za vajo premisli, katere od zgoraj na stetih lastnosti imajo naslednje relacije: • < na mnozici R, • < na mnozici R, • "kongruenten modulo 5" na Z, • C na P (N). 5.3 EkvivalenCna relacija in relacije urejenosti Relacija je ekvivalencna, ce je hkrati refleksivna, simetricna in tranzitivna. Najpreprostejsi zgled je kar identiteta I. Nadaljni zgledi so kongruenca po modulu m v mnozici Z, vzporednost v mnozici premic v ravnini, "biti enako star" na mnozici ljudi itd. Lastnost "biti ekvivalencna relacija" lahko izrazimo tudi v jeziku inverza in kompozita relacij. Trditev 5.2 Relacija R je ekvivalencna relacija na mnozici A natanko tedaj, ko je DR = A in velja R-1 o R = R. Graf ekvivalencne relacije razpade na nekaj med seboj nepovezanih grozdov, pri cemer znotraj posameznega grozda najdemo vse mozne usmerjene daljico (vkljucno z vsemi zankami). Tem grozdom pravimo tudi ekvivalencni razredi relacije. Ekvivalencne razrede natancneje definiramo takole: Definicija 5.3 Naj bo R ekvivalencna relacija na mnozici A in a G A. Tedaj mnozici R(a) = {x G A | aRx} recemo ekvivalencni razred elementa a. Mnozici A/R = {R(a) | a G A} vseh ekvivalencnih razredov recemo faktorska mnozica glede na R. Mnozici R = {A1,...,An} nepraznih, paroma disjunktnih mnozic Aj, katerih unija je enaka A, recemo razbitje mnozice A. Ni se tezko prepricati v naslednje: Trditev 5.4 Faktorska množica A/R ekvivalencne relacije R C A x A tvori razbitje množice A. Velja pa tudi obrat zgornje trditve: Denimo, da je R razbitje mnozice A. Definirajmo relacijo R na A takole: xRy ^ "x in y lezita v isti mnozici razbitja R". Ni tezko videti, da je tako definirana relacija R ekvivalencna, faktorska mnozica A/R pa kar enaka R. Relacijam, ki so tranzitivne, recemo tudi relacije urejenosti. Relacije urejenosti razvrstimo v razlicne skupine (in podskupine), glede na to, katere dodatne lastnosti se imajo: Definicija 5.5 Naj bo R tranzitivna relacija na mnozici A. C e je se: • refleksivna in antisimetricna, ji recemo delna urejenost; • antisimetricna in strogo sovisna ji recemo linearna urejenost; • asimetricna, ji recemo stroga delna urejenost; • asimetricna in sovisna, ji recemo stroga linearna urejenost. Trditev 5.6 Vsaka strogo sovisna relacija je refleksivna. Dokaž: Naj bo R strogo sovisna relacija na mnozici S. Tedaj za poljuben par elementov x, y G S velja xRy ali yRx. Ce za y vzamemo kar x, dobimo: xRx ali xRx, kar je isto kot xRx. I Neposredno iz definicije skupin urejenosti in zgornje trditve tedaj sledi: • R je linearna urejenost ^ R je delna urejenost; • R je stroga linearna urejenost ^ R je stroga delna urejenost. 5.4 Funkcije Kot zanimivost si poglejmo se zvezo med relacijami in funkcijami. Naj bo R relacija na mnozici S in A C S. S simbolom R(A) (ali tudi s simbolom AR) bomo oznacevali mnozico {y G S | (3x G A)xRy}. Ce je A = {x} mnozica z enim samim elementom, pi semo kraj se R(A) = R(x) = xR. Mnozica R(x) je neprazna natanko tedaj, ko je x G Dr. Naceloma lahko vsebuje vec kot en element. Ce pa velja, da mnozica R(x) vsebuje najvec element za vsak x, recemo, da je relacija R enolicna. Enolicnim relacijam recemo tudi funkcije (ali preslikave). Zapi s imo se s simboli: Definicija 5.7 Relacija f na mnozici S je enolicna, ce zanjo velja: (Vx)(Vy)(Vz)((xf y A xfz) ^ y = z). Enolicni relaciji recemo tudi funkcija. Pri tem namesto xfy pisemo kar y = f (x), ali pa tudi xf. Pojem domene in zaloge vrednosti relacije se smiselno prenese tudi na funkcije, saj so le-te poseben primer relacije. Ce je torej f enolicna relacija na mnozici S (funkcija), je Df = {x 1 3y(y = f (x))} in Zf = {y 1 3x(y = f (x))}. Pri funkcijah navadno poudarimo, kaj so njihove domene tako, da pi semo f: A 2 S, kjer je A = Df, medtem ko je S poljubna mnozica, ki vsebuje zalogo vrednosti Zf. Ce pri zapisu f: A 2 S slucajno velja S = Zf, recemo, da je f surjek-tivna funkcija (na mnozico S). Inverz funkcije ni nujno enolicna relacija. Ce pa kljub temu je, recemo, da je funkcija injektivna. Definicija 5.8 Funkcija f na mnozici S je injektivna, ce je inverzna relacija f-1 enolicna: (Vx)(Vy)(Vz)((xf z A yfz) ^ x = y). Ni tezko videti, da za relacijo R na mnozici S in podmnozici U, V C S velja naslednje: • R(U U V) = R(U) U R(V) in R(U n V) C R(U) n R(V) (vsebovanost v obratno smer ne velja nujno - npr. R je konstantna funkcija, U in V pa disjunktni). • Ce je R injektivna, velja tudi R(U n V) = R(U) n R(V). • R-1(U U V) = R-1(U) U R-1(V) in R-1(U n V) C R-1(U) n R-1(V). • C e je R enolicna, velja tudi R-1(U n V) = R-1(U) n R-1(V). • U C R-1(R(U)). • C e je R injektivna, velja tudi U = R-1(R(U)). • R(R-1(U)) C U. • Ce je U C Zr, velja tudi R(R-1(U)) = U. • R(R-1(R(U))) = R(U). Teorija grafov 6 Osnovno o grafih Opomba. Ta razdelek v veliki meri sledi prvemu poglavju knjige [3]. 6.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 tock (tudi vozlisc) 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 6.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 napišemo 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 vozli scema pa kot krivuljo (obicajno kar kot daljico) s krajiscema v tockah ravnine, ki ustrezata krajiscema povezave. Stopnja tocke (tudi valenca tocke) 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 6.1 (O rokovanju). Za vsak graf r velja £ deg(v) = 2 ■ |E(r)|. vev (r) Dokaž: Uporabili bomo tako imenovano racunovodsko pravilo. Naj bo M mnozica vseh urejenih parov (u, e) G V (r) x E(r), za katere je u krajisce povezave e. Pre stejmo elemente mnozice M. Po eni strani velja |M| = £ deg(u), uev (r) po drugi strani pa |M| = £ 2 = 2 ■ |E(r)|. eeE(r) S tem je trditev dokazana. I Posledica 6.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) tocke v, pri cemer prva predstavlja stevilo tock u grafa r, za katere je uv usmerjena povezava grafa r, druga pa stevilo tock u grafa r, za katere je vu usmerjena povezava grafa r. V kontekstu grafov lema o rokovanju preide v enakost £ deg-(v) = £ deg+(v) = |E|. »ev (r) »ev (r) Graf r' je podgraf grafa r, ce velja V (r') C V (r) in E(r') C E (r). Podgraf r' je vpet, ce velja V (r') = V (r), in je induciran z mnozico tock U C V (r), ce 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, ce lahko mnozico tock V (r) zapisemo kot disjunktno unijo dveh podmnozic A, B C V (r) tako, da je za vsako povezavo uv G E (r) ena od tock u, v vsebovana v mnozici A, druga pa v mnozici B. Mnozici A in B imenujemo mnozici dvodelnega razbitja grafa r. MetriCne lastnosti 37 6.2 MetriCne lastnosti Zaporedje tock vov1... vk grafa r je sprehod dolzine k, ce vi ~ vi+1 za 0 < i < k. Sprehod je enostaven, ce so vse povezave na njem razlicne. Sprehod je sklenjen, ce je v0 = vk. Sprehod, na katerem so vse tocke razlicne, je pot, enostaven sklenjen sprehod z vsaj eno povezavo, na katerem sta enaki le prva in zadnja tocka, pa je cikel grafa. Zaradi enostavnosti dopuscamo tudi sprehode dolzine 0, tj. sprehode oblike v0. Sprehod dolzine 0 je seveda hkrati tudi pot, domenimo pa se, da ga ne bomo imeli za cikel. Lema 6.3 Ce med točkama grafa obstaja sprehod dolzine k, potem med njima obstaja tudi pot dolzine največ k. Dokaz: Naj bosta u in v poljubni tocki grafa r med katerima obstaja sprehod. C e 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 s i 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 6.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 ozina) grafa. 6.3 Nekatere družine grafov V tem razdelku si bomo ogledali nekaj družin grafov, kijih pogosto srečujemo v zgledih in nalogah. Polni grafi Kn: V(Kn) = Zni E(Kn) = {uv | u, v G Zn, u = v}. Polni graf Kn ima n točk in (n) = n(n2-1) povezav. Je (n — 1)-regularen graf in je dvodelen le za n = 1 in 2. Poti Pn: V(Pn) = Zn, E(Pn) = {u(u + 1) | u = 0,1,. ..,n — 2}. Pot Pn ima n točk in n — 1 povezav (njena dolžina je n — 1). Za n = 1 in n = 2 je enaka grafu Kn. Vse poti so dvodelni grafi. Slika 2: Poti Pi, P2, P3 in P4. Cikli Cn (n > 3): V(Cn) = Zn, E(Cn) = {u(u + 1) | u G Zn}. Kadar dopusčamo tudi multigrafe, sta definirana se 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 stevilo. Vsak 2-regularen graf je disjunktna unija enega ali več čiklov. Cikel C3 imenujemo tudi trikotnik. 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 tock in mn povezav. Graf Km,n je regularen natanko tedaj, ko je m = n. Vsi grafi Km,n so dvodelni. Grafom Ki,n pravimo tudi zvezde. Slika 4: Polni dvodelni grafi K1,8, K2,4 in K3,3. Hiperkocke Qd: V(Qd) = {(ui,u2,..., ud) | u G {0,1}}, E(Qn) = {uv | u, v G V(Qd) : d=1 — vj| = 1}. Običajno med hiperkocke Štejemo tudi 0-razseZno kocko Q0 = K1. Hiperkocka Qd (skelet d-razseZne kocke) ima 2d tock in d ■ 2d 1 povezav. Je d-regularen graf. Vse hiperkocke so dvodelni grafi (za mnozici dvodelnega razbitja vzamemo mnozico tock, ki imajo sodo mnogo komponent enakih 0, in mnozico tock, ki imajo liho mnogo komponent enakih 0). 10 u— 00 11 -o 01 110 111 100/ 101 000 010 001 000 011 \ 111 / 110 101 100 001 Slika 5: Hiperkocki Q1 in Q2 ter dve sliki hiperkocke Q3. Kolesa W,n (n > 3): V(Wn) = ZnU{^}, E(Wn) = {u(u+1),uto | u G Zn}. Graf Wn ima n + 1 tock in 2n povezav. Za kolesa velja č(Wn) = 3 in A(Wn) = n. Edino regularno kolo je W3 ~ K4. Nobeno kolo ni dvodelen graf. Slika 6: Kolesa W3, W5 in Wa. Posplošeni Petersenovi grafi Pn,k (n > 3 in 0 < k < n): V(Pn,k) = {ui,vi | i G Zn}, E(Pn,k) = {uiui+i,uivi,vivi+k | i G Zn}. Posploseni Petersenov graf Pn,k ima 2n tock. C e je n = 2k, ima 3n povezav in je kubicen 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. 7 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 7.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 ciklov 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 zadosca (5), zato po indukcijski predpostavki Xi zados ca 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 ciklov. Dokazujemo, da obstaja med poljubnima tockama natanko ena pot. Zaradi povezan-oti obstaja vsaj ena pot. Ce bi bili dve, bi dobili cikel - protislovje. I Posledica 7.2 Drevo z vsaj dvema tockama vsebuje dve točki stopnje 1. Dokaz: Naj bo r graf, v katerem ima vsaj |V(r)| — 1 tock stopnjo vsaj 2 (oznacimo mnozico teh tock z U). Preostala tocka ima stopnjo vsaj 1, saj bi sicer 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 7.1 sledi, da r ni drevo, kar je protislovje I opomba. Tocki stopnje 1 recemo tudi list grafa. Zgornja posledica torej pravi, da ima drevo vsaj dva lista. Ce ima drevo natanko dva lista, potem se neenakost v dokazu zgornje trditve izide le, ce ima vsaka druga tocka stopno natanko 2. Ni se tezko prepricati, da je povezan graf, ki ima dva lista, ostale tocke pa imajo stopnjo 2, izomorfen poti. 7.1 Vpeta drevesa Vpet podgraf grafa r, ki je drevo, se imenuje vpeto drevo grafa r. Trditev 7.3 Graf je povezan, če in samo če 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. Število 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 skrcimo, 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 7.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 7.5 Laplacova matrika L(T) (multi)grafa r je kvadratna matrika, katere stoplci in vrstice so indeksirane s tockami grafa, v preseciscu vrstice u in stoplca v lezi negativno stevilo povezav med u in v, diagonalni element tocke v pa je enak stopnji tocke v. Trditev 7.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. 8 Eulerjevi in hamiltonovi grafi Opomba. Ta razdelek v veliki meri sledi cetrtemu poglavju knjige [3]. 8.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. Ižrek 8.1 Multigraf r brez izoliranih točk je eulerjev, če in samo če je povezan in so vse njegove točke sode stopnje. Dokaž: 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 T' 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 taksni 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, tak s en 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 8.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 8.2 Naj bo S C V (r) neprazna mnočica 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 cikel 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 najvecji indeks, za katerega je vni G V(ri). Tocka vni je torej zadnja tocka na ciklu C, ki se lezi v komponenti ri. Naslednja tocka, vi+1, je element mnozice S. Tocke vni+1, vn2+1,..., vnk+1 so torej (paroma razlicni) elementi mnozice 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 mnozico 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 8.3 Naj bosta u in v takšni 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 mnozica indeksov sosed tocke u ter V mnozica indeksov sosed tocke 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 cikel v grafu r. Predpostavimo torej lahko, da taks nega indeksa i ni. Z drugimi besedami, V C {0,1,..., n — 2} \ (U — 1), kjer smo z U — 1 oznacili mnozico {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 tock u in v. I Od tod z lahkoto izpeljemo naslednji posledici. Izrek 8.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 8.5 (Dirac). Ce ima graf r vsaj 3 točke in velja č(r) > , potem je graf G hamiltonov. ravninski grafi in eulerjeva formula 47 9 Ravninski grafi in Eulerjeva formula Kot smo ze omenili v uvodu, grafe radi risemo v ravnini tako, da vo-zlisče grafa predstavimo kot točko ravnine, povezo med vozlisčema pa kot ravno (ali pa tudi krivo) črto s kraji sči v točkah, ki ustrezata krajisčema povezave. Pri tem pazimo, da povezava (oziroma, natančneje, črta, ki ponazarja povezavo) ne seka same sebe in ne poteka skozi nobeno drugo vozlisče kot le svoje krajisče. Seveda ima lahko dani graf več različnih risb. Ce obstaja risba grafa, pri kateri se nobeni dve povezavi med seboj ne sekata (razen morda v svojih krajisčih), rečemo, daje graf ravninski, taksni risbi pa ravniska risba grafa. Tako so, na primer, ravninski vsi čikli 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 definičijo risbe in ravninskosti grafa lahko opišemo takole: Vložitev multigrafa r v metrični prostor S je določena z injektivno preslikavo f: V (r) ^ S, ki vsaki točki multigrafa priredi točko prostora S, in tako druzino zveznih preslikav f e: [0,1] ^ S (tu smo povezavo e predstavili z zaprtim intervalom [0,1]), da velja: fe(0) je slika enega, fe(1) pa slika drugega krajisča povezave e, f e| (o,i) je injektivna in njena slika ne vsebuje nobene točke, ki bi bila slika točke 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 načeloma enostavno - najti moramo njegovo ravninsko risbo. Prečej 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 nemogoče, je za dokazovanje neravninskosti grafov potrebno razviti kaks ne drugačne prijeme. Eden taks nih je Eulerjeva formula. 9.1 Eulerjeva formula Zamislimo si ravninsko risbo ravninskega grafa r. Ce iz ravnine izrezemo vse črte in točke, ki predstavljajo povezave in vozlisča grafa, dobimo nekaj med seboj ločenih povezanih območij, ki jih imenujemo lica. Eno od teh območij je neomejeno in obdaja čelotno risbo grafa, ostala območja pa so omejena. Mnozičo vsej lič tako narisanega grafa r označimo z F (r). Na prvi pogled ni videti nobenega razloga, zakaj bi stevilo lič grafa ne bilo odvisno od konkretne ravniske risbe le-tega. Zato je toliko presenetljivejsa naslednja trditev, iz katere med drugim sledi, da je stevilo lic ravninskega grafa neodvisno od konkretne ravninske risbe. Ižrek 9.1 (Eulerjeva formula) Naj bo r ravninski graf z mnoZičo vozličč V in mnozičo povezav E. Naj bo F mnoziča lič kake ravninske slike grafa r in Q mnoziča komponent za povezanost grafa r. Tedaj velja naslednja enakost: IV | — |E | + |F | = 1 + |Q|. Zgornji izrek navadno dokazujemo z indukcijo na stevilo povezav grafa. Pri tem si pomagamo tudi s formulo o stevilu povezav v drevesu z n tockami. Podrobnosti dokaza bomo izpustili. Namesto tega raje izpeljimo naslednjo pomembno posledico Eulerjeve formule. Trditev 9.2 Naj bo r povezan ravninski graf z vsaj tremi točkami. Tedaj je |E(r)| < 3|v(r)| — 6. Dokaž: Izberimo kako ravninsko sliko grafa r in z F oznacimo mnozico pripadajocih lic, z E pa mnozico vseh usmerjenih povezav grafa r (tj. mnozico vseh parov (u, v), u, v G V (r), za katere je u ~ v). Ce rob lica prehodimo v smeri urinega kazalca, dobimo sklenjen sprehod v grafu, ki ga bomo imenovali kar usmerjeni rob lica. Za razliko od omejenih lic se domenimo, da je usmerjeni rob neomejenega lica obhod, ki ga dobimo, ce robne povezave zunanjega lica prehodimo v smeri, ki je nasprotna urinemu kazalcu. Opazimo, da vsaka usmerjena povezava lezi na natanko enem robu lica (namrec na robu tistega lica, ki lezi desno od nje, ce gledamo v smeri usmeritve povezave). Hkrati pa vsak rob lica vsebuje vsako usmerjeno povezavo najvec enkrat. Stevilo usmerjenih povezav, ki jih vsebuje rob lica f G F, oznacimo 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 mnozico parov M = {(e, f) : e G E f G F, e lezi na robu f}. Elemente mnozice M prestejmo na dva nacina: |M| = ^ 1 = |E | =2|E |. eeE Po drugi strani: |M| = E deg(f) > E 3 = 3|F|. feF feF 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 9.3 Naj bo r povezan ravninski graf z vsaj štirimi točkami. Ce r ne vsebuje cikla dolzine 3, tedaj je |E(r)| < 2|v(r)| — 4. Iz zgornjih dveh rezultatov neposredno sledi naslednje. Trditev 9.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 vozli sc 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. 9.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 9.5 Ceje 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 krajiscema 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 9.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 9.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 9.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 9.8 Ce je graf r ravninski, tedaj je ravninski tudi vsak njegov minor r'. S pomocjo Trditve 9.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 9.9 (Wagner) Graf r je ravninski, ce in samo ce ne premore minorja, izomorfnega K5 ali K3,3. 10 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). Najmanj se 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. Najmanj se stevilo k, za katero obstaja dobro k-barvanje povezav multigrafa brez zank r, imenujemo kromatični indeks multigrafa r; oznaka x'(G). 10.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 pozre sni metodi. Nekoliko tezje pa je dokazati, da je ta zgornja meja dosezena le pri lihih ciklih in polnih grafih. Prav to pravi Brooksov izrek. Ižrek 10.1 (Brooks). Naj bo r povezan graf. Ce r ni lih čikel 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: Ižrek 10.2 (Izrek s tirih barv). Za vsak ravninski graf r je x(r) < 4. Zgled. Poisci kromaticno stevilo Petersenovega grafa Pet. Ker Pet vsebuje cikel dolzine 5, je x(Pet) > x(C5) = 3. Ker je Pet kubicen graf, iz Brooksovega izreka dobimo x(Pet) < 3. Torej x(Pet) =3. ■ 10.2 Barvanje povezav Tudi za barvanja povezav velja, da iz r' C r sledi x'(r) < x'(r). Na-jpomembnej si izrek o barvanju povezav grafov je: Izrek 10.3 (Vizing). Za vsak graf G velja A(r) < x'(r) < A(r) + 1. Graf r je razreda 1, ce je x'(r) = A(r), sicer je razreda 2. Ce je n sod, sta grafa Cn in Kn razreda 1, za lihe n-je pa sta razreda 2. Pomembna druzina grafov razreda 1 so dvodelni grafi. Natancneje: Izrek 10.4 (Konig). Za dvodelni multigraf r velja x'(r) = A(r). Za multigrafe je kromaticni indeks lahko vecji od maksimalne stopnje tock plus ena. Izrek 10.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) + 2A(r)}. Algebra in teorija Stevil 11 Algebrske strukture Pod pojmom algebrska .struktura v matematiki navadno razumemo poljubno mnozico skupaj z eno ali vec operacijami na njej. Nekate algebrske strukture, pri katerih operacije zado scajo kakim dodatnim tipicnim lastnostim, poimenujemo s posebnimi imeni, kot so polgrupa, grupa, kolobar, obseg, vektorski prostor itd. V tem poglavjuu si bomo na hitro ogledali nekatere od teh algebrskih struktur. 11.1 Operacije Naj bo M poljubna mnozica. Operacija na množici M je poljubno pravilo, ki (urejenemu) paru elementov a, b G M priredi tretji element iz M. C e operacijo oznacimo s o, tedaj element, ki ga ta operacija priredi paru a, b G M, oznacimo z a o b. Med dobro znane zglede operacij sodijo mnozenje na mnozici naravnih (ali pa racionalnih, realnih, kompleksnih) stevil, odstevanje na mnozici celih (racionalnih, realnih, kompleksnih) stevil, deljenje na mnozici nenicelnih kompleknih (realnih, racionalnih) stevil, matricno mnozenje na mnozici kvadratnih matrik fiksne velikosti ipd. C e je o poljubna operacija na mnozici M, podmnozica N C M pa tak sna, da je za vsak par elementov a, b G N tudi a o b element mnozice N , pravimo, da je N zaprta za operacijo o. V tem primeru lahko operacijo o razumemo tudi kot operacijo na mnozici N. Vpeljimo sedaj dve lastnosti operacij. Definicija 11.1 Naj bo o poljubna operacija na mnozici M. Ce za vsako trojico elementov a, b, c G M velja (a o b) o c = a o (b o c), tedaj recemo, da je operacija asociativna. Vecina operacij, ki smo jih spoznali v osnovni in srednji soli, je asociativnih. Tako sta, na primer, asociativni operaciji sestevanja in mnozenja na mnozici kompleksnih stevil (in posledicno na vsaki podmnozici kompleksnih stevil, zaprti za ti dve operaciji). Pac pa ni asociativna operacija odstevanja, saj stevilo (a — b) — c ni (nujno) enako stevilu a — (b — c). Podobno ni asociativno niti deljenje na mnozici nenicelnih racionalnih stevil. Pri asociativnih operacijah lahko pri veckratni uporabi te operacije oklepaje v zapisu izpu scamo, saj je koncni rezultat odvisen le od vrstnega reda elementov, ki jih zdruzujemo, nic pa od tega, kako jih zdruzujemo med seboj. Tako, na primer, namesto (a o (b o c)) o d (*) pisemo kar a o b o c o d, (+) saj je rezultat izraza (*) enak rezultatu, ki ga dobimo, ce v (+) vstavimo oklepaje na kakrsen koli nacin. Definicija 11.2 Naj bo o poljubna operacija na mnozici M. Ce za vsak par elementov a, b G M velja a o b = b o a, tedaj recemo, da je operacija komutativna. Med komutativne operacije sodijo mnozenje in sestevanje na mnozici kompleksnih stevilih, ne pa tudi odstevanje in deljenje. Tudi mnozenje matrik, kot vemo, ni komutativna operacija. Vcasih se primeri, da v mnozici M obstaja element, denimo e, za katerega pri vsakem a G M velja pravilo a o e = e o a = a. Taksnemu elementu pravimo nedelavni element ali tudi enota za operacijo o. Hitro se prepricamo v naslednje: Operacije 55 Lema 11.3 V mnozici M, na kateri je definirana operacija o, obstaja največ ena enota za operacijo o. Dokaz: Naj bosta e, e' G M poljubni enoti za o. Oglejmo si element e o e'. Ker je e enota, je ta element enak e'. Ker pa je tudi e' enota, je hkrati enak tudi e. Zato e = e'. I Naj bo sedaj o operačija na mnoziči M, za katero obstaja enota e, in naj bo a poljuben element mnoziče M. Ce v mnoziči M najdemo element b, za katerega velja a o b = b o a = e, tedaj pravimo, da je element a obrnljiv in da je b inverzni element elementa a glede na operačijo o. Ce je iz konteksta razvidno, katero operačijo imamo v mislih, tedaj taksen element b označimo tudi z a-1, v posebnem primeru, ko operačijo o označujemo z znakom + ali pa ©, pa tudi z —a. Element mnoziče M, ki premore inverz za operačijo o, je obrnljiv glede na operacijo o. Lema 11.4 Naj bo o asociativna operacija na mnoZici M. Tedaj za dani element a obstaja največ en inverzni element. Dokaz: Naj bosta b in c dva inverzna elementa elementa a. Označimo enoto z e. Tedaj je a o b = e = a o c. Pomnozimo levo in desno stran enakosti z b, da dobimo b o (a o b) = b o (a o c). Ce upostevamo asočiativnost operačije o in dejstvo, da je b o a = e, dobimo e o b = e o c, in zato b = c. I Naslednja lema med drugim pove, da je mnoziča obrnljivih elementov zaprta za operačijo. Lema 11.5 Naj bosta a in b obrnljiva elementa mnozice M z asociativno operacijo o. Tedaj je tudi a o b obrnljiv element in (a o b)-1 = b-1 o a-1. Dokaz: Preveriti moramo, da je (a o b) o (b-1 o a-1) = e = (b-1 o a-1) o (a o b). V to pa se zlahka prepričamo, če upostevamo asočiativnost operačije in definičijo inverza ter enote. I 11.2 Algebrske strukture z eno operacijo Polgrupa Definicija 11.6 Mnozici M skupaj z asociativno operacijo o recemo polgrupa . Ce v mnozici M obstaja tudi enota za operacijo o, polgrupi M recemo monoid ali polgrupa z enoto. C e je operacija o komutativna, govorimo o komutativni polgrupi. Preprost zgled polgrupe je mnozica naravnih stevil N = {1,2,3,...} skupaj z operacijo sestevanja. C e mnozici dodamo se element 0, dobimo monoid. V tem monoidu je edini obrnljiv element ravno enota 0. Nadalje, mnozica Z vseh celih stevil tvori skupaj z operacijo mnozenja monoid. Enota v tem monoidu je element 1, obrnljiva elementa pa sta 1 in —1. Vsi zgornji zgledi polgrup so komutativni. Za zgled nekomutativnega monoida lahko vzamemo mnozico vseh 2 x 2 matrik z realnimi koeficienti skupaj z operacijo obicajnega matricnega mnozenja. Obrnljivi elementi v tem monoidu so natanko matrike z nenicelno determinanto. Grupa Definicija 11.7 Monoidu M z operacijo o, v katerem je vsak element obrnljiv glede na o, recemo grupa. C e je operacija o komutativna, govorimo o abelovi grupi. Najosnovnej si vir grup predstavljajo mnozice obrnljivih elementov v monoidu. Velja namrec naslednje. Lema 11.8 Naj bo M monoid z operacijo o. Tedaj je mnozica M * vseh obrnljivih elementov monoida zaprta za operacijo o in tvori skupaj s to operacijo grupo. Nadaljni viri grup so mnozica celih stevil z operacijo sestevanja, mnozica nenicelnih kompleksnih stevil z operacijo mnozenja in mnozica obrnljivih n x n matrik z operacijo matricnega mnozenja. Posebej pomemben zgled grupe tvori mnozica permutacij dane mnozice O (bijektivnih preslikav iz O v Q) skupaj z operacijo kompozita. Algebrske strukture ž dvema operacijama 57 11.3 Algebrske strukture z dvema operacijama Kolobar Algebrske strukture iz prej s njih razdelkov so premogle eno samo operacijo. Struktura, ki jo bomo obravnavali v tem razdelku, pa bo premogla dve operaciji, ki jih obicajno imenujemo mnozenje in sestevanje in oznacujemo bodisi s pikico "■" in plusom "+" bodisi s simboloma 0 in ©. Ti dve operaciji bosta zadoscali tako imenovanemu distributivnostnemu zakonu, ki ga bomo sedaj definirali. Definicija 11.9 Naj bosta © in 0 dve operaciji na mnozici M. Ce za vsako trojico a, b, c G M velja (a © b) 0 c = (a 0 c) © (b 0 c) in c 0 (a © b) = (c 0 a) © (c 0 b), potem recemo, da je operacija 0 distributivna proti operaciji ©. Tako je, na primer, obicajno mnozenje stevil (kompleksnih, realnih, racionalnih itd.) distributivno proti obicajnemu se stevanju. Podobno je obicajno matricno mnozenje kvadratnih matrik distributivno proti sestevanju matrik po komponentah. Zelo zanimiv zgled pa tvorita operaciji preseka (n) in unije (U) mnozic. Vsaka od teh dveh operacij je namrec distributivna proti drugi. Oborozeni z definicijo distributivnosti lahko definiramo tudi pojem kolobarja. Definicija 11.10 Mnozci M skupaj z operacijama sestevanja © in množenja 0 recemo kolobar, ce velja naslednje: (i) Mnozica M skupaj z operacijo © tvori abelovo grupo; (ii) Mnozica M skupaj z operacijo 0 tvori polgrupo; (iii) Operacija 0 je distributivna proti operaciji ©. C e je operacija 0 komutativna, govorimo o komutativnem kolobarju, ce pa obstaja enota za operacijo 0, pa govorimo o kolobarju z enoto. Mnozico elementov kolobarja M, ki so obrnljivi glede na operacijo mnozenja, oznacimo z M *. Iz definicije kolobarja sledi, da kolobar vedno premore enoto za operacijo ©, ki jo navadno oznacimo z 0. Ce premore tudi enoto za operacijo 0, jo oznacimo z 1. Zgledi kolobarjev so, na primer, stevilske mnozice Z, Q, R in C skupaj z obicajnima operacijama sestevanja in mnozenja. Vsi ti kolobarji so komu-tativni in imajo enoto. Za zgled nekomutativnega kolobarja lahko vzamemo mnozico vseh n x n matrik s kompleksnimi (ali realnimi) koeficienti, skupaj z obicajnima operacijama se stevanja in mnozenja matrik. Trditev 11.11 Za poljuben element a poljubnega kolobarja M velja enakost a ■ 0 = 0 ■ a = 0. Dokaz: Z upostevanjem definicije nicle in distributivnosti mnozenja proti se stevanju dobimo enakost 0 ■ a = (0 + 0) ■ a = 0 ■ a + 0 ■ a. Ce pri stejemo na levi in desni inverz elementa 0-a glede na se stevanje (taksen inverz navadno oznacimo z —0 ■ a) in upostevamo definicijo inverza, dobimo enakost 0 = 0 ■ a. Analogno dokazemo tudi enakost a ■ 0 = 0. I Obseg Definicija 11.12 Kolobarju z enoto in vsaj dvema elementoma, v katerem je vsak nenicelni element obrnljiv glede na operacijo mnozenja, pravimo obseg. Obseg, v katerem je operacija mnozenja komutativna, je polje. Na primer, mnozica kompleksnih (realni ali racionalnih) stevil, skupaj z obicajnima operacijama mnozenje in sestevanja je polje. 12 Teorija stevil Teorija stevil se ukvarja s celimi žtevili. Mnozico celih stevil zapi semo kot Z = {0,1, —1, 2, —2, 3, —3,...} in jo razdelimo na mnozico naravnih stevil N = {1, 2, 3,..., }, mnozico negativnih celih stevil N- = {—1, —2, —3, . . .} in mnozico, ki vsebuje le stevilo 0. 12.1 Delitelji in večkratniki Med najosnovnej se pojme teorije stevil sodi pojem deljivosti. Definicija 12.1 Celo stevilo m deli celo stevilo n, ce in samo ce obstaja taksno celo stevilo k, da je n = km. V tem primeru pisemo m | n in recemo, da je m delitelj stevila n, da je n deljiv s stevilom m in da je n veckratnik stevila m. Opazimo, da je 0 veckratnik vsakega celega stevila (saj je 0 = 0 ■ m za vsak m G Z) in da je edino stevilo, ki ga 0 deli, stevilo 0 (saj je k ■ 0 = 0 za vsak k G Z). Po drugi stran pa s tevili 1 in —1 delita prav vsa cela stevila (saj je n = n ■ 1 in n = (—n) ■ (—1) za vsak n G Z) in poleg stevil 1 in —1 nimata prav nobenih drugih deliteljev. Naj bosta m in n poljubni s tevili. Tedaj najvecje naravno stevilo, ki deli tako m kot n oznacimo z gcd(m,n) in ga imenujemo največji skupni delitelj stevil m in n. (Oznaka gcd izvira iz angleskega poimenovanja greatest common divisor). Najmanjse naravno stevilo, ki je deljivo tako z m kot z n, pa imenujemo najmanjsi skupni veckratnik stevil m in n in ga oznacimo z lcm(m,n) (angl. least common multiple). Celi stevili m in n sta tuji, ce velja gcd(m, n) = 1. Omenimo se, da je relacija deljivosti tranzitivna relacije. Natancneje, velja naslednje: Trditev 12.2 Ce r | m in m | n , tedaj r | n. Dokaz: Iz definicije deljivosti sledi, da obstajata celi stevili k in za kateri je m = kr in n = ^m. Tedaj pa je n = ^kr, od koder sledi, da je n deljiv z r. I Funkciji div in mod Naj bo n poljubno celo stevilo in m poljubno nenicelno celo stevilo. Kot smo ze opazili, kvocient n/m tedaj ni nujno celo stevilo, kar pomeni, da v mnozici celih stevil obicajna operacija deljenje ni dobro definirana. Namesto obicajnega deljenja zato vpeljemo operacijo celostevilskega deljenja, ki ste-viloma n in m priredi celostevilski količnik k = n div m ter ostanek r = n mod m. Celostevilski kolicnik k in ostanek r sta natanko dolocena s pogojem: n = km + r; k, r G Z, 0 < r < |m| — 1. 12.2 PraStevila Definicija 12.3 Od 1 razlicno naravno stevilo je pra stevilo, ce poleg samega sebe in 1 ne premore nobenega drugega naravnega delitelja. Trditev 12.4 Vsako od 1 različno naravno stevilo je deljivo z vsaj enim prastevilom. Dokaž: Dokaz bo potekal z indukcijo na naravno stevilo n. Za n = 1 trditev ne trdi nicesar, za n = 2 pa je pravilna, saj je 2 res deljiv s pra stevilom, namrec kar z 2. Privzemimo torej, da je n > 3 in da je vsako naravno stevilo, ki je manj se od n, deljivo s kakim pra stevilom. Dokazati moramo, da tedaj isto velja tudi za stevilo n. Ce je n pra stevilo, tedaj je deljivo s prastevilom n. Ce n ni prastevilo, tedaj je deljivo s kakim naravnim stevilom m, 2 < m < n — 1. Po indukcijski predpostavki je m deljiv z nekim prastevilom p. Tedaj pa iz Trditve 12.2 sledi, da p deli n. I Trditev 12.5 Prastevil je neskončno mnogo. Dokaž: Pa recimo, da jih je le koncno mnogo; oznacimo jih s p1, p2,... ,pn. Oglejmo si stevilo m = p1p2 .. .pm + 1. Ocitno je m vecji od vsakega od prastevil pi, zato ni prastevilo. Iz Trditve 12.4 tedaj sledi, daje p deljiv s kakim prastevilom; denimo s pi. Tedaj je m = p1... pi-1pipi+1 ...pm + 1 = kpi za kak k G Z, in zato 1 = pi(k — p1.. .pi-1pi+1.. .pm). To pa je nemogoce, saj 1 ni deljiv z nobenim prastevilom, torej tudi ne s pi. I Definicija 12.6 Naj bodop^p2,... ,pk poljubna, paroma razlicna prastevila in a1,..., ak poljubna naravna stevila. Tedaj zapisu n=pa1 pa2 ••• pakk pravimo razcep stevila n na prafaktorje. Trditev 12.7 Vsako od 1 različno naravno stevilo premore razcep na prafaktorje. Razcep je do vrstnega reda faktorjev en sam. Vcasih je prirocno v razcep naravnega stevila n vrini se kako prastevilo, s katerim n ni deljiv; tako prastevilo mora seveda v razcepu nastopati z eksponentom 0. Na ta nacin omogocimo, da poljubni dve naravni stevili a, b G N zapisemo z naborom istih prastevil: a = p'k1 pk2 '''Pak, b = p11 p22 '''Pfck, a, Pi > 0. S pomocjo razcepa na prafaktorje lahko dokazemo vec zanimivih trditev: Trditev 12.8 Naravno število m deli naravno število n, Ce in samo Ce za njuna razcepa na prafaktorje velja naslednje: n = pk1 Pa2 '''Pak, m = P11 p22 ■ ■ ■ pfk, bi < ai za vsak i G {1,..., k}. Trditev 12.9 Naj bodo a, b in c poljubna cela stevila. Ce sta a in b tuji stevili in ce a deli bc, tedaj a deli c. Trditev 12.10 Naj bosta a in b poljubni celi stevili in c njun skupni delitelj. Tedaj je gcd(a, b) = . Iz zgornje trditeve neposredno sledi, da sta za poljubni celi stevili a in b stevili gcdab)in gcdfab)tuji. Računanje gcd in lcm s pomočjo razcepa na prafaktorje Vzemimo naravni stevili m in n. Ce je katero od njih enako 1 (denimo n = 1), potem je ocitno gcd(m, 1) = 1 in lcm(m, 1) = m. Predpostavimo sedaj, daje m, n > 2. Naj bodo p1,... ,pn tista prastevila, ki delijo tako m kot n. Tedaj imata razcepa stevili m in n na prafaktorje obliko m = pk1 ••• Pkn ■ ^ ••• qkk, n = pf1 ■ ■ ■ p^" ■ r^1 ■ ■ ■ rj£, pri čemer je qi = rj za vsak par indeksov i, j. V tem primeru velja: gčd(m,n) = pfn{ai^}...p^n.M lčm(m, n) = p™x{ai ■ ■ ■ p^-^M . ... qkfc . ^ ... ^ Od tod neposredno sledi naslednje: Trditev 12.11 Za poljubni naravni števili m in n velja enakost gčd(m, n) ■ lčm(m, n) = mn. 12.3 Diofantske enačbe Enačbe, pri katerih isčemo zgolj čelostevilske resitve, se imenujejo diofantske enačbe. Oglejmo si nekoliko podrobneje linearne diofantske enačbe, torej enačbe oblike a1^1 + a2^2 + ... + an£n = c, (*) kjer so ai, i = 1,...,n, in c poljubna čela stevila, xi, i = 1,...,n, pa neznanke. Resitev enačbe (*) je vsaka n-teriča (x1,..., xn) čelih stevil, ki zadosča (*). Oglejmo si najprej primer, ko imamo eno samo neznanko: ax = c, a = 0. (+) Ce bi dopusčali tudi račionalne resitve, bi zgornja enačba imela natanko eno resitev, namreč x = c/a. Ker pa nas pri diofantskih enačbah zanimajo le čelostevilske resitve, bo imela diofantska enačba (+) resitev tedaj in le tedaj, ko bo a delil c (in bo zato c/a čelo stevilo). Nekoliko bolj zanimiva je linearna diofantska enačba z dvema neznankama: ax + by = c, a, b = 0. (x). Premislimo najprej, kako je z račionalnimi resitvami. Ker je a = 0, lahko zgornjo enakost preoblikujemo v x = (c — by)/a. To pomeni, da lahko za poljuben y najdemo ustrezen x, tako da bo par (x,y) resil enačbo (x). Račionalnih resitev enačbe (x) je torej neskončno mnogo pri poljubnih ko-efičientih a, b in c. Ce pa zahtevamo, da so resitve čelostevilske, pa se pojavi tezava, saj stevilo x = (c — by)/a niti pri čelostevilskih y ni nujno čelo. Velja pa naslednje: Izrek 12.12 Diofantska enačba ax + by = c, a, b = 0, (x) je rešljiva, ce in samo ce je število c deljivo z najvecjim skupnim deliteljem števil a in b. V tem primeru je resitev neskoncno mnogo. Ce je (x0, y0) neka resitev enacbe (x), so ostale resitve enacbe (x) oblike x = x0 — kb', y = y0 + ka', k G Z, kjer je a' = a/ gcd(a, b) in b' = b/ gcd(a, b). Dokaz: Obstoj res itve, v primeru, da gcd(a, b) deli c, bomo pokazali v nadaljevanju, ko bomo predstavili postopek za iskanje resitve. Osredotocimo se torej na preostale trditve iz izreka. Denimo, daje enacba (x) resljiva. Tedaj obstajata taksni stevili x0,y0 G Z, da je ax0 + bx0 = c. Ce je m poljuben skupni delitelj stevil a in b, tedaj je a = rm in b = tm za neki celi stevili r in t, in zato c = ax0 + by0 = rmx0 + tmy0 = (rx0 + ty0 )m. Od tod sledi, da vsak skupni delitelj stevil a in b (tudi gcd(a, b)) deli c. Naj bo (x0,y0) poljubna resitev enacbe (x) in x = x0 — kb', y = y0 + ka' za neko celo stevilo k. Tedaj je ax + by = a(x0 — kb') + b(y0 + ka') = ax0 + by0 = c, kar dokazuje, da je tudi (x, y) resitev enacbe. Dokazati moramo le se, da je res vsaka resitev enacbe (x) oblike x = x0 + kb', y = y0 — ka'. Pa naj bo (xi,yi) se neka resitev enacbe (x). Tedaj je (ax0 + by0) — (ax1 + by1) = 0, in zato a(x0 — x1) = b(y1 — y0). C e iz slednje enakosti pokraj samo najvecji skupni veckratnik stevil a in b, dobimo a'(x0 — x1) = b'(y1 — y0). Iz trditve 12.10 sledi, da sta s tevili a' in b' tuji. Tedaj pa iz trditve 12.9 sledi, da je k = (y1 — y0)/a' celo stevilo. Pri tem velja x0—kb' = x0 — ——= x0—(x0—x1) = x1, y0+ka' = y0+(y1— y0) = y1, in res itev (x1,y1) je res zahtevane oblike. 12.4 RazSirjeni Evklidov algoritem Razsirjeni Evklidov algoritem uporabljamo za racunanje najvecjega skupnega delitelja danih celih stevil in za re sevanje linearnih diofantskih enacb z dvema neznankama. Sam postopek lahko opi semo takole: Vhodni podatek: Par (a, b) nenicelnih celih stevil. (ro,Xo,yo) := (a, 1, 0); (r1,X1,y1) := (b, 0,1); i := 1; dokler ri = 0 izvajaj i := i + 1; ki := ri-2 div ri-1; (ri,xi,yi) := (ri-2,Xi-2, Vi-2) — ki(ri_1, Xi_1, Vi-1); konec zanke VRNI: (ri_1,Xi_1, Vi-i). Trditev 12.13 Naj bosta a in b neničelni čeli števili. Tedaj trojiča (d, x, y), ki jo vrne razsirjeni Evklidov algoritem z vhodnim podatkom (a, b), zadočča pogoju ax + by = d, d = gcd(a, b). Dokaž: Za stevila ri, ai in bi iz opisa razsirjenega evklidovega algoritma za vsak i > 0 z indukcijo dokazimo enakost axi + bvi = ri. (*) Ta enakost ocitno velja za i = 0 in i = 1, saj je ax0+by0 = a■ 1+b-0 = a = r0 in ax1 + by1 = a ■ 0 + b ■ 1 = b = r1. Denimo sedaj, daje i > 2, in privzemimo, da enakost (*) velja za vse indekse manjse od izbranega i. Tedaj axi+bvi = a(xi-2—kiXi-1)+b(vi-2—kiVi-1) = axi_2+bvi_2 —k(axi_1+bvi_1). Po indukcijski predpostavki je slednje enako ri-2 — kri—1 = ri. S tem smo dokazali enakost (*), in zato tudi ax + by = d. Dokazati moramo se, daje gcd(a, b) = d. V izreku 12.12 smo ze dokazali, da iz enakosti ax + by = d sledi, da gcd(a, b) deli d. Dokazati moramo se, da d deli tako a kot b (in zato tudi gcd(a, b)). Razsirjeni Evklidov algoritem se ustavi takrat, ko vrednost ostanka ri pade na nic, stevilo d, ki ga algoritem vrne, pa je zadnji nenicelni ostanek (označimo njegov indeks z n). Ker je 0 = rn+1 = rn-1 — krn = rn-1 — kd, vidimo, da d deli rn-1. DokaZimo, da d deli r za vsak i G {0,..., n}. Pa denimo, da temu ni tako, in vzemimo največji indeks j, za katerega rn ne deli rj (seveda j < n — 2). Ker je rj+2 = rj — krj+1, je rj = rj+2 + krj+1. Iz definicije indeksa j sledi, da sta stevili rj+1 in rj+2 deljivi z d, in zato tudi stevilo rj. To pa je v protislovju z na so predpostavko. S tem smo dokazali, da d res deli ri za vsak i > 0, torej tudi ro = a in r1 = b. S tem je izrek dokazan. I Trditev 12.13 nam pove, kako poiskati resitev diofantske enačbe ax + by = c kadar je c = gcd(a, b). Kaj pa, če je c nek pravi večkratnik stevila gcd(a, b), na primer c = tgčd(a, b). Tedaj najprej z raz sirjenim evklidovim algoritmom poi s čemo re s itev (x',y') enačbe ax' + by' = gčd(a,b). C e to enakost pomnozimo s stevilom t, vidimo, da je x0 = tx', y0 = ty' res resitev prvotne diofantske enačbe. Zgled. Poišči vse rešitve diofantske enačbe 4333x + 623y = 21. (*) Izvedimo razsirjeni Evklidov algoritem z vhodnim podatkom (a, b) = (4333, 623). i rj xi yi ki 0 4333 1 0 1 623 0 1 2 595 1 —6 6 3 28 —1 7 1 4 7 22 —153 21 5 0 —89 619 4 Algoritem torej vrne trojičo (7, 22, —153). Trditev 12.13 tedaj pravi, daje gčd(4333, 623) = 7 in 4333 ■ 22 + 623 ■ (—153) = 7. Enakost pomnozimo s 3 in dobimo: 4333 ■ 66 + 623 ■ (—459) = 21. Od tod razberemo, da je x0 = 66 in y0 = —459 re sitev enačbe (*). Iz Izreka 12.12 sledi, da je poljubna re s itev enačbe (*) enaka xk = 66 — ^k = 66 + 89k, yk = —459 + ^^š33k = —459 + 619k, za kak k G Z. ■ 12.5 Modularna aritmetika Definicija 12.14 Naj bo m poljubno naravno stevilo. Pravimo, da sta celi stevili x in y kongruentni po modulu m, ce in samo ce m deli y — x. Pri tem pisemo x = y (mod m) ali tudi x =m y. Relacija kongruence je v tesni zvezi z operacijo celostevilskega ostanka mod . Velja namrec naslednje: Trditev 12.15 Za poljubna stevila x,y G Z in m G N velja x = y (mod m) ^ x mod m = y mod m. Dokaz: Zapisimo x = km + r in y = £m + s, kjer je r = x mod m in s = y mod m. C e je r = s, tedaj ocitno m deli stevilo y — x = m(£ — k). Denimo sedaj, da je x = y (mod m). Dokazati moramo, da od tod sledi r = s. Ker m deli stevilo y — x = (£ — k)m + s — r, je (£ — k) + s — r = tm za neki t G Z, in zato s — r = m(t + k — £). Vendar stevili s in r obe lezita na intervalu med 0 in m — 1, zato tudi njuna razlika po absolutni vrednosti ne presega stevila m — 1. Iz zgornje enakosti tedaj sledi, da je t + k — £ = 0, in zato s = r, kot je bilo potrebno dokazati. I Kot kaze naslednji izrek, je relacija kongruence lepo uglasena z operacijama se stevanja in mnozenja. Izrek 12.16 Naj velja x1 = y1 (mod m) in x2 = y2 (mod m). Tedaj velja tudi x1 + x2 = y1 + y2 (mod m) in x1x2 = y1y2 (mod m). Dokaz: Pi s imo y1 — x1 = k1m in y2 — x2 = k2m. Tedaj je (y1 + y2) — (x1 + x2) = (k1 + k2)m, in zato x1 + x2 = y1 + y2 (mod m). Pri dokazu druge kongruence moramo biti nekoli zviti. Racunajmo: y1y2 — x1x2 = y1 (y2 — x2) + (y1 — x1)x2 = (y1k2 + k1x2)m. Torej m deli razliko y1y2 — x1x2, in zato x1x2 = y1y2 (mod m). I Od tod lahko z uporabo indukcije izpeljemo naslednji sklep. Trditev 12.17 Ceje x = y (mod m) in r G N, tedaj je tudi xr = yr (mod m). Naslednji izrek pa nam pove, na kak sen nacin lahko iz kongruence kraj samo multiplikativne faktorje. Ižrek 12.18 Naj bodo a, x,y poljubna čela čtevila, a = 0, in m poljubno naravno stevilo. Tedaj velja naslednji sklep: ax = ay (mod m) ^ x = v (mod ——j). Dokaž: Naj velja ax = ay (mod m). Tedaj obstaja k G Z, tako da je ay — ax = km. Na levi izpostavimo a in enakost delimo z gcd(a, m). Dobimo: am -(V — x) = k- gcd(a, m) gcd(a, m) Iz trditve 12.9 sledi, da sta stevili gcd(a m) in gcd(a m) tuji. Trditev 12.10 pa tedaj pravi, da gcd^a m) deli v — x, kot smo zeleli pokazati. I Zgornjo trditev najveckrat uporabimo v dveh skrajnih primerih: ko je a tuj m in ko a deli m. Sklepa, ki ju dobimo v teh dveh primerih, zapi simo posebej: Posledica 12.19 Naj velja ax = ay (mod m). (i) Ce je gcd(a, m) = 1, tedaj je x = y (mod m). (ii) Ce a deli m, tedaj je x = y (mod (). 12.6 Kolobar ostankov Skozi ves razdelek naj m predstavlja poljubno fiksno naravno stevilo, vecje ali enako 2. Mnozico vseh moznih ostankov pri deljenju s stevilom m oznacimo takole: Zm = {0,1,..., m — 1}. Na mnozici ostankov Z( definirajmo operaciji, ki ju bomo imenovali sestevanje in mnozenje po modulu m in oznacevali z © in 0. Za a, b G Zm naj bo a © b = (a + b) mod m in a 0 b = (ab) mod m. Kot bomo videli, se ti dve operaciji v mnogocem obna sata podobno kot navadno se stevanje in mnozenje, zato bomo, kadar ne bo nevarnosti za pomoto, krozec okoli znakov + in ■ izpuscali. Z nekaj dela se lahko prepricamo v naslednj trditev. Trditev 12.20 Množica Zm skupaj z operacijama seštevanja in množenja po modulu m tvori komutativni kolobar z enoto. V kolobarju Zm se lahko nekateri elementi obnašajo nekoliko nenavadno. Oglejmo si na primer elementa 6 in 4 v Zg. Njun običajni produkt je enak 24, kar je deljivo z 8. Zato v Z8 velja enakost 6 0 4 = 0. V kolobarju ostankov je torej produkt dveh neničelni Stevil lahko enak 0. Taksna stevila si zasluzijo ime: imenujemo jih delitelji niča. Ni teZko razmisliti, daje neničelni element x kolobarja Zm delitelj niča, če in samo če x ni tuj m. 12.7 Obrnljivi elementi v Zn Naj bo n poljubno naravno stevilo, večje ali enako 2. Zaradi enostavnej sega zapisa bomo v tem razdelku operačiji © in 0 v kolobarju Zn pisali kar kot običajna "plus" in "krat". Kadar bo obstajala nevarnosti za nesporazum, bomo posebej poudarili, ali imamo v mislih običajne operačije v Z ali pa gre za operačije v Zn. Definicija 12.21 Naj bo x poljuben element kolobarja ostankov Zn. Ce v Zn obstaja element x, za katerega v kolobarju Zn velja xx = 1, rečemo, da je element x obrnljiv v Zn, element x pa imenujemo inverz elementa x in ga —1 označimo z x 1. Za zgled si oglejmo element 2 v Z7. Ker je 2 ■ 4 = 8 = 1( mod 7), je 2 obrnljiv element v Z7 in 2-1 = 4. Ce si ogledamo spodnjo tabeličo mnozenja v kolobarju Z7, se hitro prepričamo, da je v Z7 obrnljiv prav vsak neničelni element. 0 1 2 3 4 5 6 0 0 0 0 0 0 0 0 1 0 1 2 3 4 5 6 2 0 2 4 6 1 3 5 3 0 3 6 2 5 1 4 4 0 4 1 5 2 6 3 5 0 5 3 1 6 4 2 6 0 6 5 4 3 2 1 Inverze lahko prečitamo iz spodnje tabele. x 1 2 3 4 5 6 1 x 1 1 4 5 2 3 6 Obrnljivi ELEMENTI v Z 69 Precej drugačna je situacija v kolobarju Z6. Oglejmo si tabelico množenja. 0 1 2 3 4 5 0 0 0 0 0 0 0 1 0 1 2 3 4 5 2 0 2 4 0 2 4 3 0 3 0 3 0 3 4 0 4 2 0 4 2 5 0 5 4 3 2 1 Vidimo, da sta edina obrnljiva elementa kolobarja Z6 Stevili 1 in 5. Pri tem, kot vedno, velja 1-1 = 1. Nekoliko nenavadna pa je enakost 5-1 = 5. Vpra sajmo se torej, ali znamo za dano naravno stevilo n ugotoviti, kateri elementi kolobarja Zn so obrnljivi, ne da bi izračunali celotno tabelico množenja. Odgovor se skriva v naslednjem izreku. Izrek 12.22 Neničelni element a kolobrja Zn je obrnljiv, ce in samo če je tuj proti številu n. Dokaz: Problem prevedimo na obicajne operacije med celimi stevili. Element a G Zn je obrnljiv v Zn, ce in samo ce obstaja stevilo x, za katerega je ax = 1 (modn), oziroma, ce in samo ce obstajata celi stevili x in y, za kateri je ax — 1 = ny. Taks ni stevili pa obstajata, ce in samo ce je re sljiva naslednja diofantska enacba ax — ny = 1. (*) Kot vemo, pa ima zgornja enacba resitev, ce in samo ce sta stevili a in n tuji. S tem je izrek dokazan. I Dokaz pa nam je povedal tudi, kako inverz danega elementa dejansko izracunati. Potrebno je res iti diofantsko enacbo (*) in po potrebi poiskati tisto resitev, za katero je x na intervalu med 0 in n — 1. (Premisli, da lahko tak sno re sitev vedno najdemo.) Zgled. Izračunaj 31-1 v Z365 Resiti moramo difantsko enacbo 31x — 365y = 1. To lahko storimo z razsirjenim Evklidovim algoritmom. ■ Koliko obrnljivih elementov pa premore kolobar Zn? Kot pravi izrek 12.22, natanko toliko, kot je naravnih s tevil med 1 in n — 1, ki so tuja s tevilu n. Stevilo taksnih stevil je tako pomembno, da nosi svoje ime. 12.8 Eulerjeva funkcija Definicija 12.23 Naj bo n poljubno naravno stevilo, večje ali enako 2. Stevilo tistih naravnih stevil med 1 in n — 1, ki so tuja n, označimo z p(n). Dodatno definiramo se p(1) = 1. Tako definirani funkciji p: N ^ N rečemo Eulerjeva funkcija. Trditev 12.24 Ce je p praštevilo in r poljubno naravno število, je p(pr) = Pr — Pr-1 = pr-1(p — 1) = pr (1 — -). p Ce sta a in b tuji naravni števili, je p(ab) = p(a)p(b). Zgornja trditev nam omogoča, da izračunamo Eulerjevo funkcijo p(n) za vsako naravno stevilo n, če ga le znamo razčepiti na prafaktorje. Namreč, če je ai ao ak n = Pi p22•••pfck razčep stevila n na prafaktorje, tedaj je p(n) = p^1 )p(p22) ■ ■ ■ p(p2k) = Pi1 (1 — PL)P22 (1 — p-) ■ ■ ■ P2k (1 — p1) = k p 1 p2 k pk = n(1 — PL)(1 — P_)... (1 — PL). p1 p2 pk 12.9 Mali Fermatov izrek in Eulerjev izrek Izrek 12.25 (Fermat) Naj bo p praštevilo in a naravno število, tuje p. Tedaj je ap-1 = 1 mod p. Opomba. Zgornji izrek lahko povemo tudi v jeziku kolobarjev ostankov. Izrek namreč pravi, da za vsako prastevilo p in element a G Zp \ {0} velja ap-1 = 1. Dokaz: Oglejmo si elemente a, 2a, 3a,..., (p — 1)a of Zp. C e sta dva izmed njih enaka, denimo ia = ja, potem z mnozenjem z a-1 v Zp dobimo i = j (spomni se, da je element a v Zp obrnljiv, če je tuj proti p. S tem smo dokazali, da so zgoraj nasteti elementi paroma različni, in ker jih je ravno p — 1, tvorijo mnozičo vseh neničelnih elementov v Zp: {a, 2a, 3a,..., (p — 1)a} = {1,2,3,... ,p — 1}. C e zmnozimo vse elemente mnozic na levi in desni strani enakosti, dobimo naslednjo enakost v Zp: (p — 1)! = 1 ■ 2 ■ 3 ••• (p — 1) = a ■ 2a ■ 3a •• ■ (p — 1)a = (p — 1)!ap-1. Vendar (p — 1)! je tuj proti p, zato ga smemo iz leve in desne strani enakosti v Zp pokrajsati. Od to dobimo enakost ap-1 = 1 v Zp. I Zgornji izrek pa lahko nekoliko posplosimo. Najprej opazimo, da je <^(p) = p — 1 za vsako prastevilo p. Zato lahko izraz ap-1 interpretiramo tudi kot a^(p). Ob tej interpretaciji se izkaze, da lahko pogoj, da je p prastevilo, izpustimo. Velja namrec naslednji izrek. Ižrek 12.26 (Euler) Naj bo n poljubno naravno stevilo in a stevilo, ki je tuje n. Tedaj je a^(n) = 1 mod n. Opomba. V jeziku kolobarjev ostankov zgornji izrek pravi, daje a^(n) = 1 za vsak obrnljiv element a G Z^. Dokaz Eulerjevega izreka je na las podoben dokazu malega Fermatovega izreka, le da namesto s stevili a, 2a,..., (p — 1)a pricnemo z elementi za, kjer z pretece vse obrnljive elemente iz Z^. Podrobnosti dokaza lahko izdela bralec sam. Zgled. S pomočjo Eulerjevega izreka izračunaj 18401995 mod 26 Najprej izracunamo 1840 mod 26 = 20. Zato 18401995 = 201995 mod 26. Ker 20 ni tuje 26, Eulerjevega izreka ne moremo uporabiti takoj. Zato 201995 pisemo kot 41995 ■ 51995. Za razcep 20 = 4 ■ 5 smo se odlozili zato, ker je 5 med delitelji stevila 20 najvecji, ki je tuj 26. Ker je gcd(5, 26) = 1, lahko stevilo 51995 mod 26 izracunamo neposredno s pomocjo Eulerjevega izreka. Ker je ^>(26) = 12, najprej zapi semo 1995 = 12 ■ 166 + 3 in od tod dobimo 51995 = (512)166 ■ 53 = 53 = 21 (mod 26). Pri racunanju ostanka 41995 mod 26 moramo biti nekoliko iznajdljivej s i. Najprej zapisemo 41995 = 23990 in oznacimo x = 23990 mod 26. Tedaj je x = 23990 — 26q, kjer q = 23990 div 26, in zato x = 2y za neko naravno stevilo y. Od tod dobimo 2y = 23990 (mod26), od koder sledi y = 23989 (mod 13), in zato y = 23989 mod 13. Slednji ostanek pa lahko izracunamo s pomocjo Eulerjevega izreka (oziroma celo s pomocjo Fermatovega malega izreka). Ker je p(13) = 12 in 3989 = 332 ■ 12 + 5, je 23989 = 25 = 6 mod 13, in torej y = 6 in x = 12. S tem smo dokazali kongruenco 41995 = 12 (mod 26). Racun zakljucimo takole: 18401995 = 201995 = 41995 ■ 51995 = 12 ■ 53 = 60 ■ 25 = 8 ■ (—1) = 18 (mod 26). 12.10 Kriptografski sistem RSA Za zgled uporabe modularne aritmetike si oglejmo kriptografsko metodo, imenovano RSA, ki omogoca posiljanje tajnih sporocil med vec udelezenci, pri cemer vsebino tajnega sporocila lahko razbere le tisti, ki mu je bilo sporocilo poslano. Sistem RSA sodi med kriptografke sisteme z javnim kljucem. Posebnost teh sistemov je, da vsak udelezenec komunikacije, ki zeli prejemati tajna sporocila od ostalih udelezencev, javno objavi svoj javni ključ (geslo), ki ga ostali uporabijo za sifriranje njemu namenjenih sporocil, v tajnosti pa ohrani svoj privatni ključ, ki je potreben za desifriranje sporocil, ki so bila zasifrirana z njegovim javnim kljucem. Varnost metode sledi na dejstvu, da je iz posameznikovega javnega kljuca zelo tezko (prakticno neizvedljivo) izracunati njegov privatni kljuc. Opi simo na kratko, kaj mora storiti oseba A, ki bi od osebe B zelela prejeti tajno sporocilo. • Najprej nakljucno izbere dve prastevili, p in q, ter izracuna n = pq, p = p(n) = (p — 1)(q — 1). Za varnost sistema je zelo pomembno, da sta prastevili p in q tako veliki, da stevila n nihce, razen osebe A, ne zna razcepiti na produkt prastevil. Danes se v praksi uporabljajo vsaj 100 mestna prastevila, kjer pa je potrebna vecja varnost, pa se vecja prastevila. • Izbere poljubno stevilo e G Z*v (stevilo med 1 in p — 1, ki je tuje p) in s pomočjo raz sirjenega Evklidovega algoritma izračuna inverz d = e-1 G Z£. V praksi stevilo e izbremo tako, da naključno izberemo stevilo med 1 in p — 1, nato pa z razsirjenim Evklidovim algoritmom testiramo, ali je stevilo e res tuje stevilu p; če ni, postopek izbire stevila e ponovimo. Kot bomo videli kasneje, nekatere vrednosti stevila e niso najboj se (na primer, e = 1), zato zavrnemo tudi morebitne taksne naključne izbire. • Javno objavi stevili n in e (javni ključ), sam pa varno shrani stevilo d (privatni ključ). Ostale podatke "pozabi". Zdaj pa si oglejmo, kaj mora storiti oseba B, ki zeli osebi A poslati tajno sporočilo. • Svoje tekstovno sporočilo najprej pretvori v stevilo m G Zn. To stori na javno znan način in tako, da bo vsak, ki bo poznal stevilo m, brez tezav rekonstruiral začetno tekstovno sporočilo. Ce je tekstovno sporočilo predolgo, ga najprej razbije na manj se dele, jih pretvori v zaporedje stevil v Zn, in izvede spodaj opisani postopek za vsak člen tega zaporedja. • Prebere javni ključ (n, e) osebe A, izračuna stevilo c = me mod n in ga poslje osebi A. Ko oseba A prejme stevilo c, uporabi svoj privatni ključ d in izračuna stevilo m' = cd mod n. Izkaze se, daje stevilo m' kar enako originalnemu stevilu m. Nazadnje oseba A iz s tevila m' = m rekonstruira tekstovno sporočilo osebe B. Vidimo, da čelotna metoda temelji na naslednji trditvi. Trditev 12.27 Naj bosta p in q različni praštevili in naj bo n = pq ter p = (p — 1)(q — 1). Nadalje, naj bo e poljuben obrnljiv element kolobarja Zv in d = e-1 G Z^ njegov inverz. Tedaj za vsako celo število m, 1 < m < n — 1, iz enakosti c = me mod n sledi enakost cd mod n = m. Dokaž: Ker je d inverz elementa e v Z^, obstaja celo stevilo x, za katerega je ed — x^> = 1. Tedaj cd = med = m1+x^ = m ■ (m^)x mod n. C e je gcd(m,n) = 1, potem iz Eulerjevega izreka sledi m^ = 1mod n, in zato cd = m mod n. Predpostavimo torej lahko, da m ni tuj n. To se zgodi le, ce bodisi p bodisi q deli stevilo m. Brez izgube splosnoti lahko predpostavimo, da je m veckratnik stevila p. Tedaj je tudi stevilo cd = med deljivo s p, in zato cd = m = 0 mod p. Ker m ni hkrati deljiv tudi s q (saj bi sicer ne bil manjsi od n), smemo uporabiti Fermatov izrek in ugotoviti, da je mq-1 = 1 mod q. Zato velja cd = med = m1+^ = m ■ (m(q-1))(p-1)x = m mod q. Od tod sledi, da imata stevili cd mod n in m enaka ostanka pri deljenju s p kot tudi pri deljenju s q. Ni tezko videti, da imata tedaj enaka ostanka tudi pri deljenju z n = pq. Ker sta obe stevili manj si ali enaki n, sta zato enaki. Kombinatorika Kombinatorika je s iroko podrocje, ki se ukvarja predvsem s koncnimi mate-maticnimi objekti. Osrednji vpra sanji, ki si jih zastavlja kombinatorika, sta obstoj in generiranje objektov s predpisanimi lastnostmi in pa stevilo tak snih objektov. V na sem hitrem pregledu kombinatorike se bomo osredotocili predvsem na slednje vprasanje. V prvem razdelku bomo obravnavali vpras anja tipa "Na koliko nacinov lahko izberemo k kroglic iz skatle z n kroglicami". Obravnavali bomo vec razlicicah tega vpra sanja. 13 Izbori Razdelek pricnimo z naslednjim zgledom. Pri igri loto se v bobnu nahaja 39 kroglic, o stevilcenih s stevili 1, 2, . . . , 39. Organizator igre iz bobna zaporedoma sedemkrat izvlece po eno kroglico. Na koliko nacinov lahko to stori? Odgovor je odvisen od tega, kako razumemo besedo "nacin". Osnovni dilemi pri razumevanju naloge sta naslednji: Prva dilema je, ali kroglico, ki smo jo v posameznem koraku izvlekli, vrnemo v boben - od tega je namrec odvisno, ali lahko posamicno kroglico izvlecemo veckrat ali morda najvec enkrat. Druga dilema pa je, ali je za nas vrstni red izvlecenih kroglic pomemben - konkretneje, ali naj razlikujemo med izboroma sicer iste mnozice kroglic, na primer {2, 6, 7,13,19, 21, 35}, kjer v prvem primeru kroglice izvlecemo v vrstnem redu 2,13, 35, 7, 6, 21,19, v drugem pa v dru-gacnem vrstnem redu, denimo, 35,13, 7, 6, 21,19, 2? Ti dve dilemi mora seveda razre siti tisti, ki nam je nalogo zastavil. Od njegovega odgovora je odvisno, kako bomo nalogo re sevali. Kadar je za zastavljalca naloge vrstni red pomemben, bomo pre stevali urejene izbore (tudi variacije) izvlecenih kroglic - bodisi s ponavljanjem (ce kroglice vracamo) bodisi brez ponavljanja (ce kroglic ne vracamo). Ce pa vrstni red ni pomemben, bomo steli neurejene izbore (tudi kombinacije) kroglič - spet bodisi s ponavljanjem bodisi brez ponavljanja. V nadaljevanju si bomo ogledali vsako od stirih moznih interpretačij naloge nekoliko podrobneje. Za lazjo izrazavo bomo rezultat vlečenja kroglič imenovali zreb. Mnozičo 39 kroglič označimo z N = {1,2,...,39}. 13.1 Urejeni izbori s ponavljanjem Denimo, da izvlečene krogliče v boben vračamo, vrstni red izvlečenih kroglič pa je pomemben. Tedaj lahko rezultat zreba enolično predstavimo z urejeno sedmerico elementov mnoziče kroglič N, pri čemer urejeno sedmeričo (a1, ..., a7) razumemo kot tisti zreb, pri katerem v i-tem poskusu izvlečemo krogličo ai G N. To nas napelje na idejo, da urejen izbor s ponavljanjem definiramo na naslednji način. Definicija 13.1 Naj bo N poljubna mnoziča z n elementi in r poljubno naravno stevilo. Urejeni r-teriči (a1, a2,..., ar) elementov mnoziče N rečemo urejeni izbor elementov množice N dolžine r. C e zelimo poudariti, da so lahko nekateri izmed elementov ai med seboj tudi enaki, dodamo, da gre za urejeni izbor s ponavljanjem.. Mnozičo vseh taksnih izborov označimo s simbolom V (N, r). Trditev 13.2 Naj bo N poljubna mnozica z n elementi in r poljubno naravno stevilo. Tedaj mnozica V (N, r) premore nr izborov. Dokaz: V to se najlazje prepričamo z indukčijo na dolzino izbora r. C e je r = 1, je tipični izbor oblike (a), kjer je a element mnoziče N. Ker je elementov mnoziče 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! Označimo elemente mnoziče N s simboli a1,..., an. Izbore iz V (N, k + 1) razvrstimo v n skupin, R1,..., Rn, pri čemer v skupino Ri razvrstimo vse izbore, ki imajo na prvem mestu element ai. C e izboru (ai, x1,..., ) iz mnoziče Ri odrezemo prvo komponento, dobimo "ostanek" (x1,..., ), ki je izbor iz V (N, k). Pri tem se vsak izbor iz V (N, k) pojavi natanko enkrat kot "ostanek" izbora iz skupine Ri. Zato je v vsaki skupini Ri natanko toliko izborov, kot je izborov v mnoziči V (N, k); teh pa je, kot zagotavlja indukčijska predpostavka, nk. Skupaj imamo torej nkn = nfc+1 = nr izborov. S tem je indukčijski korak dokazan. I Opomba. Ce so Ai,..., Ar poljubne mnozice, tedaj množici vseh urejenih r-teric oblike (xi,..., xr), xj G Aj, recemo kartezični produkt mnozic Ai,...,Ar in jo oznacimo s simbolom A1 x ... x Ar. C e so vse mnozice Aj enake neki fiksni množici A, tedaj govorimo o kartezični potenci, ki jo oznacimo z Ar. Mnozica V (A, r) ni tako nic drugega kot kartezicna potenca Ar. Trditev, ki smo jo dokazali zgoraj, se posplosi do dejstva, da je moc kartezicnega produkta mnozic enaka produktu moci mnozic, ki nastopajo v produktu. 13.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 13.3 Urejeni r-terici paroma razlicnih elementov mnozice N recemo urejeni izbor elementov mnoziče 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 pre stejemo, vpeljimo naslednji funkciji nravnih stevil n in r: nr = n(n — 1) ■ ■ ■ (n — r + 1), n! = nn = n(n — 1) ■ ■ ■ 1 in dodatno definirajmo s e n0 = 0! = 1 za vsak n G No. Simbolu nr recemo padajoča potenča stevila n, simbolu n! pa n fakulteta (tudi faktoriela). Trditev 13.4 Naj bo N poljubna mnozica z n elementi in r poljubno naravno stevilo. Tedaj mnoZica V (N, r) premore nr izborov. Dokaz: Razmisljamo lahko povsem enako kot pri dokazu trditve 13.2. Za r = 1 trditev ocitno velja. V indukcijskem koraku definiramo mnozice Ri enako kot prej, le da v njih razporedimo le izbore brez ponavljanja. Opazimo, da je ostanek (x1,..., xn) tipicnega elementa (ai, x1,..., xk) G Ri izbor elementov mnozice N \ {ai} brez ponavljanja. Kot v dokazu trditve 13.2 uporabimo indukčijsko predpostavko in ugotovimo, da Ri premore nk izborov. Vseh iskanih izborov je tako n(n — 1)k = n k+1 _ Ce je |N| = r, se v urejenem izboru elementov mnoziče N dolzine r brez ponavljanja vsak element mnoziče N pojavi natanko enkrat. Taksnemu izboru rečemo permutacija mnoziče N. Iz trditve 13.4 neposredno sledi naslednje: Trditev 13.5 Stevilo vseh permutacij n-elementne množice je enako Opomba. Permutačijo (ai,..., an) mnoziče N lahko razumemo tudi kot linearno ureditev elementov mnoziče N, pri kateri je a1 "prvi" element, ki mu "sledi" element a2 in tako dalje, vse do "zadnjega" elementa an. C e pa so elementi mnoziče N ze vnaprej podani z nekim vrstnim redom (npr. če je N = {1, 2,..., n}) pa lahko na permutačijo (a1,...,an) pogledamo tudi kot na bijektivno preslikavo iz mnoziče N vase, ki i-temu elementu mnoziče N priredi element aj. nn = n!. 13.3 Neurejeni izbori brez ponavljanja Mislimo si sedaj, da vrstni red izbranih kroglič ni pomemben, izbranih kroglič pa ne vracamo v boben. V tem primeru lahko izid zreba enolično podamo z množico sedmih izzrebanih kroglič. Moznih izidov zreba je torej toliko, kot je vseh sedemelemntnih podmnozič mnoziče kroglič N. To nas napelje na naslednjo definičijo. Definicija 13.6 Naj bo N poljubna mnoziča z n elementi in r poljubno nenegativno čelo stevilo. Tedaj r-elementni podmnoziči mnoziče N rečemo neurejeni izbor elementov mnočice N brez ponavljanja dolčine r. Mnozičo vseh taksnih izborov označimo s simbolom K(N, r) njihovo stevilo pa s simbolom (n) = lK(N .r)|. ki mu pravimo binomski simbol (tudi binomski koeficient) in ga preberemo "n nad r". Trditev 13.7 Za poljubni nenegativni celi števili n in r velja enakost (n\ nr \r) r! Dokaž: Naj bo N poljubna n-elementna mnozica in r poljubno ne-negativno 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 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 taks nih izborov enako r!. Iz trditve 13.4 tedaj sledi enakost Delimo se z r! in dobimo formulo iz trditve. I 13.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 mnozica, dopusca pa veckratno pripadnost kakega elementa. Taks nemu objektu pravimo mul-timnoziča. 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 13.8 Multimnozica z elementi v mnozici A je poljubna preslikava ^: A ^ N0. Pri tem stevilu ^(a), a G A, 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 red elementov, tako kot pri mnozicah, ni pomemben. Na primer, multimnozico ^: {a, 6, c, d} ^ N0 ^(a) = 1, ^(6) = 2, ^(c) = 0, ^(c) = 3 lahko podamo tudi z nastevanjem elementov ^ = [6, c, c, a, c, 6] = [c, 6, c, 6, a, c] = ... ali ^ = [a1,62, c3] Moc multimnozice ^ je 6. Neurejene izbore s ponavljanjem lahko sedaj opisemo v jeziku multimnozic. Definicija 13.9 Naj bo A mnozica moci n. Multimnozici moci r z elementi v mnozici A recemo neurejeni izbor elementov mnoziče A dolzine r s ponavljanjem.. Mnozico vseh taks nih multimnozic oznacimo s simbolom K(A,r), njihovo stevilo pa s K(n, r). Trditev 13.10 Za poljubni nenegativni stevili n in r velja K(-)=(-+——-1)=(-+r— Dokaz: Vzemimo n-elementno mnozico A = {a1,...,an}. Trditev dokazemo na strog matematicen nacin tako, da najdemo bijektivno preslikavo iz mnozice K(A, r) v mnozico K(NNn+r-1,n — 1)1 Ker so mnozice, med katerimi obstajajo bijektivne preslikave, enako mocne, to res zado sca za dokaz prve enakosti v zgornji formulu. Drugi enacaj sledi neposredno iz lastnosti binomskih simbolov (glej razdelek 13.6). Naj bo ^: A ^ N0 multimnozica moci r. Za k G {1,..., n — 1} definira-jmo 6fc = ^(a1) + ... + ^(afc) + k 1Glej opombo, ki sledi trditvi 13.12. in jih zdruzimo v mnozičo BM = {b1, b2,..., bn-1}. Dokazimo najprej, da je B^ elementna podmnoziča mnoziče Nn+r-1 in da premore n — 1 elementov. Ker je bfc+1 = bk + Mafc+1) + 1 za vsak k > 1, je zaporedje s tevil bk strogo nara s čajoče. Ker je b1 = ^(a1) + 1 > 1, so stevila bk pozitivna. Po drugi strani pa je n bn-1 = ^1) + ... + Man-1) + n — 1 < £ ^(afc) + n — 1 = r + n — 1. (*) k=1 Zato je res BM element mnoziče K(Nn+r-1,n — 1). Dokazimo zdaj, da je preslikava $: K(A,r) ^K(Nn+r-1,n — 1), = BM, bijekčija. Surjektivnost dokazemo tako, da vzamemo poljubno (n — 1)-elementno podmnozičo B C Nn+r-1, uredimo njene elemente bk po velikosti, b1 < b2 < ... < bn-1, in resimo sistem enačb izhajajoč iz prvega enačaja formule (*) na neznanke ^(ak). Dobimo: MaO = b1 — 1, ^(ak) = bk — bk-1 — 1 za k > 2. Za tako določeno multimnozičo ^ G K(A, r) očitno velja BM = B. S tem je surjektivnost preslikave $ dokazana. Injektivnost sledi iz dejstva, da so stevila bk v formuli (*) natanko določajo vrednosti ^(ak). I Na konču poglavja se vrnimo k na si začetni nalogi o stevilu moznih zrebov sedmih kroglič. Pri vseh stirih različičah naloge prestevamo izbore elementov mnoziče z n = 39 elementi dolzine r = 7. Ce je vrstni red izvlečenih kroglič pomemben, krogliče pa vračamo v boben, stejemo urejene izbore s ponavljanjem. Teh je - v skladu s trditvijo 13.2 - natanko 397 = 137231006 679. C e je vrstni red izvlečenih kroglič pomemben, kroglič pa ne vračamo v boben, stejemo urejene izbore brez ponavljanja. Teh je - v skladu s trditvijo 13.4 - natanko 397 = 77 519 922 480. C e vrstni red izvlečenih kroglič ni pomemben, krogliče pa vračamo v boben, stejemo neurejene izbore s ponavljanjem. Teh je - v skladu s trditvijo 13.10 - natanko '39 + 7 — 1\ /45 . „ , = 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 13.7 - natanko 39\ 397 7 J =37^ = 15380937. 13.5 Permutačije multimnoZic Naj bo ^: A ^ N0 multimnozica moci n. Urejeni n-terici (x1,...,xn), v kateri se vsak element a G A pojavi natanko ^(a)-krat, recemo permutacija multimnozice Trditev 13.11 Naj bo ^ multimnozica moči n z elementi x1,..., in krat-nostmi = n». Tedaj je število permutačij multimnozice ^ enako n n! n1,...,nfc/ nj ••• nfc! Dokaž: Za vsak i{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,x2,x3}, potem iz permutacije ((x2, 3), (x1, 1), (x2, 1), (x2, 2), (x2, 2), (x2, 1)) mnozice X dobimo permutacijo (x2,x1,x2,x2,x2,x2) 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 ^ n!/n1! ■ ■ ■ nk!. I 13.6 Binomski simboli in Pascalov trikotnik Oglejmo si nekaj zanimivih lastnosti binomskih simbolov, ki smo jih vpeljali v razdelku 13.3. Najprej opazimo, da lahko formulo iz trditve 13.7 podamo v naslednji "neokraj sani" obliki: Z računskim postopkom smo tako pris li do enakosti med stevili, ki pa imajo, kot sledi iz definičije 13.6 in trdtive 13.7, tudi kombinatorično inter-pretačijo: Trditev 13.12 Naj bo N poljubna n-elementna množica. Tedaj je r-ele-mentnih podmnožic množice N enako mnogo kot (n-r)-elementnih podmnožic množice N. Zgornje dejstvo niti ni tako presenetljivo, saj bi do njega lahko pri sli tudi z naslednjim neposrednim premislekom: Vsaki r-elementni podmnoziči A C N priredimo njen komplement AC C N. Komplement AC tedaj steje n — r elementov. Na ta način vsaki r-elementni podmnoziči priredimo neko (n — r)-elementno podmnozičo mnoziče N. Ker sta komplementa AC, BC dveh različnih podmnozič A = B tudi sama različna, in ker je vsaka (n — r)-elementna podmnoziča mnoziče N komplement kake r-elementne podmnoziče (saj je enaka komplementu svojega komplementa), je s tem zgornja trditev dokazana. Opomba. Načelo, ki ga uporabili na konču zgornjega premisleka, je zelo pomembno kombinatorično načelo in ga lahko povzamemo takole: Ce med mnozičama A in B najdemo bijektivno preslikavo, tedaj mnoziči A in B premoreta enako mnogo elementov. Temu preprostemu načelu rečemo tudi nacelo enakosti. Vlogo mnozič A in B v zgornjem premisleki igrata mnoziči A = K(N, r) in B = K(N, n — r), vlogo bijekčije med A in B pa preslikava, ki mnozičo A gA preslika v njen komplement C e za r v zgornji formuli vstavimo n — r dobimo naslednjo enakost: AC. Trditev 13.13 Za poljubni števili n, r g No, r < n, velja: Dokaz: Navedimo dva dokaza te trditve. Prvi je povsem računski in temelji na formuli iz trditve 13.7. Računajmo: n\ + / n \ nr + (r + 1)nr + 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 kombinatoričen in upoSteva le dejstvo, da je (n) 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. Pre stejmo se one iz prve skupine: vsaki podmnozici A iz prve skupine priredimo mnozico A' = A\{n + 1}. Ker A po predpostavki vsebuje element n + 1, je A' r-elementna podmnozica mnozice N \ {n + 1}. C e sta A in B dve razlicni mnozici iz prve skupine, sta tudi mnozici A' in B' razlicni. Po drugi strani pa je vsaka r-elementna podmnozica mnozice N\ {n +1} enaka A' za neko mnozico A iz prve skupine (namrec kar za A = A' U {n + 1}). S tem smo dokazali, da je preslikava, ki mnozici A priredi A' = A \ {n + 1} bijektivna preslikava med prvo skupino mnozic in mnozico vseh r-elementnih podmnozic mnozice N\{n+1}. Ker je slednjih , je toliko tudi podmnozic iz prve skupine. V obeh skupinah skupaj je torej + (r+J podmnozic. Po drugi strani pa obe skupini podmnozic skupaj tvorita mnozico vseh (r + 1)-elementnih podmnozic (n + 1)-elementne mnozice N, za katere pa vemo, da jih je (^+1). Enakost je s tem dokazana. I Formula iz trditve 13.13 nosi ime Pascalova identiteta. Omogoca nam racunati binomske koeficiente rekurzivno s pomocjo sheme, ki ji recemo Pascalov trikotnik. Shema ima obliko enakokrakega trikotnika, ki ga gradimo iz "gornjega" oglisca "navzdol" tako, da na skrajni mesti vsake vrstice najprej vpi s emo s tevilo 1, "notranjost" vrstice pa zapolnimo tako, v vsako prazno mesto vpi semo vsoto stevili, ki stojita levo in desno diagonalno nad praznim mestom. Pri tem prvo vrstico, v kateri stoji le ena stevilka, namrec 1, imenujemo 0-to vrstico, 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 stevilo nr . Naslednja zanimiva lastnost binomskih koefičinetov sledi iz dobro znane binomske formule, ki pravi, da za poljubni realni stevili x in y ter poljubno naravno stevilo n velja enakost (x + y)n = jr (n)xn-ryr. r=0 r Trditev 13.14 r o r=0 r (—D- (n) r=0 Dokaz: Prvo trditev dobimo, če v binomsko formulo vstavimo x = y = 1, druga pa, če vstavimo x = 1 in y = —1. I Od tod z lahkoto izpeljemo naslednji rezultat. Trditev 13.15 Naj bo N poljubna n-elementna mnozica in PN mnozica vseh njenih podmnozic. Tedaj je |PN| = 2n. Dokaz: Seveda je PN = U=0K(N, r), saj se vsaka pomnoziča A mnoziče N pojavi v kaki (natanko eni) mnoziči iz K(N, r), namreč tisti, pri kateri je r = |A|. Ker so si mnoziče v uniji desno od enačaja paroma tuje, je moč mnoziče na levi enaka vsoti moči mnozič na desni. I Zgled. S pomočjo izpeljanih trditev rešimo nekaj preprostih prestevalnih nalog. 1. Koliko besed dolzine 3 lahko sestavimo iz 25 črk slovenske abecede. Koliko od teh je taksnih, da se nobena crka ne ponovi. 2. Koliko 8-mestnih varnostnih gesel lahko sestavimo iz nabora stevilk 0, 1,..., 9 ter velikih in malih crk angleske abecede, ce mora geslo vsebovati vsaj eno stevilko? = 2n; 0. 3. Varnostno geslo je sestavljeno iz sedem ali osem znakov, kijih izbiramo med 25 crkami in 10 stevkami. Geslo mora vsebovati vsaj pet crk in vsaj eno stevko. Koliko takšnih varnostnih gesel obstaja? 4. Koliko besed lahko dobimo s premetavanjem crk besede "cmrlj"? ReSitve: 1. Besedo dolzine 3 si predstavimo kot urejeni izbor crk slovenske abecede dolzine 3. Ce se crke smejo ponavljati, uporabimo trditev 13.2 in zakljucimo, da je iskanih besed natanko 252 = 15 625. C e se crke ne smejo ponavljati, pa uporabimo trditev 13.4 in dobimo rezultat 252 = 13 800. 2. Pre stejmo najprej vsa gesla, vkljucno s tistimi, ki ne vsebujejo nobene stevilke. Tak sno geslo lahko predstavimo kot poljuben urejen izbor s ponavljanjem dolzine 8, pri cemer elemente izbiramo iz mnozice stevilk in velikih ter malih crk angleske abecede. Ker angleska abeceda steje 26 znakov, je vseh razpolozljivih simbolov 10+2-26 = 62. Vseh gesel je zato 628. Da dobimo stevilo dopustnih gesel (torej tistih, ki vsebujejo vsaj eno s tevilko), moramo od tega odsteti s tevilo "slabih" gesel, torej tistih, ki so sestavljena zgolj iz crk. Teh je po enakem premisleku 528. Odgovor na zastavljeno nalogo je torej 628 — 528 = 164 880377053440. 3. Naj Am,n oznacuje mnozico gesel, sestavljenih iz m crk in n stevk. Geslo zadosca pogojem naloge natanko tedaj, ko pripada kaki od mnozic A5,2, A6,1, A5,2, A6,2 in A7,1. Ker so te mnozice paroma dis-junktne, je iskano stevilo enako vsoti njihovih moci. Izracunajmo zdaj moc mnozice Am,n za poljubni par m, n. Elemente mnozice Am,n bomo razvrstili v nekaj podmnozic glede na to, na katerih mestih v geslu se nahajajo stevke. Natancneje, za vsako n-elementno mnozico J C Nm+n naj bo Mj mnozica vseh tistih gesel iz Am,n, ki ima na k-tem mestu s tevko natanko tedaj, ko je k G J. Mnozico M j si lahko sedaj predstavljmo kot kartezicni produkt mnozic C1 x ... x Cm+n, kjer je Ck mnozica stevk, ce je k G Mj, in je Ck mnozica crk sicer. Sledi, da je |Mj| = 25m10n. S pomocjo nacela vsote dobimo: |Am,n| = E |Mj| = (m + n) 25m10n. Iskano stevilo gesel je torej enako |A5,2| + |Aa,1| + |A5,3| + |A6,2| + IA7.1I = ^ -255-102 + Q -256.10+-255-103 + -256-102 + Q-257-10 « 1,7 ■ 1012. 4. Ker se nobena črka v besedi "čmrlj" ne ponovi, je premetank te besede ravno toliko, kot je permutačij mnoziče črk č, m, r, l, j, torej 5! = 120. 14 Razbitja množic in razčlenitve stevil 14.1 Stirlingova stevila druge vrste Mnozici paroma disjunktnih nepraznih mnozic A1,...,A^, katerih unija je enaka mnozici A, recemo razbitje mnozice A. Stevilu vseh razbitij n-elementne mnozice A na k nepraznih podmnozic recemo Stirlingovo stevilo druge vrste in ga oznacimo z S(n, k). Ocitno velja S(n, k) = 0 za k > n , S (n, n) = 1 in S(n, 1) = 1. Dodatno definiramo s e S(n, 0) = 0 za vsak n > 1 in S(0,0) = 1. Trditev 14.1 Za vsak par naravnih števil n, k, 1 < k < n velja S (n, k) = S (n — 1, k — 1) + kS(n — 1, k). Dokaz: Naj bo N = {x1,..., xn} poljubna mnozica, R mnozica vseh razbitij mnozice A 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 ax iz mnozice N izrezemo. Tedaj razbitje R preide v razbitje R' = {A1 \ {xra},..., Afc \ {xra}} mnozice N \ {xra}. 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 mnozice (n — 1)-elementne mnozice N\ {xn} na k — 1 nepraznih podmnozic. Obratno, vsako razbitje T = {A'1,...,A/fc_ 1} mnozice N\ {xn} na k — 1 nepraznih podmnozic lahko z vkljucitvijo mnozice {xn} dopolnimo do razbitja R = {{xra},A1 ...,A/_ 1} mnozice N. Ni tezko videti, da je R edino razbitje iz R0, za katero je R' = T. Zato je razbitij iz skupine R0 natanko toliko kot razbitij mnozice N \ {n} na k — 1 nepraznih podmnozic, torej S (n — 1, k — 1). Ce pa razbitje R sodi v skupino R1, tedaj nobena od mnozic rabitja R' ni prazna, kar pomeni, da je R' razbitje mnozcie N \ {xn} na k nepraznih podmnozic. C e vzamemo poljubno razbitje T = {A1,..., A/} mnozice N \ {xn} na k nepraznih podmnozic, lahko z vkljucitvijo elementa {xn} va katero koli od k mnozic Ai dobimo razbitje R iz skupine R1, za katerega je R' = T. Tako dobljena razbitja R so hkrati edina, za katere je R' = T, kar pomeni, daje vseh razbitij iz skupine R1 natanko k-krat toliko, kot je razbitij (n — 1)-elementne mnozice N\ {xn} na k-nepraznih podmnozic, torej kS(n — 1, k). Trditev sedaj z lahkoto sledi, saj je |R| = |R0| + |Ri | = S(n -1, k - 1) + kS (n - 1, k). ■ Rekurzivna formula nam omogoča, da Stirlingova Stevila 2. vrste računamo podobno kot binomske koeficiente. Sestavimo tabelo, v kateri na preseči s ču 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 začetnih pogojev sledi, da so nad glavno diagonalo same ničle, po diagonali same enke, v prvem stolpču pa, razen pri prvem elementu, zopet same ničle. 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 lezi v vrstiči 6 in stolpču 4, smo torej dobili tako, da smo sesteli 25 (levo zgoraj) in 4 ■ 10 (smo v stolpču 4, nad iskanim stevilom pa stoji 10). 14.2 Lahova stevila 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) razbitjana 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 mozni mnoziči. Po drugi strani pa razbitje {{a}, {b, c, d}} porodi 3! = 6 porodi 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 se L(n, 0) = 0 za vsak n > 1 in L(0,0) = 1. Podobno kot pri Stirlingovih s tevilih 2. vrste lahko tudi za Lahova s tevila izpeljemo rekurzivno zvezo. Izpeljava se razlikuje zgolj v tem, da tu pri stetju razbitij iz skupine R1 iz danega razbitja T = {A'1,...,A'k mnoziče N \ {xn} lahko najdemo n — 1 + k razbitij R iz skupine R1, za katera je R' = T; izbrisani element xn lahko namreč vrinemo v katero koli mnozičo Ai na eno od |Ai| + 1 razpolozljivih mest (za vse elemente mnoziče Ai ali pa pred kakega od |Ai| elementov mnoziče A). Element xn lahko torej vrinemo v razbitje na (|A1| + 1) + (|A2| + 1) + ... + (|Ak| + 1) načinov, kar znese n — 1 + k. Od tod seldi naslednja trditev. Trditev 14.2 Za 1 < k < n velja L(n, k) = L(n — 1, k — 1) + (n + k — 1)L(n — 1, k). Z indukčijo na stevilo n in z uporabo rekurzivne formule iz trditve 14.2 lahko izpeljemo tudi ekspličitno formulo, ki Lahova stevila izrazi s pomočjo binomskih simbolov. Trditev 14.3 Za 1 < k < n velja r, ,, /n — 1\ n! /n\ (n — 1)! L(n,k) = 1 1 k — 1) k! \k) (k — 1)! Podobno kot pri binomskih simbolih in Strilingovih stevilih 2. vrste, lahko tudi Lahova stevila računamo s pomočjo sheme, ki izhaja iz rekurzivne zveze. V spodnji tabeli na presečisču n-te vrstiče in k-tega stolpča 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 vrstiči 5 in stolpču 2, smo torej dobili tako, da smo sesteli 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 predznacena Lahova .stevila, definirana s formulo L'(n,k) = (—1)nL(n,k). 14.3 Stirlingova Stevila prve vrste Stirlingovo stevilo prve vrste s(n,k) stejeje razbitja n-elementne mnozice na k nepraznih ciklicno 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)!. Stirligova stevila za mejne pare stevil n in k zadoscajo enakostim s(n, k) = 0 za k > n , s(n, n) = 1 in L(n, 1) = (n — 1)!. Dodatno definiramo s e 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 ničle. V skladu z rekurzivno formulo izračunamo stevilo s(n, k) v tabeli dobimo tako, da sestejemo stevilo, ki stoji levo zgoraj nad njim, in (n — 1)-kratnik stevila, ki stoji neposredno nad njim. Na primer, na presečisču vrstiče 5 in stolpča 3 dobimo vsoto stevila 11 (levo zgoraj) in stevila (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 srečamo tudi predznacena Stirlingova stevila prve vrste, ki so definirana s formulo s'(n, k) = (—1)n-k s(n, k). 14.4 Stevilo razbitij naravnega Stevila Zaporedju (neničelnih) naravnih stevil m1 < m2 < ... < mk, katerih vsota je enaka n, rečemo razclenitev naravnega stevila n na k clenov. Stevilo vseh taksnih razčlenitev označimo s pk (n). Očitno je Pk(n) = 0 za k > n. Dodatno definiramo p0(0) = 1 in p0(n) = 0 za n > 0. Trditev 14.4 Za vsak par naravnih stevil n, k velja Pk (n) = Pk-1(n — 1) + pk (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. Ce razčlenitvi iz mnoziče R0 odvzamemo prvi element m1 = 1, dobimo razčlenitev s tevila 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 | R01 = Pk-1(n — 1). Razčlenitev (m1,... ,mk) G R1 lahko spremenimo v razčlenitev s tevila n — k na k sumandov, če vsak mi zmanj samo za 1. Ker vsako razčlenitev stevila n — k na k sumandov dobimo na taksen način natanko enkrat, je |Ri| = Pfc(n — k). Od tod dobimo p;(n) = |Ro| + |Ri| = Pfc-i(n — 1) + pfc (n — k). ■ Računanje S tevil (n) si olajSamo, če sestavimo tabelo, v kateri na preseči sču n-te vrstice in k-tega stolpca stoji stevilo (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 (n) v tabeli dobimo tako, da se stejemo 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 15 Načelo vključitev 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 manj sa od vsote moci posameznih mnozic, saj pri se stevanju 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. 15.1 Unija dveh mnoZic Pricnimo s preprostim zgledom unije dveh mnozic A in B. C e 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|. 15.2 Unija poljubno mnogo mnoZic C e je mnozic vec, moc njihove unije racunamo s pomocjo naslednje trditve. Trditev 15.1 Naj bodo A1,..., An poljubne mnozice. Za k G {1,..., n} naj Sk = e | n Ai | je(Nn) iej označuje vsoto moCi presekov vseh k-teric mnozic Ai. Tedaj je | U Ai| = E(—1)k-1Sk. (*) — ^ k— 1 < i=1 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 (m) presekih niejAi za katere je |J| = k. To pa pomeni, da x za vsak k prispeva k desni strani enakosti (*) natanko (—1)k—1 (m), skupaj torej n / \ m / \ E (—/M m) = 1 + E (—11)k—1'( m) = !■ k=1 V ' k=0 V ' kjer smo pri zadnji enakosti uporabili trditev 13.13. S tem je trditev dokazana. Zgled. V krčmo na Divjem zahodu vstopi druščina n revolverasev. Ker je v salonu prepovedano nositi oroZje, pri vratih vsak odda svoj revolver. Zaradi objektivnih okolisčin so v nekem trenutku krčmo prisiljeni na hitro zapustiti, pri čemer vsak na .slepo zagrabi enega od n oddanih revolverjev. Koliksna je verjetnost, da nihče od revolverasev ni zagrabil svojega revolverja. Označimo revolverase z naravnimi stevili med 1 in n. Situačijo po odhodu iz salona lahko opi s emo z n-teričo (a1,..., an), kjer je aj zaporedna stevilka lastnika revolverja, ki gaje ob odhodu zagrabil i-ti revolveras. Ta n-teriča je očitno permutačija mnoziče Nn. Vseh moznih situačij po odhodu iz salona je torej n!. Koliko situačij pa je takih, da noben revolveras ne zagrabi svojega revolverja? Za i = 1,..., n naj bo Aj mnoziča tistih permutačij (a1,..., an) za katere je aj = i. Permutačije v Aj predstavljajo natanko tiste situačije, kjer je i-ti revolveras zagrabil svojo pistolo. Unija U™=1 Aj tedaj predstavlja mnozičo tistih situačij, kjer vsaj eden revolvera s zagrabi svojo pistolo. Nas zanima stevilo n! — | U™=1 Aj|. Opazimo, daje |njej Aj| = (n—k)!, za vsako indeksno mnozičo J G (Nn). Stevilo Sfc iz načela o vključitvah in izključitvah je tako enako s* = e m (nv—k)!=n. Zato je n n . n n! — |U Aj |= n! — £(—1)k-1 £ = n! £(—1)k k_. j=1 fc=1 fc=0 Iskana verjetnost je tako enaka alternirajoči vsoti —1)k 1 fc=0 E(—1) \k_ k!, kar je za dovolj velike n priblizno enako 0,37. 16 Dirichletovo načelo in sorodni izreki 16.1 Dirichletovo načelo C e razvrstimo n predmetov v več kot n skatel, bo vsaj ena od skatel vsebovala vsaj dva predmeta. To preprosto dejstvo imenujemo Dirichletovo nacelo2 Navedimo ga v nekoliko splos nej s i obliki. Izrek 16.1 Ce vec kot kn objektov razporedimo v n skatel, potem bo v vsaj eni skatli vec kot k objektov. Oglejmo si nekaj zgledov uporab Diričheltovega načela. Zgled. Vsak clovek ima na glavi najvec sto tisoc las. V Sloveniji gotovo zivi vec kot milijon petsto tisoc ljudi. Dokazite, da v Sloveniji obstaja skupina desetih ljudi, ki imajo na glavi enako .stevilo las. V mislih razdelimo prebivalče Slovenije v 100.001 skatlo, pri čemer v i-to skatlo (i = 0,1,..., 100.000) uvrstimo vse tiste ljudi, ki imajo natanko i las na glavi. Ker je vseh prebivalčev Slovenije več kot 10 ■ 100.001, nam osnovna oblika Diričhletovega načela pravi, da obstaja skatla, v kateri je več kot 10 ljudi (vstavi k = 10, n = 100.001). Seveda imajo vsi ljudje v tej skatli enako stevilo las na glavi. ■ Veliko nalog o deljivosti razlik čelih stevil lahko prevedemo na Diričh-letovo načelo, če upo stevamo dejstvo, da je razlika dveh čelih stevil deljiva z danim naravnim stevilom m, če in samo če dasta pri deljenju z m enak ostanek. C e se zavedamo, da je ostanek pri deljenju z m lahko le eno od m stevil 0,1,..., m — 1, zlahka resimo naslednjo nalogo: Zgled. Med 101 celim stevilom vedno lahko najdemo dve, katerih razlika je deljiva s 100. Mislimo si, da imamo na razpolago 100 skatel, ki jih označimo s stevili 0,1,..., 99. Danih 101 s tevil razporedimo v teh 100 s katel, pri čemer s tevilo x razvrstimo v skatlo i, če in samo če je ostanek stevila x pri deljenju s 100 enak i. Ker je stevil, ki jih razvr sčamo, več, kot je skatel, nam Diričhletovo načelo pravi, da obstaja skatla z vsaj dvemi stevili. Razlika teh dveh stevil je seveda deljiva s 100. ■ 2Johann Dirichlet (1805-1859), nemški matematik, utemeljitelj modernega koncepta funkcije. V angleško govoreCih deželah tukaj opisano Diricheltovo naCelo imenujejo tudi načelo golobnjaka (ang. pigeonhole principle). S tem še izognejo zamenjavi s pomembnim izrekom iž analize, ki prav tako nosi ime Dirichletovo nacelo. Zgled. Pobarvajmo vsak kvadratek neskončnega karirastega lista papirja z eno od desetih barv. Dokači, da obstajajo čtirje enako pobarvani kvadratki, katerih središča so ogličča pravokotnika s stranicami, ki so vzporedne črtam karirastega papirja. Oglejmo si pas karirastega papirja visine 11 kvadratkov. Po Diričhletovem prinčipu morata biti v vsakem stolpču pasu vsaj dve polji pobarvani enako. Stolpeč je lahko pobarvan na 1011 načinov. Ce pogledamo znotraj pasu poljubnih 1011 + 1 stolpčev, morata biti vsaj dva pobarvana popolnoma enako. V teh dveh stolpčih vzemimo po dva enako pobarvana kvadratka. Dobili smo zahtevane 4 enako pobarvane kvadratke. ■ 16.2 Ramseyev izrek Diričhletovemu načelu soroden izrek je tako imenovani Ramseyjev izrek. Za motivačijo navedimo naslednje zanimivo dejstvo. Trditev 16.2 Ce se neke zabave udeleži vsaj šest ljudi, tedaj bomo med njemi lahko našli bodisi skupino treh, ki se med seboj vzajemno poznajo (vsak iz trojice pozna vsakega drugega iz trojice) bodisi vzajemno ne poznajo (nihče iz trojice ne pozna nikogar drugega iz trojice). Preden trditev dokazemo, jo prevedimo v jeziku grafov. Naj bo G graf in K C V (G). Ce sta poljubni dve točki mnoziče K v grafu G sosednji, pravimo, da je K klika grafa G. Mnoziča K je antiklika (tudi neodvisna množica) grafa G, če nobeni dve točki iz K v grafu G nista sosednji. Zgornjo trditev sedaj lahko povemo takole: Trditev 16.3 Vsak graf z vsaj sestimi tockami premore vsebuje kliko moci 3 ali pa antikliko moci 3. Dokaz: Naj ima graf G vsaj 6 točk. Denimo, da graf G ne premore niti klike niti antiklike velikosti 3. Potem seveda niti komplementarni graf GC ne premore niti klike niti antiklike velikosti 3. Naj bo u poljubna točka grafa G in G(u) sose sčina točke u. C e bi v G(u) obstajali dve sosednji točki, bi le-ti skupaj z u tvorile kliko velikosti 3. To pa pomeni, da točke v mnoziči G(u) tvorijo antikliko. Ker graf ne premore antiklik moči 3, vsebuje sosesčina poljubne točke grafa G največ dve točki. Z drugimi besedami, stopnja vsake točke grafa G je največ 2. Ker pa ima graf G vsaj 6 točk, je stopnja vsake točke v komplementarnem grafu GC vsaj 3. To pa ravno dokazanem pomeni, da vsebuje graf bodisi kliko bodisi antikliko velikosti 3, kar je protislovje z zacetno predpostavko. I Pravkar dokazno trditev posplos i naslednji znameniti Ramseyjev izrek. Izrek 16.4 Za poljubni naravni stevili k in l obstaja najmanjše takšno naravno število n = r(k,l), za katerega velja naslednje: Vsak graf z vsaj n točkami premore bodisi kliko velikosti k bodisi antikliko velikosti l. Stevila r(k,l) imenujemo Ramseyjeva števila. Ramseyjev izrek nam sicer zagotavlja obstoj tak snih stevil, na daje pa nam nobenega prakticnega napotka, kako jih racunati. Problem racunanja Ramseyjevih stevil zelo tezak ze pri majhnih vrednostih stevil k in l. C e zelimo dokazati, da je Ramsey-jevo stevilo r(k, l) enako n, moramo v resnici dva problema. Najprej moramo dokazati, da vsak graf z vsaj n tockami premore bodisi kliko velikosti k bodisi antikliko velikosti l. S tem dokazemo neenakost n > r(k,l). Nato pa moramo najti graf na n — 1 tockah, ki ne premore niti klike velikosti k niti antiklike velikosti l. S tem dokazemo se n < r(k, l). Brez dokaza navedimo naslednje enakosti in neenakosti: r(k,l) = r(1, l) = r(k, 2) = r(k, l) < r(k, l) < r(k, k) > Zgled. DokaZi, daje r(3,3) = 6. Neenakost r(3, 3) < 6 sledi iz Trditve 16.3. Za dokaz neenakosti r(3,3) > 6 moramo poiskati graf na petih tockah, ki ne premore niti klike niti antiklike moci 3. Tak graf je, na primer, cikel dolzine 5. ■ Omenimo se, da lahko Ramseyjev izrek izrazimo tudi z barvanjem povezav polnega grafa. Ce namrec povezave polnega grafa na r(k, l) tockah pobarvamo z dvema barvama, denimo rdeco in modro, bomo gotovo nasli bodisi polni graf moci k s samimi rdecimi povezavami bodisi polni podgraf moci l s samimi modrimi povezavami. r(l, k) r(k, 1) = 1 k r(k — 1,l) + r(k,l — 1) k + l — 2N k—1 k 22 za k > 1 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. Potočnik: Kombinatorika s teorijo grafov: primeri in resene naloge, DMFAS, Ljubljana, 2000. vir6 D. Veljan: Kombinatorika s teorijom grafova Skolska knjiga, Zagreb, 1989 [4] R. J. Wilson, J. J. Watkins: Uvod v teorijo grafov, DMFAS, Ljubljana, 1997.