ITT0030 Diskreetne matemaatika II - eksamikonspekt (1)

Diskreetne matemaatika II
Suulise eksami konspekt
IABB 2011
[1]. Hulgad. Alam- ja ülemhulgad. Tehted hulkadega.
[2]. Hulga võimsus. Kontiinumhüpotees.
[3]. Järjendid. Permutatsioonid. Kombinatsioonid.
[4]. Binoomi valem. Pascali kolmnurk .
[5]. Liitmis - ja korrutamisreegel kombinatoorikas.
[6]. Kordustega permutatsioonid. Multinoomkordajad.
[7]. Elimineerimismeetod (juurde- ja mahaarvamise valem).
[8]. Korratused ja subfaktoriaalid.
[9]. Dirichlet ‘ printsiip.
[10]. Arvujadade genereerivad funktsioonid. Jadade ja genereerivate funktsioonide teisendamine .
[11]. n objekti jaotamine k gruppi.
[12]. Rekurrentsed võrrandid. Rekurrentsi lahendamine ad hoc meetodil ja iteratsioonimeetodil.
[13]. Tasandi tükeldamine n sirgega ja n nurgaga .
[14]. Lineaarsed rekurrentsed võrrandid.
[15]. Rekurrentsete võrrandite lahendamine genereerivate funktsioonide meetodil.
[16]. Fibonacci arvud. Üldliikme valem ja rakendused.
[17]. Lucas ‘ arvud.
[18]. Catalani arvud.
[19]. Sündmused ja tõenäosus. Statistiline tõenäosus. Bernoulli suurte arvude seadus.
[20]. Sõltuvad ja sõltumatud sündmused. Sündmuste summa ja korrutis.
[21]. Täistõenäosuse valem. Bayesi reegel.
[22]. Bernoulli valem (k katse õnnestumine katsete üldarvu n korral).
[23]. Kord- ja algarvud . Algarvude jaotus, algarvulisuse kontroll, Eratosthenese sõel.
[24]. Naturaalarvude kanooniline kuju. Suurim ühistegur ja vähim ühiskordne.
[25]. Fermat teoreem . Pseudoalgarvud ja Carmichaeli arvud.
[26]. Eukleidese algoritm .
[27]. Lineaarsed diofantilised võrrandid.
[28]. Täisarvude kongruentsid. Kongruentsi omadusi.
[29]. Moodularitmeetika.
[30]. Algarvulisuse Fermat‘ test. Miller -Rabini test.
[31]. Graafid ja graafide omadused. Ahelad ja tsüklid graafis.
[32]. Euleri graafid. Hamiltoni tsüklid.
[33]. Puud. Puude omadused.
[34]. Graafi vähima kaaluga aluspuud.
[35]. Märgendatud puud. Puude esitamine arvuti mälus.
[36]. Prüferi kood. Märgendatud puude loendamine . Cayley teoreem.
[37]. Märgendamata puude arv.
[38]. Kooskõlad graafis. Berge ’i teoreem.
[39]. Kooskõlad kahealuselises graafis. Halli teoreem.
[40]. Tasandiline graaf . Euleri valem: seos tasandilise graafi tippude, servade ja tahkude arvude vahel. Eulri valemi rakendusi.
[41]. Graafi tasandilisuse kriteeriumid. Kuratowski teoreem.
[42]. Graafi tippude värvimise ülesanne. Brooksi teoreem (tõestuseta).
[43]. Tasandilise lihtgraafi värvimine 6 ja 5 värviga. Neljavärviprobleem ja kaartide värvimine.
I. OSA
[1]. Hulgad. Alam- ja ülemhulgad. Tehted hulkadega.
Hulk on koosvaadeldavate objektide kogum.
*Eristatakse kaht erinvat hulgateooriat:

Naiivne hulgateooria - Naiivses hulgateoorias puudub kindel tugev aksiomaatika, ent ta on piisavalt efektiivne väga paljude lihtsamate vajaduste rahuldamiseks. Sageli õpetatakse matemaatikas esmalt naiivset hulgateooriat, kuna ta võimaldab inimesel paremini mõista hulga kontseptsiooni ning seda, miks aksioomid vajalikud on. Ka meie kasutasime kursuse raames naiivset hulgateooriat. Loojaks loetakse George Cantorit(19.saj.)
Aksiomaatiline hulgateooria- Kuna on teada, et naiivne hulgateooria jookseb väga paljudel juhtudel ummikusse (nt. Russeli „habemeajaja“ paradoks ), hakati alates 1908. hulgateooriat palju normeerima, mille tulemusel tekkiski aksiomaatiline hulgateooria. Aksiomaatilist hulgateooriat kasutatakse seal, kus on äärmiselt oluline vältida erinevaid hulgateoreetilisi paradokse või uurida teatavate matemaatiliste probleemide põhimõttelist lahenduvust/ mittelahenduvust.

*Võrdsed hulgad- Kahte hulka loeme võrdseks, kui nad koosnevad täpselt samadest elementidest. Elementide järjekord hulgas ei ole oluline.
*Alamhulk/ülemhulk- Hulka A nimetatakse hulga B alamhulgaks (e. osahulgaks), kui kõik hulga A elemendid sisalduvad ka hulga B koossesisus. Sellisel juhul on hulk B ka muuseas hulga A ülemhulk. Tähistaktakse:
ning .
Tehted:
Hulkade ühend- Kahe hulga ühendiks on „kõik hulga A elemendid + kõik hulga B elemendid“. (Tähistatakse ∪)
Hulkade ühisosa- Kahe hulga ühisosaks on „kõik elemendid, mis sisalduvad samaaegselt nii hulgas A kui ka hulgas B“. (Tähistatakse ∩)
Hulkade vahe- Kahe hulga vahe A/B on defineeritud kui „hulk, mis koosneb kõigist niisugustest elementidest, mis kuuluvad hulka A ent ei kuulu hulka B“ (Tähistatakse /)
Hulkade sümmeetriline vahe- Kahe hulga sümmeetriliseks vaheks on „kõik hulga A elemendid + kõik hulga B elemendid ilma nende ühise osata“ (Tähistatakse ∆)
[2]. Hulga võimsus. Kontiinumhüpotees.
Hulga võimsus- Lõpliku hulga võimsus on tema elementide arv. Hulga võimsust tähistavat sümbolit nimetatase ka hulga kardinaalarvuks.
*Lõpliku hulga kardinaalarv on selle hulga elementide arv, lõpmatute hulkade puhul kasutatakse aga eritähiseid: ℵ0 tähistab loenduvat võimsust, ℵ1 aga tähistab kontiinumvõimsust. (loendamatu)
*Võrdvõimsad hulgad- Kui kahes hulgas on ühepalju elemente ning nende elementide vahel saab luua üksühese vastavuse, on need kaks hulka võrdvõimsad. (Tähistatakse |A|=|B|)
* Loenduv hulk- Kui hulk on sama võimsusega nagu naturaalarvude hulk N, peetakse teda üldiselt loenduvaks. Loenduv hulk võib seega olla ka lõpmatu.
*Loendamatu hulk- Kui hulk on sama võimsusega nagu reaalarvude hulk IR, peetakse teda loendamatuks. Tänu komakohtadele pole elemente lihtsalt võimalik ammendavalt loetleda.
Kontiinumhüpotees- Kontiinumhüpotees on hüpotees, mille arendajaks oli George Cantor (aastal 1877 ) ning see puudutab lõpmatute hulkade võimalikke suurusi.
*Hüpoteesis eristatakse nö. „väiksema võimsusega lõpmatut hulka“, milleks on naturaalarvude hulk N ning „suurema võimsusega lõpmatut hulka“, milleks on reaalarvude hulk R.
*Hüpotees väidab, et ei leidu ühtki sellist lõpmatut hulka, mis oma võimsuse poolest jääks nende „väikse lõpmatu hulga“ ning „suure lõpmatu hulga“ vahele.
Lisaks: Hulga astmehulgaks nim. hulga kõikide alamhulkade hulka. Hulga astmehulga võimsus on |P(A)|=2n
*Hiljem on märgitud, et aksiomaatilise hulgateooria baasil ei ole Cantori väidet võimalik ei tõestada, ega ka ümber lükata.
[3]. Järjendid. Permutatsioonid. Kombinatsioonid.
Järjendid e. korteezid e. ennikud- n-elemendilise hulga elementidest moodustatud k-kohalist järjestatud loendit nimetatakse järjendiks.
*Kaks järjendit on võrdsed vaid siis, kui nad on sama pikad ning nende vastavates positsioonides on samad väärtused. Järjendi puhul on oluline temas sisalduvate elementide järjestus. (Nt. hulk [3] järjendeid on 9: 11,12,13,21,22,23,31,32,33)
Permutatsioonid-
n-permutatsioonideks nimetatakse järjendeid, mis on mingi lõpliku hulga A kõikkide elementide n kõikvõimalikud ümberpaigutused. (n!)
k-permutatsioonideks nimetatakse järjendeid, mis on mingi lõpliku hulga A teatud alamhulga elementide kõikvõimalikud ümberpaigutused. k-permutatsioone nim. ka variatsioonideks. (Nt. hulk[3] 1-permutatsioonid: 1,2,3)
*Arvutada saab: n-permutatsioone Pn = n! ning k-permutatsioone
Kombinatsioonid-
k-kombinatsiooniks nimetatakse hulga A igat k-elemendilist alamhulka. (Nt. hulk<).
*Arvutada saab:
[4]. Binoomi valem. Pascali kolmnurk.
*Kombinatsioonide arvu tähist nimetatakse sageli ka binoomkordajaks. See tulenebgi aga (Newtoni) binoomivalemist.
Binoomi valem-Valem, mis esitub kujul , ning sisuliselt kujutab ta endast „summa ruudu valemit“ astmel n. Selgub aga, et binoomivalemi sulgude avamisega saame sellise üksliikmete summa, kus iga liikme kordaja e. binoomkordaja vastab sisuliselt kombinatsioonide arvule , kus k on konkreetse üksliikme x’i aste ning n on algse sulgavaldise aste. Näiteks:
Toetused aga multinoomvalemile, saaksime binoom -koefitsente välja arvutada ka valemi abil, kus k1 on üksliikme esimese kordaja aste, k2 aga teise kordaja aste.
Omadusi:
* Binoomkordajad on sümmeetrilised alumise indeksi suhtes:
Pascali kolmnurk- Pascali kolmnurk on prantsuse matemaatiku Blaise Pascali poolt loodud matemaatiline element, mis kujutab endast binoomkordajate massiivi, kus viimased on kõik seatud kolmnurksesse paigutusse. Kolmnurga tipuks on binoomkordaja kohal n = 0, allapoole minnes n’i väärtus aga aina kasvab.
Pascali kolmnurga omadusi:
*Ta on sümmeetriline vertikaaltelje suhtes.
*Iga arv Pascali kolmnurgas võrdub tema kohal olevate arvude summaga . (Seetõttu on mõningatel juhtudel teda väga mugav ülesannete lahendamisel kasutada).
* Ehkki binoomkordajate kolmnurkset asetust kirjeldas ametlikult esimesena Pascal , arvatakse, et ka paljud varasemad matemaatikud teadsid selle olemasolust.
[5]. Liitmis- ja korrutamisreegel kombinatoorikas.
Liitmisreegel - üks kahest kombinatoorika põhipostulaadist. Ta ütleb, et kui ühte objekti saab valida m erinval viisi ja teist objekti saab valida n erinval viisil, kusjuures esimese ja teise objekti valikud on teineteist välistavad, siis kas esimese või teise objekti valmiseks leidub täpselt m + n erinevat võimaust.
Korrutamisreegel- teine kombinatoorika põhipostulaat. Ta väidab, et kui ühte objekti saab valida m erineval viisil ja teist objekti saab valida n erineval esimesest valikust sõltumatul viisil, siis nii esimese kui ka teise objekti valimiseks on täpselt m*n erinvat võimalust kokku.
[6]. Kordustega permutatsioonid. Multinoomkordajad.
Kordustega permutatsioonid on sellised n-permutatsioonid, kus mingit hulga elementi a esineb n korda, kusjuures n > 1. (Tähistame )
Anagrammid:
*Nagu ka L.Lovasz’i õpikus näidatud oli, leiavad kordustega permutatsioonid sageli rakendust näiteks juhul, kui meil on vaja arvutada mingi sõna anagrammide arv.
*Et sageli ei ole mingis sõnas sisalduvad tähed kõik erinevad, ongi meil anagrammide leidmisel tegu kordustega permutatsioonidega.
*Sellisel juhul saame sõna anagrammide arvu leida järgneva valemi abil: Pnr = .
*Viimasest järeldub muuseas, et sõnal on enim anagramme, kui kõik tema tähed on erinevad, ning vähim anagramme, kui kõik tema tähed kattuvad.
*Eesti keeles kutsutakse seda valemit ka nö. Raamatupidaja reegliks.
Multinoomkordajad- Tuleks ära märkida, et sümbol
tähistab matemaatikas multinoomkordajat: see tähendab, et ta on multinoomi (X1 +.......+ Xk)n arenduses (sulgude avamisel) üksliikme e. mononoomi kordajaks. (analoogselt binoomi valemile).
Multinoomkordaja leidmine: Oletame et meil on valem (a + b + c)3 ning vaja on leida liikme a1b1c1 koefitsienti väärtust. Üheks võimaluseks on lahti korrutada avaldis (a + b +c)(a + b +c)(a + b +c), ning leida vastava kordaja väärtus. Lihtsam on aga kasutada multinoomi teoreemi, mis annab meile palju mugavamalt kätte mistahes liikme koefitsiendi, näiteks:
ning .
Binoomiteoreem ning binoom-koefitsiendid on sisuliselt vaid multinoomi valemi erijuht.
[7]. Elimineerimismeetod (juurde- ja mahaarvamise valem).
Elimineerimismeetod- Elimineerimismeetod on hulkade võimsuse notatsioonil põhinev, äärmiselt mugav vahend leidmaks mitme, üksteisega ühisosa omava hulga ühendit või ühisosa.
*Ilma konkreetse valemita oleks suure hulga ühisosa omavate hulkadega arvutamine äärmiselt tülikas. (Venni diagramme kasutades kaob ülevaade juba näiteks 4 hulga puhul). *Elimineerimismeetod on aga rakendatav praktiliselt kuitahes suure koguse hulkade korral.
*Elimineerimismeetodi valem avaldub üldkujul järgmiselt:
*Elimineerimismeetodil on rakendusi ka arvuteoorias: näiteks võimaldab ta meil lahendada ülesannet kujul: Kui palju on arve 1-2500, mis ei oma 2500’ga ühiseid tegureid? (e. on relatiivselt algarvulised 2500 suhtes).
*Vahetevahel on elimineerimismeetodit kirjanduses nimetatud ka Grassmanni valemiks (ka DM I kursuse raames).
[8]. Korratused ja subfaktoriaalid.
*Korratus on püsipunktideta permutatsioon. Püsipunktideta permutatsiooni puhul ei jää pärast elementide ümberjärjestamist ükski element oma endisele kohale.
().
*Muuseas nimetatakse n-korratuste arvu dn ka arvu n subfaktoriaaliks, ning seda tähistatakse sümboliga !n.
*Mingi arvu korratuste arvu dn on võimalik leida mitme keeruka valemi abil, ent neist kõige optimaalsem on tegelikult järgmine: dn = n! =
*Valemis leitakse esmalt avaldisest korratuste ligikaudne arv. Et aga tulemus pole täisarvuline, liidetakse sellele veel 0,5 ning siis rakendatakse floor funktsiooni. (E. taandatakse tulemus täisarvuni, „alumise“ väärtuseni).
[9]. Dirichlet‘ printsiip.
Dirichlet’ printsiip väidab, et kui n hulgas sisaldub rohkem kui n elementi, peab leiduma vähemat üks selline hulk, milles sisaldub enam kui 1 element.
*See, esmapilgul naeruväärselt triviaalne reegel, osutub sageli äärmiselt rakenduslikuks keeruliste väidete tõestamisel või ümberlükkamisel (nt. Eestis elavate inimeste juuksekarva probleem, püssilaskude omavahelise kauguse probleem märklauas jne.)
*Dirichlet’ printsiip leiab laia kasutust ka arvuteoorias.
*Dirichlet’ printsiipi tuntakse veel kui tuvipesaprintsiipi, laekaprintsiipi või Dirichlet’ sahtliprintsiipi. (Heal lapsel mitu nime )
[10]. Arvujadade genereerivad funktsioonid. Jadade ja genereerivate funktsioonide teisendamine.
Genereerivad funktsioonid on sellised astmeread, mille kordajad e. koefitsendid sisaldavad informatsioonina mõnda arvujada an.
Genereerivad funktsioonid on harilikult esitatud nö. suletud kujul(vastandina lahtisele astmereale): näidatud on vaid avaldis, mis defineerib rea saamiseks teatud tehete hulga (nende tehete sooritamisel saamegi astmerea, mille kordajateks on meile vajalikud väärtused). Tehniliselt on suletud kuju valem tuletatud geomeetrilise summa valemi järgi.
Suletud kuju kasutamine on kasulik selleks, et siis on vaade avaldisest palju ülevaatlikum ning veelgi enam, genereerivatele funktsioonidele defineeritud tehete rakendamine lihtsustub väga oluliselt (jadade liitmine , lahutamine, korrutamine jne).
*Astmereale defineeritud tehete hulgas võivad leiduda nii aritmeetilised operatsioonid nagu korrutamine, liitmine ja lahutamine, kuid ka differentseerimine: näiteks tuletised x’i suhtes. Samuti võib näiteks leiduda asendamisi teistesse funktsioonidesse.
Mõningaid näiteid genereerivatest funktsioonidest:
a).
(„võtme tähtsusega gen. funktsioon“, vastab jadale ).
b). (vastab jadale , vahed tulenevad „2n“ ’ist).
c). (vastab jadale ).
Genereerivatele funktsioonidele defineeritud tehted/ teisendused :
1).Skaleermisireegel: Kui ↔ F(X) siis ↔ c*F(X) ,ehk genereeriva funktsiooni korrutamisel mingi konstandiga, korrutuvad kõik tema jada (astmerea) liikmed selle konstandiga.
2).Liitmisreegel: Kui ↔ F(X) ja ↔ G(X), siis ↔ F(X) + G(X), ehk kahe genereeriva funktsiooni liitmisel liidetakse omavahel ka kõik vastavad jada(astmerea) väärtused.
3).Nihkereegel: Kui ↔ F(X), siis ↔ xk*F(X) (nulle on k tükki), ehk genereeriva funktsiooni korrutamisel mingi xk’ga nihkuvad kõik genereeriva funktsiooni jada(astmerea) liikmed k positsiooni edasi, asemele tekivad 0’id.
4).Diferentseerimisreegel: Kui ↔ F(X), siis ↔ F(X), ehk genereeriva funktsiooni jada(astmerida) on võimaik ka diferentseerida (toimub tavaliste reeglite põhjal).
5). Intengreerimisreegel: Kui ↔ F(X), siis ↔ dz, ehk genereeriva funktsiooni jada(astmerida) on võimalik ka integreerida (tavaliste integreerimismeetodite baasil).
6). Konvolutsioonireegel(korrutis): Kui ↔ F(X) ja ↔ G(X), siis ↔ F(X)*G(X), kus hn= f0 gn + f1 gn-1 + f2 gn-2 +...+ fn g0. Seega, genereerivate funktsioonide korrutamisel korrutatakse ka kõik jada(astmerea) liikmed omavahel, ent ei korrutata mitte vastavad liikmed vaid nö. jada vastandliikmed (hakatakse sümmeetriliselt mõlemast jada otsast tulema ).
(Genereerivaid funktsioone kirjeldas esimesena Abraham Moivre, 1730 ent tegelikkuses on siiski tegu väga uue suunaga).
[11]. n objekti jaotamine k gruppi.
On selge, et tegu on kombinatooorse probleemiga.
a). n kingi jagamine k inimese vahel kui on teada, kui mitu kinki iga inimene peaks saama:
1). Oletame, et kõik n kinki on laotatud pika laua peale ritta . Kuna on teada, kui palju kinke keegi peab saama, võime ette kujutada, et esimene inimene tuleb võtab laualt (vasakult alustades) esimesed n1 kinki. Teine inimene võtab seejärel järgmised n2 kinki. Viimane inimene k võtab lõpuks laualt ära viimased kingid nk.
2). On selge, et kinke on lauale võimalik järjestada Pn = n! erineval viisil. Seejuures on samuti triviaalne, et kutsudes inimesi laua äärde tagasi, on esimesel neist võimalik oma kinke järjestada n1! viisil, teisel inimesel n2! viisil jne. Kokkuvõttes saamegi, et n kingi selliselt jagamiseks on võimalust. Saadud valemit kutsutakse ka Raamatupidaja valemiks.
b). n mündi jagamine k inimese vahel nii, et igaüks saab vähemalt ühe mündi:
1). Müntide jagamine erineb kinkide jagamisest sellepoolest, et mündid on kõik identsed – seega olulised on vaid kogused , mitte see kes millise mündi saab. Kuigi tegu on suhteliselt erinevate probleemidega, saame kasutada sarnast lahendust : laotame mündid põrandale ritta ning laseme esimesel inimesel neid korjama hakata.
2). Teatud hetkel peame korjama laskma teise inimese- selgub, et erinevaid alustamiskohti on meil selleks n-1 tükki. Inimese valikuks on meil aga k-1 võimalust. Selgubki, et n mündi jagamiseks on meil võimalust.
c). n mündi jagamine k inimese vahel nii, et igaüks ei pruugi saada münti:
1). Esmalt laename igalt k’st inimesest ühe mündi ning seejärel jaotame kõik mündid analoogselt eelmisele punktile laiali nii, et iga inimene saab vähemalt ühe mündi (need kellel veab, saavad rohkem ). Selliselt saame olukorra, kus iga k inimesest saab tagasi temalt laenatud summa, ent ei pruugi saada enamat . Münte on meil jagamiseks seetõttu n+k-1.
2).Selgub, et n mündi jagamiseks k inimese vahel on meil võimalust, kus iga inimene saab vähemalt 1 mündi.
[12]. Rekurrentsed võrrandid. Rekurrentsi lahendamine ad hoc meetodil ja iteratsioonimeetodil.
Arvujada (An) = (a0,a1,a2...) nimetatakse rekurrentseks, kui tema iga järgnev üldliige on avaldatav eelnevate liikmete kaudu nn. rekurrentse võrrandi abil. (Tuleneb ladina keelest: „recurre“- tagasi jooksma ).
NÄIDE: Seost Pn = nPn-1 nimetatakse faktoriaalijada (Pn) rekurrentseks võrrandiks ja avaldis Pn = n! selle võrrandi lahendiks . (e. jada (Pn) üldliikme analüütiliseks esituseks).
Rekurrentsi järk k on rekurrentse võrrandi „sügavus“: see näitab, kui mitmest eelmisest jada liikmest iga järgnev üldliige sõltub.
Lahendamismeetodid:
a). ad hoc meetod e. „for the cause “ meetod – sellisel juhul on tavaliselt ette antud kas rekurrentne võrrand või mõni muu seos, mille abil on võimalik jada liikmeid leida. Liikmete väärtuste põhjal saab heuristiliselt tuletada algebralise hüpoteesi, mida juba omakorda on võimalik kontrollida induktsiooni abil. (Eeldades et n=k, heaks näiteks on siin noore Gaussi meetod).
b). Iteratsioonimeetodi puhul võetakse ette rekurrentne võrrand (näiteks Zn = aZn-1 + b) ning hakatakse seda järjest „ koorima nagu sibulat“ – rekurrentset liiget hakatakse lahti kirjutama aina järgmiste väärtuste jaoks (nt. Zn = a(a(Zn-2)+ b) + b  Zn = a2Zn-2 + ab +b), kuni hoomatav on kindel süsteem.
*Kui võrrand on kujul Zn = aZn-1 + b; Z0 = c , saab tema väärtust arvutada valemist Zn= anc + b ning erijuhul, kus a = 1 (ehk Zn = Zn-1 + b) , valemist Zn= bn + c.
(Iteratsioonimeetodi miinuseks on see, et ta kehtib vaid esimest järku rekurrentsete võrrandite puhul).
[13]. Tasandi tükeldamine n sirgega ja n nurgaga.
Tasandi tükeldamine n sirgega:
Antud ülesanne on äärmiselt sisuline näide selle kohta, kuidas rekurrentsed arvujadad esinevad reaalsetes rakendustes. Ülesande eesmärgiks on leida, kui mitu sektorit tekib tasandi tükeldamisel n sirgega. Olgu tasandi tükelduste arvuks Qn.
a). 0 sirge puhul on vastuseks kindlasti Q0 = 1, 1 sirge puhul aga Q1 = 2. Suhteliselt lihtne on näha ka seda, et Q2 = 4. Siinkohal võiksime püstitada hüpoteesi Qn = 2n.
b). Jada edasi uurides aga selgub, et järeldus oli ennatlik. Jada järgmisteks väärtusteks on Q3 = 7 ning Q4 = 11, mille toel on võimalik püstitada rekurrentne hüpotees Qn = Qn-1 + n.
c). Püstitaud hüpoteesi kontrollimiseks lahendame saadud rekurrentse võrrandi näiteks karakteristliku võrrandi meetodit kasutades ning võrdleme saadavaid väärtusi olemasolevate väärtustega. Kui need kattuvad täies ulatuses, on tõenäoline, et oleme probleemi õigesti lahendanud.
Tasandi tükeldamine n nurksirgega:
Nüüd uurime seda, kui mitu sektorit tekib tasandi jaotamisel n nurksirgega (linnunoka kujulised). Olgu seekord tasandi tükelduste arvuks Tn.
a). Jällegi on lihtne leida jada esimesed väärtused: 0 nurksirge puhul on selleks T0 = 1.
1 nurksirge puhul saame T1 = 2 ning 2 nurksirge puhul T2 = 7. Võrreldes jada Qn ning Tn esimesi väärtusi (kuni n=9), märkame seost Tn = Q2n – 2n ehk sisuliselt saame defineerida jada Tn läbi jada Qn rekurrentsi. Loomulikult on nurksirgete jada jaoks võimalik leida ka iseseisev rekurretne võrrand: selleks on Tn = Tn-1 + 4n – 3.
[14]. Lineaarsed rekurrentsed võrrandid.
Lineaarseid rekurrentseid võrrandeid jaotatakse:
1.Lineaarsed homogeennsed rekurrentsed võrrandid. (Nt. An = An-1 + 5An-2).
2.Lineaarsed mittehomogeennsed rekurrentsed võrrandid.(Nt. An = 3An-1 + 2An-2 - n).
Reaalsetes rakendustes leidub mõlemat varianti üsna sageli. Teise tüübi puhul tuleb aga võrrandi lahendamisel arvestada ka tekivate erilahenditega (Mittehomogeennsuse puhul sõltub arvujada väärtus tavaliselt lisaks jada eelnevatele väärtustele An ka liikme indeksist n või suvalisest liidetavast x).
Esimest järku rekurrentse on lihtne ning efektiivne lahendada interatsioonimeetodi abil.
Teist järku rekurrentse lahendatakse tavaliselt karakteristliku võrrandi meetodi abil. Selleks, et lahendada mistahes n’indat järku rekurrentset võrrandit, vajame me ka vähemalt n’i erinevat eeldefineeritud algtingimust An. Kui algtingimused on olemas, on võrrand üheselt määratud.
Karakteristliku võrrandi meetod:
a). Rekurrentse võrrandi lahendit otsime alati kujul
b). Esmalt peame selleks leidma karakteristliku võrrand lahendid : karakteristliku võrrandi saame, kui viime kõik võrrandi liikmed ühele poole ning asendame nad oma järgu järgi muutujaga
Tulemuseks on polünoomiaalne võrrand, mille lahenditeks ongi karakteristliku võrrandi lahendid.
c). Järgmise sammuna peame leidma antud ülesandele sobivad rajatingimused c1 ning c2. Rajatingimusi saame arvutada seesugusest süsteemist:
d). Leidnud sobivad rajatingimused, avaldamegi rekurrentsi kujul
[15]. Rekurrentsete võrrandite lahendamine genereerivate funktsioonide meetodil. (Ainus küsimus, millest ei saa mitte sittagi aru).
Olgu arvujada esitatud rekurrentse seose abil.
a). Esmalt täiendan jada elementidega g-1 = g-2 = ... = 0
b). Korrutan rekurrentse võrrandi mõlemaid pooli suurusega zn ning summeerin üle kõigi n’i väärtuste. Võrduse vasakul poolel olevat summat
nimetatakse jada
genereerivaks funktsiooniks.
c). Teisendan võrrandi paremat poolt nii, et sinna tekiks avaldis funktsioonist G(z).
d). Lahendan võrrandi G(z) suhtes, st. sisuliselt avaldan G(z)’i.
e). Arendan G(z) astmeritta, elemendi zn kordaja ongi jada rekurrentse võrrandi lahendiks.
NÄITEKS: Valem Fibonacci jada liikmete arvutamiseks: G(z) = zn , ning kuna lahendiks on (eelmise punkti alusel) Zn kordaja, siis saangi Fibonacci arvude leidmiseks: Fn, kus ning = .
[16]. Fibonacci arvud. Üldliikme valem ja rakendused.
*Fibonacci arvud on kahtlemata kõige tuntum rekurrentne arvujada, mille esimeseks kirjeldajaks peetakse Itaalia matemaatikut Leonardo de Pisat. Mõnes mõttes „avastas“ ta selle arvujada iseteadmatult, kuna esialgselt oli tegu „huvitava probleemiga“, mis puudutas jäneste arvu kasvamist nende paaritumisel 1-kuise intervalliga.
*Hiljem esitati Fibonacci poolt avastatud arvujada aga kindla rekurrentse avaldisena:
Fn = Fn-1 + Fn-2 , kus algtingimustena on teada, et F0= 0 ning F1 = 1, ehk sisuliselt on n’indat Fibonacci jada arvu võimalik arvutada, liites kaks eelmist arvu.
*Tahtes nüüd aga arvutada Fibonacci jada n. liikme väärtust ilma, et peaks korduvalt kasutama eelnevalt antud rekurrentset seost, peame me rekurretnse võrrandi lahendama . Antud juhul on selleks kõige optimaalsem kasutada karakterilstliku võrrandi meetodit.
Olles leidnud karakteristliku võrrandi lahendid λ1 ja λ2 ning sobivad rajatingimused c1 ja c2, selgub, et Fibonacci jada liikmete väärtuseid on võimalik leida algebralisest valemist:
Fn =
*Fibonacci arvude kohta teatakse ka seda, et ta on väga lähedaselt seotud nn. kuldse lõikega- see on proportsioon , mis esineb väga sageli looduses ning näiteks arhitektuuris, kuna ta paistab välimuselt inimestele kõige aesteetilisem.
*Asetades näiteks rekurssiivselt üksteise sisse ruudud , mille küljepikkus ühtib fibonacci jada arvuga ning ühendades diagonaalsed nurgad kurvidega, saame kuldlõike spiraali .
*Fibonacci arve kasutatakse sageli populatsioonide arvukuse uurimiseks ja prognoosimiseks bioloogias.
*Veel üks huvitav jada omadus: gcd(Fn,Fm) = Fgcd(n,m)
[17]. Lucas‘ arvud.
Lucas’ arvud on defineeritud täpselt sama lineaarse rekurrentse võrrandi baasil, mis Fibonacci arvudki. Erinevad on vaid algtingimused.
Lucas’ arvud avalduvad seega võrrandist:
Ln = Ln-1 + Ln-2 , kus algtingimusteks L1= 1 ning L2= 3
*Lucas’ arvujada leiab rakendust näiteks graafiteoorias, kuna tema abil on võimalik leida n-tipulise graafi kõikvõimalike aluspuude arvu. Täpsemalt kehtib seos T(Wn) = L2n – 2, kus n on esialgse graafi tippude arv.
*Rakendusi leidub aga ka hulgateoorias: on avastatud, et mingi hulga A alamhulka suvalisel heuristilisel valikul on täpselt Ln sellist võimalust, mille korral valitud alamhulgas ei sisaldu kaht järjestikust arvu.
*Arvuteoorias: selgub, et kui n on algarv , siis kehtib alati kongruents Ln ≡ 1 (mod n).
*Lucas’ arvujada on oma nime saanud prantsuse matemaatiku F.E.A.Lucas’ järgi, kes muuseas on väga tuntud selle poolest, et ta pani kirja valemi arvutamaks Fibonacci jada n’indat väärtust. Kirjanduses mainitakse veel, et ta oli ka ühe algarvulisuse testi autoriks .
[18]. Catalani arvud.
Catalani arvudeks on naturaalarvude jada, mis on oma nime saanud Belgia matemaatiku Eugene Catalani järgi ning ta esinevad sageli loendamisega seotud probleemides.
*Catalani arvud on lahenduseks väga suurele hulgale erinevatele probleemidele, eriti just kombinatoorika vallas. Näiteid:
a).Catalani arv Cn on erinvate Dycki sõnade arv pikkusega 2n. (Dycki sõnad on lahtistest ning kinnistavatest sulgudest koosnevad stringid, kusjuures kõik eelnevalt „avatud sulud“ peavad sõna lõpuks saama ka „suletud“ ning stringi alguses ei tohi kinnistavaid sulge olla rohkem, kui lahtiseid sulge).
b).Catalani arv Cn on kõigi erinevate n+1 lehega täielike kahendpuude arv.
c). Catalani arv Cn on kõigi võimalike teede arv N x N dimensionaalse võrgu külgi mööda liikumiseks vastastippude vahel nii, et ei ületataks diagonaali.
d). Catalani arv Cn on kõikide erinevate võimaluste arv lõikamaks n + 2 küljega hulknurka tükkideks, kui tippe ühendada sirgjoontega.
n’indat Catalani arvu on võimalik leida väga mitmest erinvast valemist. Nende hulgas:
Rekurrentsest seosest: Cn = Cn-1, kus algväärtuseks C0 = 1;
Kombinatoorsest valemist: Cn =
Genereeriva funktsioonina: C(z) =
*Kokkuvõttes võib öelda, et Catalani arvude jada on kindlasti üks suurima arvu kasutusvald-kondadega arvujadadest kombinatoorikas.
[19]. Sündmused ja tõenäosus. Statistiline tõenäosus. Bernoulli suurte arvude seadus.
Tõenäosusteoorias eristatakse sündmusi järgnevalt:
a). Kindel sündmus(Ω)- kindel sündmus on sündmus, mis antud vaatluse või katse korral alati toimub.
b). Võimatu sündmus(∅)- võimatu sündmus on sündmus, mis antud vaatluse või katse korral mitte kunagi ei toimu.
c). Juhuslik sündmus- juhuslik sündmus on sündmus, mis antud vaatluse või katse korral võib toimuda aga võib ka mitte toimuda.
*Sündmuse A toimumise tõenäosuseks nimetatakse selle sündmuse esinemiseks soodsate võimaluste arvu m ja kõigi võimaluste n arvu suhet e. p(A) = .
*Sündmused on võrdvõimalikud, kui nende toimumise tõenäosused on ühesugused.
*Juhuslikke sündmusi nim. üksteist välistavateks, kui nad ei saa korraga toimuda.
*Sündmuse A vastandsündmuseks on sündmus , mis „toimub“ siis, kui sündmus A ei toimu.
*Sündmuse A statistiliseks tõenäosuseks nimetatakse piirväärtust p, millele läheneb sündmuste suhteline sagedus s(A) katsete arvu piiramatul kasvamisel.
*Bernoulli suurte arvude seadus ütleb, et küllalt pika katseseeria korral on sündmuse suhteline sagedus ligikaudselt võrdne sündmuse tõenäosusega ühel katsel e. s(A) ≈p(A).
[20]. Sõltuvad ja sõltumatud sündmused. Sündmuste summa ja korrutis.
*Sõltumatud sündmused- Kui sündmuse A toimumise tõenäosus ei olene sündmuse B toimumisest/mitte-toimumisest siis nimetatakse neid kahte sündmust sõltumatuteks sündmusteks.
1).Kahe sõltumatu sündmuse A ja B summaks A U B nimetatakse sündmust, mille toimumine seisneb kas sündmuse A VÕI sündmuse B toimumises. Seega, kahe sündmuse summa on p(A∪B) = p(A)+p(B).
Nt: Urnis on 3 punast, 5 sinist ja 2 valget kuuli. Tõenäosus, et võetakse sinine VÕI punane kuul, on p(A∪B) = p(A)+p(B) = 3/10 + 1/2 = 4/5
2). Kahe sõltumatu sündmuse A ja B korrutiseks A∩B nimetatakse sündmust, mille toimumine seisneb sõltumatute sündmuse A JA B toimumises.
Nt: Ühes urnis on 5 musta ja 3 valget kuuli ning teises urnis 4 musta ja 6 valget kuuli. Kummastki urnist võetakse üks kuul, milline on tõenäosus, et mõlemad kuulid on mustad? p(A∩B)=5/8 * 4/10.
*Sõltuvad sündmused- Sündmust B nimetatakse sõltuvaks sündmusest A, kui sündmuse B toimumise tõenäosus sõltub sellest, kas sündmus A toimus või mitte.
1). Kahe teineteist mittevälistava sündmuse A ja B summa tõenäosus võrdub nende sündmuste tõenäosuste summaga, millest on lahutatud sündmuste koosesinemise e. korrutise tõenäosus. p(AUB) = p(A) + p(B) – p(A∩B).
Nt. Visatase kahte täringut. Kui suur on tõenäosus, et ühel täringutest on tulemuseks vähemalt 2 silma VÕI silmade summa on 5.
2). Kahe teineteist mittevälistava sündmuse A ja B korrutise tõenäosus võrdub sündmuse A tõenäosuse ja sündmuse B tingliku tõenäosuse korrutisega. (St. oletatakse, et kui toimub sündmus A, siis toimub ka sündmus B) p(A∩B) = p(A) * p(B|A).
[21]. Täistõenäosuse valem. Bayesi reegel.
Täistõenäosuse valem: Kui sündmus A võib toimuda koos ühega hüpoteesidest H1; H2; .... Hn, siis sündmuse A toimumise tõenäosus on võrdne summaga, mille liidetavateks on iga hüpoteesi tõenäosuse ja sellele hüpoteesile vastava sündmuse A tingliku e. oletusliku tõenäosuse korrutis.
NÄITEKS: Võtame ülesande, kus on antud kolm urni . Neist ühes on 3 musta ja 2 valget kuuli, teises 2 musta ja 3 valget ning kolmandas 5 valget kuuli. Võetakse huupi üks urnidest ja sellest pimesi üks kuul. Kui tõenäoline on, et võetud kuul on valge?
a). Antud juhul oleks A- valge kuuli võtmine;
b). Hüpoteesid aga H1 –valitakse esimene urn; H2 –valitakse teine urn; H3-valitakse kolmas urn.
c). Et hüpoteesid on alati teineteist välistavad, siis saangi, et p(A) = p(A∩H1) + p(A∩H2) + p(A∩H3) ehk p(A) = 2/15 + 1/5 + 1/3 = 2/3.
Kokkuvõtteks: selleks, et täistõenäosuse valemit rakendada, peab korralikult defineeritud olema terve hüpoteeside hulk.
Bayesi reegel: Thomas Bayes ’i järgi nime saanud reegel esitub kujul: P(A|B) =
ning ta võimaldab arvutada tingimuslikke tõenäosusi. Valemis sisalduvatest suurustest on:
*p(A|B) – kogeumustest tulenev hüpoteesi A tõenäosus tingimusel, et katse tulemusena juhtus sündmus B(seda otsimegi) (näiteks tõenäosus, et naisel on rinnavähk, kui mammograaf positiivset tulnemust näitab).
*p(B|A) – katsetulemuste B esinemise tõenäosus tingimusel, et ennustati hüpoteesi A paikapidamist (näiteks tõenäosus, et mammograaf näitab õiget tulemust täpsusega 95% - ehk et kui ennustati, et naisel on rinnavähk, kinnitas seda 95% juhtudest ka mammograaf).
*p(A)- kogemusele eelnev hüpoteesi A tõenäosus; (näiteks tõenäosus, et naisel on rinnavähk(1%))
*p(B) – kogemusele eelnev katseandmete B tõenäosus; (näiteks tõenäosus, et mammograaf näitab positiivset tulemust(5%))
(Nt. veel Baromeetri ülesanne loengust).
Bayesi reegli rakendamiseks peab meil täpselt määratud olema kogu ülejäänud tõenäosuste hulk (p(B), p(A), p(B|A)).
Bayes’i täiendatud versioon :
(Teoreem viiakse vastavusse täistõenäosusega).
*p(B|A) = Tõenäosus, et kui inimesel ON haigus, siis test näitab ka positiivset tulemust e. testi täpsus (95%).
*p(A) = Tõenäosus, et inimesel on antud haigus(1%).
*p(B|Ac) = Tõenäosus, et kui inimesel EI OLE haigust, siis test näitab positiivset tulemust e. testi ebatäpsus(5%).
*p(Ac) = Tõenäosus, et inimesel ei ole antud haigust(99%).
(NB! NENDES SULGUDEGA JUNNIDES ALATI EELDAME TÄHTE NR 2)
II.OSA
[22]. Bernoulli valem (k katse õnnestumine katsete üldarvu n korral).
*Bernoulli valem on Sveitsi matemaatiku Jacob Bernoulli poolt 17-18 saj. kirja pandud valem, mis tänapäeval leiab väga laia kasutust tõenäosusteoorias ning statistikas.
*Bernoulli valem on sisuliselt valem, mis näitab n ühesuguse ja sõltumatu katse korral sündmuse A toimumise tõenäosust täpselt k korda, kui sündmuse tõenäosus igal katsel on p = P(A) ning sündmuse vastandsündmuse tõenäosus on q = 1 – P(A).
Valem ise: Pn,k =* pk * qn – k
*Bernoulli valemi rakendamise tulemusena saadakse k katse õnnestumine katsete üldarvu n korral. Kohati on kirjanduses p ja q tähistatud ka kui „õnnestumise“ ning „ebaõnnestumise“ tõenäosus.
nt. Leida mündi 10-kordsel viskamisel kirja 4 korda esinemise tõenäosus, kus seega p = 0,5 ning q = 0,5.
[23]. Kord- ja algarvud. Algarvude jaotus, algarvulisuse kontroll, Eratosthenese sõel.
*Kordarv on selline ühest suurem naturaalarv n, millel on ka muid positsiivseid tegureid peale 1 ning tema enda.
*Algarv on selline ühest suurem naturaalarv n, mille ainsateks positiivseteks teguriteks on arvud 1 ning tema ise.
Algarvud: 2, 3, 5, 7, 11, 13, 17, 19....
Kordarvud: 4, 6, 8, 9, 10, 12, 14, 15....
*Esiteks, algarve on naturaalarvude hulgas lõpmata palju.
*Algarvude jaotus kohta on teada, et neid leidub naturaalarvude hulgas suhteliselt korrapäratult. Mõningates vahemikes leidub naturaalarve oluliselt rohkem kui mõningates teistes vahemikes. Korrapärade otsimine algarvude jaotuses on teadlastele huvi pakkunud sajandeid: neid on paiknevuse järgi kujutatud erinevatele graafikutele jne. Seaduspära või tsüklit pole aga siiani leitud.
*Huvitava korrapärana algarvude hulgas paistavad silma nn. algarvude kaksikud e. teatud vahega leiduvad naturaalavude hulgas N sellised algarvud, mis on justkui „paarilised“ (nende vahe on 2).
*Algarvulisuse kontroll:
a). „Katse-eksimis meetodil“ – sellisel juhul on mõtekas proovida kuni väärtuseni , kuna järgnevate arvude hulgas tegurit enam tõenäoliselt ei leidu.
b). Fermat’ väike teoreem- asendadada arvud Fermat’ väikesesse teoreemi.
c). Miller-Rabini test- ehkki tegu on tõenäosusliku polünomiaalse meetodiga, on tulemus suhteliselt usaldusväärne, kuna eksimisvõimalus on harilikult 0,01% või vähemgi.
*Erathosthense sõel- ( Antiikne ) meetod selekteerimaks n naturaalarvu seast välja algarve. Üles kirjutatakse kõik antud vahemiku naturaalarvud 1,2,3....n ning nende seast hakatakse järjest välja kriipsutama n-1 kordseid arve. Alles jäävad vaid algarvud.
[24].Naturaalarvude kanooniline kuju. Suurim ühistegur ja vähim ühiskordne.
Iga naturaalarvu n saab esitada kujul n = , ehk sisuliselt teatud (astmesse tõstetud) algarvude korrutisena. Arv n jagub kõigi nende algarvudega p. Iga naturaalarv n on esitatav täpselt ühe unikaalse kanoonilise kuju avaldisena.
Nt. 35 = 5*7 ==> Kanoonilise kuju näide.
*Suurim ühistegur(SÜT)- Naturaalarvude a ja b ühisteguriks nimetatakse igat naturaalarvu, millega jaguvad nii arv a kui ka arv b. Selliste ühistegurite hulgast suurim ongi suurim ühistegur, inglise keelses kirjanduses gcd e. Greatest Common Divisor.
*Suurima ühisteguri leidmist on mugav sisse programmeerida algoritmilise Eukleidese meetodi baasil. Eukleidese algoritm võimaldab hästi lahendada ka lineaarseid diofantilisi võrrandeid ning kongruentse.
*Kahte arvu nimetatakse üksteise suhtes „relatiivselt algarvuliseks“, kui nende arvude a ja b jaoks ei leidu ühest suuremat ühistegurit. (Tegelikkuses ei pruugi nad kumbki olla algarvud).
*Vähim ühiskordne(VÜK)- Arvude a ja b vähim ühiskordne on nende arvude vähim ühiskordne tegur e. sisuliselt vähim arv, kus teguritena sisalduvad mõlemad arvud a ja b. Vähim ühiskordne ning suurim ühistegur on duaalsed mõisted. Vähimat ühiskordset on samuti võimalik leida Eukleidese algoritmi abil. Äärmiselt kasulik on siin omadus a*b = lcm(a,b) * gcd(a,b)
[25].Fermat teoreem. Pseudoalgarvud ja Carmichaeli arvud.
*Fermat’ väike teoreem- teoreem ütleb, et kui p on algarv, siis iga täisarvu a korral, mis ei jagu p-ga, kehtib seos p|ap-1 – 1 , samaväärne esitus on p|ap – a.
*Fermat’ teoreemi avastas prantsuse matemaatik Pierre de Fermat 17. sajandil.
*Teoreem on väga tähtis ka tänapäevases maailmas, kuna kürpteerimine on sageli seotud algarvudega ning just Fermat’ teoreem võimaldab välja selgitada, kas arv x on algarv.
*Mõningatel juhtudel võib aga Fermat’ teoreem anda positiivse tulemuse ka siis, kui p ei ole tegelikult algarv:
Pseudoalgarvud- pseudoalgarvud on sellised kordarvud, mis teatud aluse a korral võivad Fermat’ teoreemi järgi „käituda“ kui algarvud. Pseudoalgarvude probleemi võimaldab aga lahendada Fermat’ teoreemi rakendamine mitmel erineval alusel a. Kui näiteks Fermat’ teoreemi rakendada mingi arvu p jaoks 10 erinva aluse a baasil, on eksimisvõimalus juba väiksem, kui 0,1%.
Carmichaeli arvud- Carmichaeli arv on paaritu kordarv, mis rahuldab Fermat’ teoreemi väidet iga aluse korral. Carmichaeli algarvud on Fermat’ teoreemi suurimaks kirstunaelaks. Selleks aga, et Carmichaeli arvude probleemist kõrvale hiilida, rakendataksegi tänapäeval põhiliselt Miller-Rabini testi, mis on Fermat’ teoreemi täiendatud versioon.
[26].Eukleidese algoritm.
* Eukleides algoritm on nö. süsteemne ning algoritmiline viis leidmaks kahe arvu suurimat ühistegurid (gcd). Kuigi kahe arvu suurima ühisteguri leidmiseks leidub ka teisi heuristilisi mooduseid, on eukleidese algoritm nendest optimaalseim:
a). Algoritmi programmsel realiseerimisel on välistatud kõiksuguste silmuste tekkimine, st. programm lõpetab ALATI oma töö.
b). Ta annab tulemuseks 100%-kindlusega suurima ühisteguri.
c). Algoritm käib äärmiselt efektiivselt ümber arvuti ressurssidega nagu ka loengus mainitud sai. Sisuliselt „loeb ta vaid korra sisse“ kõik ette antud operandid. Algoritmil kulub tulemuse saamiseks aega ülimalt 1 sammu.
*Sõnades võib algoritmi tööd esitada järgmiselt:
a). Valime b ossa suurema kahest arvust gcd(a,b).
b). Jagame b’d a’ga, saame jäägi r ning asendame b selle jäägiga r.
c). Pöördume tagasi silmuse algusesse või kui a on 0, siis väljastame b gcd’na.
*Lisaks: Eukleidese algoritm on äärmiselt laia kasutust leidnud ka arvuteooria erinvates rakendustes, kuna ta võimaldab näiteks leida lineaarsetele diofantilistele võrranditele täisarvulisi lahendeid või siis lahendada kongruentseid võrrandeid moodulil m.
[27].Lineaarsed diofantilised võrrandid.
*Lineaarsed diofantilised võrrandid e. Diophantose võrrandid on mitme tundmatuga ning täisarvuliste kordajatega algebralised võrrandid, millele otsitakse täisarvulisi lahendeid.
*Lineaarsele diofantilisele võrrandile leiduvad täisarvulised lahendid parajasti siis, kui gcd(a,b)|c. Kui viimane tingimus pole täidetud, siis täisarvulisi lahendeid võrrandil ei leidu.
*Lahendamiseks kasutatakse harilikult laiendatud Eukleidese algoritmi iteratiivset meetodit. (Teiste meetoditena leiduvad veel näiteks rekursiivne meetod ning tabeli meetod) *Vastuse saamisks on vaja leida kordajad s ja t, millest seejärel arvutatakse võrrandi lahendid kujul x = ning y = .
*Mõningatel juhtudel on lineaarsetel diofantilistel võrranditel ka mitu erinevat lahendit.
*Lineaarsete ning teist järku diofantiliste võrrandite teooria on põhjalikult välja töötatud, kuid kõrgemat järgu diofantiliste võrrandite lahendamiseks teooria puudub: teada on vaid erivõtteid üksikute juhtude lahendamiseks.
[28]. Täisarvude kongruentsid. Kongruentside omadusi.
*Öeldakse, et täisarvud a ja b on kongruentsed mooduli m>0 järgi, kui nad annavad jagamisel m-iga sama jäägi. Kongruentsi tähistatakse a ≡ b (mod m).
*Kongruentside üldisemaid matemaatilisi omadusi:
*Kongruentsidele kehtib refleksiivsus , st. a ≡ a (mod m).
*Kongruentsidele kehtib sümmeetria, st. a ≡ b (mod m)  b ≡ a (mod m) ehk kui a on kongruentne b’ga, on ka b kongruentne a’ga.
*Kongruentsid on transitiivsed, st. kui a ≡ b (mod m) ning a ≡ c (mod m), siis igaljuhul ka a≡c (mod m).

*Kongruentsidel on ka terve rida spetsiifilisemaid, algebralisi omadusi:
1). Kui a ≡ b (mod m) ning d|m, siis a ≡ b (mod d) ehk kui moodulit on võimalik läbi jagada mingi väiksema arvuga, siis võib seda teha ilma, et kongruents kaotaks kehtivuse.
2). Kui a ≡ b (mod m) ning c ≡ d (mod m), siis a + c ≡ b + d (mod m), ehk sama mooduliga kongruentside puhul võib avaldise vastavad pooled omavahel liita.
3). Kui a ≡ b (mod m) ning c ≡ d (mod m), siis a - c ≡ b - d (mod m), ehk sama mooduliga kongruentside puhul võib avaldise vastavad pooled üksteisest lahutada.
4). Kui a ≡ b (mod m) ning c ≡ d (mod m) siis a*c ≡ b*d (mod m), ehk sama mooduliga kongruentside puhul võib avaldise vastavad pooled omavahel korrutada.
5). Kui ak ≡ bk (mod m) siis samuti a ≡ b (mod m), ehk kui mooduli pooli on võimalik läbi jagada mingi arvuga, võib seda.
6). Kui a ≡ b (mod m) siis suvaliste täisarvude u ja v korral a + um ≡ b + vm (mod m), ehk moodulikordseid võib alati kongruentsi mõlemale poolele liita.
7). Kui ak ≡ bk (mod mk), siis a ≡ b (mod m) ehk võimalusel võib a, b ning mooduli läbi jagada mingi naturaalarvuga k.
*Kokkuvõtteks: täisarvude kongruentse on hea kasutada näiteks suurte väärtustega jagamistehetes jäägi väljaselgitamiseks.
[29]. Moodularitmeetika.
*Moodularitmeetikat kutsutakse sageli ka „kella aritmeetikaks“ ning see on täisarvude jaoks defineeritud aritmeetika süsteem, kus numbrid „teevad täisringi“ pärast mingi kindla väärtuse (moodulini) jõudmist.
*Moodularitmeetika moodsa lähenemise esimesteks juurutajateks olid Sveitsi matemaatik Leonhard Euler ning Saksa matemaatik Carl Friedrich Gauss .
Moodularitmeetika matemaatilisi omadusi:
*Moodularitmeetikas kehtivad kommutatiivsus , assotsiatiivsus, fakt, et liitmine on lahutamise pöördtehe jne.
*Juhul, kui moodul m on algarv, on moodularitmeetikas defineeritud ka jagamistehe. (Kusjuures mitte-algarvulise mooduli korral jagamistehe üks-üheselt määratud ei ole).
*Suvalise jagatise y = a/b leidmiseks moodularitmeetikas peame esmalt leidma jagatise kujul y = 1/b ning alles pärast seda korrutame y = 1/b’i soovitud lugejaga a’ga läbi, et saada meelepärane lõppjagatis.
*Selleks, et leida aga avaldise 1/b väärtust, peame jällegi rakendama Eukleidese algoritmi laiendatud versiooni kujul gcd(x,p).
*Jagamistehte olemasolu võimaldab meil teatud juhtudel lahendada modulaararitmeetilisi lineaarseid võrrandeid ning isegi modulaararitmeetilisi võrrandsüsteeme.
*Alternatiivselt on moodularitmeetilisi võrrandeid võimalik lahendada mooduli kordsete liitmismeetodiga ning võrrandsüsteeme hiina jäägiteoreemi abil.
*Lisaks 12-tunnisele kellale on headeks moodularitmeetika näideteks veel nö. „nädalapäevade aritmeetika“ (mod 7) ning Boole’i loogikaalgebra (mod 2).
[30]. Algarvulisuse Fermat‘ test. Miller-Rabini test.
*Fermat test:
Fermat’ teoreemist tulenevalt on teada, et kui p on algarv ja 1 a ap - 1 ≡ 1 (mod p)
ehk ap ≡ a (mod p).
*Seega, et Fermat’ testi abil kontrollida, kas naturaalarv n on kordarv või algarv:
a).Kirjutan teatud hulga juhuslikult valitud aluste a = 2, 3 ,... n – 1 baasil välja kongruentsi an-1 ≡ 1 (mod n). Kui antud kongruents osutub paari suvalise aluse korral kehtivaks, on suhteliselt tõenäoline, et n’i näol on tegu algarvuga. (Tõenäosus, et arv n on algarv on
p(A) = 1 - 1/(2 s) *100% , kus s on erinvate katsete arv).
b).Seega 10 katse õnnestumisel on eksimise tõenäosus juba väiksem, kui 0,01%.
*Fermat’ teoreemi miinused:
1. Mõningatel juhtudel on vaja arvutada väga suuri astmeid => võimalik siiski lahendada ruututõstmismeetodiga.
2. Vaja on arvutada väga suurte arvudega => appi tuleb modulaararitmeetika.
3. Arv p võib osutuda pseudoalgarvuks => selle probleemi lahendamiseks tuleb a valida juhuslikult ning Fermat’ testi rakendada korduvalt.
4. Arv a võib osutuda Carmichaeli arvuks => Fermat’ testi puhul ainuke möödapääsmatu probleem; sellest tulebki rakendada efektiivsemad meetodeid nagu nt. Miller-Rabini test.

*Miller-Rabini test:
*Miller-Rabini test on sisuliselt Fermat’ teoreemi karastatud versioon, mis peaks olema immuunne ka Carmichaeli arvude vastu:
a). Vaatleme avaldist an – a = a(an – 1) , kus n on testitav naturaalarv ning a suvaline n’ist väiksem naturaalarv.
b). Eelnevalt esitatud avaldise parem pool lahutatakse rekursiivselt lahti teguriteks vastavalt seosele x2 - 1 = (x – 1)(x + 1). (nii pikalt kui võimalik).
c). Kui avaldis an – a ei jagu n’iga, siis ei jagu selle arvuga ükski tegur. Sellest tulenevalt ei tohi üksi parema poole teguritest jaguda arvuga n. Kui aga vähemalt üks neist teguritest n’iga jagub, on tõenäoliselt tegu algarvuga. Tõenäosuse suurendamiseks tuleks katset korrata mingi teise juhusliku alusega.
[31]. Graafid ja graafide omadused. Ahelad ja tsüklid graafis.
Graaf- graaf on objektidevahelisi seoseid kajastav joonismudel.
Graafidest rääkides eeldatakse tavaliselt, et tegu on lihtgraafiga, st. graafis ei leidu kordseid servi ega silmuseid. Reaalse elu probleemide lahendamiseks tuleb aga paratamatult sageli kasutada ka multigraafe- seal on kordsed servad ning silmused lubatud.
Graafisid on võimalik esitada joonismudelitena, naabrusmaatriksitena või ka tippude hulkadena.
Graafe jaotatakse veel oma servade iseloomu poolest:
Orienteerimata graafid- Graafi servade hulk E(G) koosneb vaid suunamata servadest, st. kõiki graafi servi on võimalik läbida korduvalt mistahes suunas.
Orienteeritud graafid e. o-graafid- Graafi servade hulk E(G) koosneb suunatud servadest e. kaartest, mida on võimalik läbida vaid ühes defineeritud suunas.
Sidus graaf- kui graafi mistahes tipust A leidub tee graafi mistahes teise tippu B siis öeldase, et tegu on sidusa graafiga.
Tipu aste e. valents- graafi tipu aste on selle tippuga seotud servade arv.
TEE e. ahel graafis G = (V,E) on servade järjestus tipust x tippu y.
LIHTTEE e. lihtahel graafis G on selline tee, milles ei esine korduvaid tippe.
KINNINE TEE on tee, kus x0 = xk e. tee lõppeb oma alguspunktis.
TSÜKKEL on kinnine lihttee.
Tähstsamaid teoreeme:
*Suunamata lihtgraafis on alati paarisarv paaritu asmtega tippe. – antud tingimus osutub sageli kasulikuks erinevate ülesannete lahendamisel, kus tippude valentside hulga järgi on vaja välja selgitada, kas antud graafi on ka reaalselt võimalik joonistada.
Sidususkomponent- graafi G sidususkomponent on selle graafi G maksimaalne sidus alamgraaf .
[32]. Euleri graafid. Hamiltoni tsüklid.
Euleri tsükliks graafis G=(V,E) nimetatakse sellist servade järjestust, mis läbib graafi igat serva täpselt 1 kord ning servade järjestus lõppeb oma alguspunktis.
Euleri graaf on graaf, mis sisaldab Euleri tsüklit.
Euleri ahel on lahtine servade järjestus, kus igat serva läbitakse täpselt 1 kord.
Euleri semigraaf on graaf, mis sisaldab Euleri ahelat .
Kui mingi graaf on Euleri graaf, siis:
a). Graaf on sidus.
b). Kõikkide tippude aste peab olema paarisarvuline.
c). Servade hulk E esitub paarikaupa lõikumatute tsüklite ühendina.
Algoritm Euleri tsükli leidmiseks graafis G: Esmalt eraldatakse G servade hulgast ükshaaval tsüklid ning seejärel pannakse tsüklitest kokku Euleri ahel.
Teooria arendajaks oli Leonhard Euler(18. saj) – Köeningsbergi sildade probleem.
Hamiltoni tsükliks graafis G = (V,E) nimetatakse sellist graafi servade järjestust, mis läbib graafi igat tippu täpselt 1 kord ning servade järjestus lõppeb oma alguspunktis.
Hamiltoni graaf on graaf, mis sisaldab Hamiltoni tsüklit.
Hammiltoni ahelaks graafis G nimetatakse lahtist servade järjestust, kus igat tippu läbitakse täpselt 1 kord.
Hamiltoni semigraaf on graaf, mis sisaldab Hammiltoni ahelat.
Algoritm Hamiltoni tsükli leidmiseks graafis G: Hamiltoni tsükli leidmine on NP-keerukas ülesanne, seega puudub konkreetne algoritm.
Leidub vaid üksikuid seaduspärasusi, mille järgi saab öelda, et graafis Hamiltoni tsüklit ei leidu- näiteks kui graaf koosneb kahest suuremast sidususkomponendist, mille vaheliseks „sillaks“ on üksainus tipp, ei ole graafis kindlasti Hamiltoni ahelat.
Teooria arendajaks oli William R. Hamilton(19. saj).
[33]. Puud. Puude omadused.
Puu on defineeritud, kui sidus tsükliteta orienteerimata graaf.
Puude omadusi:
a). Puu on alati sidus.
b). Puus ei sisaldu tsükleid.
c). Puus leidub alati n-1 serva, kus n on tippude arv.
d). Iga puu koosseisus leiduv serv on sild .
e). Suvalise serva lisamisel mistahes kahe puu tipu vahele tekib tsükkel.
f). Suvalise kahe tipu vahel leidub alati täpselt 1 lihtahel.
Mets- graaf, mis ei sisalda tsükleid (ent ei pruugi olla ka sidus).
Lehed- Lehed on puu tipud , mille astmeks on 1 (e. deg(e) = 1).
Sild- Sidusa graafi G=(V,E) serva e ∈ E nimetatakase sillaks, kui selle serva eemaldamisel muutuks graaf mittesidusaks.
Rakenduses esineb sageli ka juurega puid st. tippude hulgast on välja eraldatud üks tipp, juur . Serva seda otstippu, mis asub juurele lähemal, nimetatakse sellisel juhul ülemtipuks, teist otstippu aga alamtipuks.
[34]. Graafi vähima kaaluga aluspuud.
Graafi aluspuu - sidusa graafi G aluspuu on vähima servade arvuga alamgraaf, mis ühendab kõiki graafi tippe. Cayley teoreemist järeldub, et igal n-tipuliselt täisgraafil on kokku nn-2 erinevat aluspuud.
Graafi serva kaal- on servale omistatud teatav positiivne reaalarv .
Graafi vähima kaaluga aluspuu leidmisel püütakse seega välja selgitada selline optimaalne aluspuu, kus kõikkide allesjäänud servade kaalude summa oleks minimaalne.
Kruskali algoritm- efektiivseim teadaolev algoritm minimaalse kaaluga aluspuude leidmiseks.
Sammud algoritmi kasutamiseks:
a). Olgu G kaalutud n-tipuline graaf.
b). Valime graafist G vähima kaaluga serva e1.
c). Iga järgneva i = 2,3,...n-1 korral valime graafist G sellise vähima kaaluga serva ei, mis erineb servadest e1,e2,...,ei-1 ja ei moodusta koos eelnevate servadega tsüklit.
Teooria arendajaks oli Martin Kruskal(20. saj).
Vähima kaaluga aluspuude leidmise ülesanne on äärmiselt aktuaalne näiteks logistikavaldkonnas (selgitamaks välja veokite optimaalset trassi, maanteede efektiivseimat paigutust jne).
Kruskali algoritm kuulub nö. „ahnete algoritmide klassi“, nende algoritmide iseloomulik tunnus on see, et igal sammul täiendatakse kontruktsiooni just niisuguse objektiga, mille valimine näib just sel hetkel kõige soodsam , pööramata aga tähelepanu sellele, et hilisematel sammudel tuleb seetõttu võibolla teha ebasoodsaid otsuseid.
[35]. Märgendatud puud. Puude esitamine arvuti mälus.
Märgendatud puu korral on igale puu tipule omistatud konkreetne naturaalarvuline tähis hulgast <.
Reaalsetes rakendustes tegeldaksegi rohkem märgendatud puudega (neid puudutav teooria on seetõttu ka mahukam), märgendamata puid uuritakse suures osas vaid matemaatilistel ning arvutustehnilistel kaalutlustel .
Märgendatud puude esitusviisid arvutimälus:
a). Naabrusmaatriksina- traditsiooniline graafi esitusviis, kus nii maatriksi ridadele kui ka veergudele vastavad graafi tipud ning 1’ga on tähistatud elemendid, kus kahe tipu vahel leidub serv. Ebaefektiivne ning mälu raiskav esitusviis. Vajadus mälus järele:
b). Servade loendina- servade loendi puhul on puu esitatud kaheelemendiliste järjenditena, kus järjendi komponentideks on puu tipud, mida serv ühendab. Tunduvalt efektiivsem esitusviis naabrusmaatriksist. Vajadus mälu järele: 2n.
c). Prüferi koodina- Prüferi koodi moodustamine koosneb laias laastus vähima märgendiga lehe leidmisest ja selekteerimisest, tema naabertipu ülesmärkimisest, ning antud tipu kustutamisest. Kõige efektiivsem märgendatud puude esitusviis arvuti mälus. Vajadus mälu järele: (n-1).
[36]. Prüferi kood. Märgendatud puude loendamine. Cayley teoreem.
Prüferi kood on kindlat märgendatud puud esitav arvujada pikkusega n - 2, kus n on antud puu tippude arv. Iga puu prüferi kood on unikaalne .
Puu esitamine Prüferi koodina-
a). Esmalt teen kontrolli mõttes kindlaks puu Prüferi koodi pikkuse (n-2).
b). Otsin puu koosseisust üles vähima märgendiga lehe, kirjutan üles tema märgendi ning selle alla tema naabertipu märgendi ning kustutan antud lehe puust.
c). Kordan rekursiivselt sammu b, kuni säilinud on vaid 1 tipp.
d). Prüferi koodi moodustavadki alumise rea esimesed n-2 elementi.
Puu taastamine Prüferi koodi järgi:
a). Kirjutame puu Prüferi koodi üles nö. „alumise reana“, koodi lõppu lisame tingimuse n-2 põhjal veel ühe elemendi, milleks on tippude arv n.
b). Seejärel hakkame konstrueerima ülemist rida: esimese elemendina paneme kirja vähima arvu, mis ei esine alumises reas.
c).Järgnevateks ülemise rea väärtusteks on alati need vähimad tippude märgendid, mis ei sisaldu juba ülemises reas vasakul ega alumises reas all või paremal.
d). Kordan sammu c rekursiivselt, kuni täitunud on terve ülemine rida.
e). Tulemuseks saan sisuliselt puu servade loendi, mille alusel on lihtne ka puu välja joonistada.
Prüferi kood on kõige efektiivsem märgendatud puude esitusviis arvuti mälus. Ligikaudne vajadus mälu järele: (n-1)
Cayley teoreem- n-tipuliste märgandatud puude arv on nn-2. (Üks tähtsamaid puusid puudutavaid teoreeme). (Esialgselt saigi Prüferi kood leiutatud Heinz Prüferi poolt selleks, et tõestada Cayley teoreemi aastal 1918).
[37]. Märgendamata puude arv.
Märgendamata puude korral tippudele tähiseid ei omistata ning seega on neid ka vähem, kui märgendatud puid. (Kuna puud, mis muidu oleksid teineteisest erinenud oma märgendite poolest, osutuvad nüüd isomorfseteks).
n-tipuliste märgendamata puude arv rahuldab võrratusi ehk
(kui n>30). See tähendab, et puudub algoritm arvutamaks n-tipuliste märgendamata puude täpset arvu. Teada on vaid antud vahemik, kuhu see arv langeb.
a). Alumine tõke tuleneb sellest järeldusest, et iga n-tipulist puud saab erinvate märgenditega märgendada täpselt n! viisil.
b). Ülemine tõke tuleneb aga juurega puude kõikvõimalike planaarkoodide arvust – On ju selge, et puid peab olema vähem kui erinevaid planaarkoode, kuna planaarkoodid pole üheselt määratudki. Seega on ülemiseks tõkkeks 22(n-1).
Planaarkood e. binaarkood- tehnika, mida kasutatakse märgendamata puude esitamiseks ning salvestamiseks. Kuna kõiki puu servi läbitakse 2 korda: edasi ning tagasi minnes, on n-tipulise puu binaarkoodis 2(n-1) kahendkohta. Binaarkoodi põhjal saab puu üheselt taastada.
*Erinevalt Prüferi koodist, ei ole mingi puu planaarkood üheselt määratud e. unikaalne, kuna puu juureks võib alati valida erinevaid tippe.
[38]. Kooskõlad graafis. Berge’i teoreem.
Kooskõlaks nimetatakse orienteerimata graafi G = (V,E) servade sellist alamhulka M⊂E, kus mistahes kaks serva ei oma kahekaupa võetuna sama otspunkti.
Kooskõlaline e. küllastunud tipp- tipu nimetatakse kooskõlastatuks, kui ta on mõne hulka M kuuluva serva otstipuks.
Maksimaalne kooskõla- kooskõla on maksimaalne, kui mistahes täiendava graafi serva lisamisel hulka M ei oleks see enam kooskõla.
Kooskõla määr- |M|, ehk kooskõlas sisalduvate servade arv.
Maksimumkooskõla- kooskõla on maksimumkooskõla, kui Mi võimsus on kõigist võimalikest väärtustest suurim. (Alustades suvalisest servast saame maksimaalse kooskõla, ent ei pruugi saada maksimumkooskõla).
Täielik kooskõla- kooskõla on täielik, kui graafi iga tipp on mingi kooskõlla kuuluva serva tipp. Täielik kooskõla on alati ka maksimumkooskõla.
Oletades, et graafis G leidub kooskõla M:
M-vahelduv on selline ahel P, kus servade järjestusse kuuluvad servad on kordamööda „kooskõla M“ / „tavalise servade hulga E“ elemendid.
M- laienev on selline ahel P,kus servade järjestuse esimene ning viimane tipp ei ole kooskõlalised e. nad ei sisaldu kooskõla M koosseisus (mõne kooskõla M serva otstipuna).
Berge’i teoreem:
„Kooskõla M⊂E(G) on maksimumkooskõla vaid parajasti siis, kui graafis G ei leidu M-laienevat ahelat“.
(Berge’i teoreem on tegelikult triviaalne- kui ette kujutada näiteks 3-tipulist M-laienevat ahelat kus kooskõlla on valitud keskmine serv, võiksime selle asemel kooskõlla valida hoopis mõlemad ahela äärmised servad, saavutades niiviisi ühe võrra suurema kooskõla määra).
Maksimaalse kaaluga kooskõla leidmiseks on võimalik kasutada Dijkstra lühima tee algoritmi või võrgu maksimaalse voo leidmise algoritmi.
(Rakendusi: infovoogude jaotamine serverite vahel nii, et võrgu läbilaskevõime oleks suurim).
[39]. Kooskõlad kahealuselises graafis. Halli teoreem.
Maksimumkooskõlade leidmise ülesanne jaotub nelja raskusastmesse:
a). Maksimumkooskõlade leidmine kahealuselises graafis.
b). Maksimumkooskõlade leidmine üldises graafis.
c). Maksimumkooskõlade leidmine kaalutud kahealuselises graafis.
d). Maksimumkooskõlade leidmine üldises kaalud graafis.
Vaatleme neist esimest juhtu- lihtsaim on kasutada heuristilist laienevate ahelate meetodit:
Laienevate ahelate meetod:
a). Konstrueerime graafi G tarvis kooskõla M, lisades sellele servi, millel puuduvad kahekaupa võetuna ühised otspunktid.
b). Järgmisena püüan graafis leida M-laienevat ahelat P.
c).Kui selline M-laienev ahel P ka leidub, koostada uus ning suurem kooskõla, mis elimineeriks ahela P.
d). Korrata protsessi seni, kuni on võimalik leida uusi M-laienevaid ahelaid.
Sellist algoritmi järgides saame lõpptulemuseks kooskõla, mis on igaljuhul maksimumkoos-kõla (ning võib osutuda ka täielikuks kooskõlaks).
Hall’i teoreem(e. Halli abielu teoreem)- Halli teoreemi rakendatakse graafi teoorias selleks, et selgitada välja, kas kahealuselises graafis G=(V1+V2, E) leidub täielik kooskõla (e. kõik tipud on küllastunud) või mitte.
HALLI TEOREEM: Oletamegi, et meil on graaf G=(V1+V2, E), kus X on tipuhulga V1 mistahes alamhulk. Tipuhulga X naabrus on hulk NG(X) (naabrusesse kuuluvad kõik sellised graafi tipud, mis on tippude hulga X mistahes elemendist kaugusel 1).
Halli teoreem ütlebki, et täielik kooskõla leidub siis ja ainult siis , kui |X|≤|NG(X)|, ehk kui tippude hulga V1 mistahes alamhulk X omab iseenda võimsusest rohkem naabertippe, leidub täielik kooskõla.
Regulaarses (kõikide tippude aste on sama) kahealuselises graafis, mis pole nullgraaf, leidub täielik kooskõla.
[40]. Tasandiline graaf. Euleri valem: seos tasandilise graafi tippude, servade ja tahkude arvude vahel. Euleri valemi rakendusi.
Tasandiline(planaarne) graaf- graaf on tasandiline e. planaarne, kui teda saab tasandile joonistada nii, et tema servad väljaspool tippe ei lõikuks.
Graafi tahud- graafi joonis tükeldab alati tasandi. Tekkinud tükke nimetatakse G tahkudeks.
Graafil leidub alati ka üks lõpmatu tahk (sisuliselt tahk, mis ümbritseb kogu graafi).
Euleri valem(id):
Teoreem: Olgu graaf G sidus tasandiline graaf, mille tippude arv on n, servade arv m ning joonise tahkude arv f. Sellisel juhul kehtib alati n + f = m + 2 ehk n + f – m = 2.
a). Järeldus 1: Olgu G tasandiline graaf, mille sidususkomponentide arv on k, tippude arv on n, servade arv on m ning joonise tahkude arv f. Sellisel juhul kehtib alati n + f = m + k + 1.
b). Järeldus 2: Olgu G sidus tasandiline graaf. Kui tal on vähemalt 3 tippu e. n = 3, siis kehtib alati m ≤ 3n – 6, kus n tähistab tippude arvu, m servade arvu.
c). Järeldus 3: Täielik graaf K5 ei ole tasandiline, eelmise järelduse põhjal (n=5,m=10).
d). Järeldus 4: Kui G on sidus tasandiline, vähemalt 3 tipuga lihtgraaf , milles pole tsükleid pikkusega 3, siis m ≤ 2n – 4.
e). Järeldus 5: Täielik kahealuseline graaf K3,3 ei ole tasandiline (tuleneb eelmisest omadusest, kuna graafis K3,3 on n = 6 ning m = 9.
f). Järeldus 6: Iga tasandilises lihtgraafis leidub tipp, mille asta on ülimalt 5 – pea tähtsaim omadus. Tähendab seda, et ei saa eksisteerida tasandilist lihtgraafi, mille kõikide tippude aste oleks >5 (vastasel juhul ei saa ta olla tasandiline).
(K5 ja K3,3 on meile niivõrd tähtsad seetõttu, et IGA mittetasandiline graaf sisaldab ÜHTE neist alamgraafina).
Euleri valem on väga tähtis, kuna ta võimaldab meil mistahes graafi G kohta välja selgitada, kas viimane on tasandiline (e. kas ta on tasandil esitatav selliselt, et mistahes 2 serva ei lõikuks).
[41]. Graafi tasandilisuse kriteeriumid. Kuratowski teoreem.
Graafi tasandilisuse kriteeriumid panevad kõige täpsemini paika Kuratowski ja Wagner:
Homöomorfism e. topoloogiline isomorfism on kahe topoloogilise ruumi üksühene vastavus, teisendades säilitatakse objekti topoloogilised omadused. Kaks graafi G1 ja G2 on homöomorfsed, kui nad on mõlemad saadavad mingi graafi G’ servasid poolitades.
Näiteid homöomorfismidest: tass => kohver => sõõrik;
Väga tuntud homöomorfism on ka nö. trefoil’i sõlm, mis on iseenesest samuti homöomorfne sõõrikuga.
Kuratowski’ teoreem: Graaf on tasandiline parajasti siis ja ainult siis, kui ta ei sisalda alamgraafi, mis oleks homömorfne kas graafiga K5 või K3,3.
Teisisõnu, graaf G ei ole tasandiline parajasti siis, kui temas sisaldub K5 või K3,3 järgmiselt:
1). Graafi G tipud on K5 või K3,3 tippudeks.
2). Graafi G lihtahelad, mis ei lõiku (v.a. otstippudes) – lihtahelate koosseisus sisalduvad tipud on sel juhul tekitatud serva poolitamise operatsiooniga(ning seega graafid on homoömorfsed) on K5 või K3,3 servadeks.
K.Wagneri teoreem: Graaf on tasandiline parajasti siis, kui ta ei sisalda alamgraafi, mis servi kokku tõmmates on muudetav graafiks K5 või K3,3.
Serva kokkutõmbamise operatsioon – kahte servaga intsidentset tippu lähendatakse teineteisele lõpmatult (paratamatult lähenevad teineteisele ka muud tipuga ühendatud servad).
Näiteks kuulus Peterseni graaf on serva kokkutõmbamise operatsiooni abil esitatav täisgraaf K5’na.
[42]. Graafi tippude värvimise ülesanne. Brooksi teoreem (tõestuseta).

Üldisemad definitsioonid :
Graafi tippude värvimise ülesanne seisneb värvide omistamises graafi tippudele selliselt, et mistahes kaks omavahel servaga ühendatud tippu (naabertippu) oleksid erinevat värvi. Seega tuleb „naabertipud“ „värvida“ erinevalt.
Graafi G kromaatiline arv on minimaalne selline värvide arv k, mille abil on võimalik ära värvide kõik graafi tipud nii, et naabertipud oleksid erinevat värvi.
k-aluseliseks graafiks nimetatakse mistahes graafi, mille kõik tipud on värvitavad k erineva värviga. Nt: kromaatiline arv 1 on vaid tühjal graafil; kromaatiline arv 2 on kahealuselisel graafil jne.
Klikiks nimetatakse lihtgraafi G mingit alamgraafi G’, mis on ühtlasi täisgraaf Kx.

Graafi tippude värvimise ülesanne:
Oletame, et ∆G on graafi maskimaalne aste.
Teoreem: Silmuseta graaf G = (V;E) on värvitav vähemasti ∆G + 1 värviga. (saab tõestada induktsiooniga).
Brooksi teoreem:
„Oletame, et G = (V,E) on silmuseta graaf ning d≥. Kui G’s pole (d+1)-elemendilist klikki, siis on graaf G värvitav d värviga“.
Sisuliselt seab Brooksi teoreem omavahel suhtesse graafi tipu maksimaalse astme ning kromaatilise arvu.
Teoreemi järgi on mistahes graafis, mille igal tipul v∈V on maksimaalselt ∆(G) naabrit tipud võimalik värvida ainult ∆(G) erineva värviga, va. juhul kui:
*G on klikk või
*G on paaritu pikkusega tsükkel.
Viimastel juhtudel on graafi tippude värvimiseks vaja siiski ∆(G) + 1 värvi.
(Jõhkralt pika tõestusega teoreem).
[43]. Tasandilise lihtgraafi värvimine 6 ja 5 värviga. Neljavärviprobleem ja kaartide värvimine.
Tasandilise lihtgraafi värvimine 6 värviga:
Teoreem: Tasandiline lihtgraaf G = (V,E) on värvitav 6 värviga.
Tõestus: Tõestus baseerub sellel, et igas tasandilises graafis peab leiduma tipp v ∈ V, mille puhul deg(v) ≤ 5. Tõestatakse induktsiooniga.
Tasandilise lihtgraafi värvimine 5 värviga:
Teoreem: Tasandiline lihtgraaf G = (V,E) on värvitav 5 värviga.
Tõestus: Tõestus baseerub sellel, et igas tasandilises graafis peab leiduma tipp v ∈ V, mille puhul deg(v) ≤ 5. Samuti on vajalik tõestuse käigus kasutada serva kokkutõmbamise operatsiooni. Tõestatakse induktsiooniga.
Neljavärviprobleem:
Graafi teoorias väga palju „tuntust kogunud probleem“, mis iseenesest tuleneb mitte niivõrd olulisest rakenduslikust küsimusest. Nimelt: kas suvalist poliitilist kaarti ( tasapinnal või keral ) saab värvida nelja või väiksema arvu värviga nii, et mistahes kaks ühise piiritükiga riiki oleksid erinevat värvi?
Probleem on lihtsalt taandatav graafde värvimise ülesandele: (tähistades erinevad riigid kaardil graafi G tippudega ning piirid riikide vahel servaega).
Neljavärvi probleemi lahendus: Iga tasandiline graaf G=(V,E) on värvitav 4 värviga.
„Probleemiks“ ongi neljavärviprobleemi puhul see, et „lahendust“ pole kunagi suudetud ammendavalt tõestada. Selle kohta on küll vigaseid - ning arvuti „proof by exhaustion“-tüüpi tõestuseid, ent konkreetne matemaatiline tõestus puudub tänaseni. (Arvuti tõestused: G.Gonthier, 2002).
Enamik kaarte on tegelikult värvitavad lausa 3 värviga, neljandat värvi on tarvis siis, kui üks riikidest on ümbritsetud paaritu arvu teiste riikide „tsükliga“:
NB! Neljavärviprobleemi puhul eeldatakse, et ühel riigil pole teineteisega mitte-ühendatud territooriume (nagu Venemaal Kaliningradi oblast).
34