ühte igast järgnevast funktsioonist: 0 mittesäilitav, 1 mittesäilitav, mittepööratav, mittemonotoonne, mittelineaarne **** Graafid Graaf: objektidevaheliste seoste joonismudel, mis koosneb tippudest ja kaartest. Orienteerimata graaf: kõik kaared suunamata, neid tähistatakse harilike joontega Orienteeritud graaf: kõik kaared suunatud, neid tähistatakse nooltega Ahel: tee orienteerimata graafis Alamgraaf: graaf on mingi graafi alamgraaf, kui ta on selle graafi mingi taandatud graafi jääkgraaf Baas: selline minimaalne tippude osahulk, kus selle osahulga tippudest leidub tee selle graafi mistahes tippu (orienteeritud graafis) Elementaarahel: elementaartee orienteerimata graafis Elementaartee: tee, mis ei läbi ühtki graafi tippu üle ühe korra Euleri ahel: läbib täpselt 1 kord kõik orienteerimata graafi kaared, aga ei lõpe oma algustipus. Euleri graaf: (orienteerimata) graaf, mis omab Euleri tsüklit.
graafil. Euleri graaf omab euleri tsüklit. Orienteerimata graafi Euleri tunnuseks on sidusa graafi paarisarvuline tippude aste. Orienteeritud graafi Euleri tunnuseks on sisend ja väljunastmete võrdsus. Hamiltoni graaf omab hamiltoni tsüklit. Jääkgraafil saab ära jätta kaared, aga tipud säilivad. Taandatud graafil saab ära jätta tipud ning nende kaared. Alamgraaf on graaf, millele on rakendatud nii jääkgraaf kui ka taandatud graaf. Graaf on kahealuseline, kui tema tipud jagunevad kaheks mittelõikuvalt osahulgaks. Tasandiline graa on paigutatav tasandile nii, et kaared ei lõiku. Baas on selline minimaalne tippude hulk, kus selle hulga tippudest leidub tee graafi mistahed teise tipuni. Sõltumatute tippude hulk on graafi osahulk, kus 2 suvalist tippu pole omavahel ühendatud.
( ) 0 1 00 R= 0 0 10 0 0 01 0 1 00 Relatsiooni astme maatriks Relatsiooni astme maatriksi saab leida järjestikuse korrutamise teel: 1 R =R Rn+1 =Rn ∘R GRAAFID 33. Graafi definitsioon. Tipud, servad. Multigraaf. Täisgraaf, nullgraaf, täiendgraaf. Kaalutud graaf. Intsidentsus. Naabertipud. Graafi naabrusmaatriks. Alamgraaf. Regulaarne graaf. [2] Graaf, tipud, servad o Graaf on punktide hulk (tavaliselt lõplik), kus mõned punktid on ühendatud joontega. o DEF. Graaf on paar G = (V,E), kus V on mittetühi hulk ning E hulk, mille elementideks on hulga V kaheelemendilised alamhulgad. Hulga V elemente nimetatakse graafi tippudeks, hulga E elemente aga servadeks. Ülaltoodud graafi puhul näiteks on V = {A,B,C,D,E} Ja E = {{A,B}, {A,C}, {A,D}, {A,E}, {B,C}, {C,E}}.
c. Tõestus 2. https://moodle.ut.ee/mod/url/view.php?id=107318 lk 64 65 d. Lähtudes ühetipulisest graafist, saab konstrueerida puu, kui igal sammul lisades ühe tipu ning ühendada see servaga ühe suvalise tipuga juba olemasolevast graafist. Tekkinud graaf on puu: ta on sidus, sest igas tipust on võimalik liikuda kõige esimesse tippu, ning ei sisalda tsükleid, sest suvalise serva eeldamisel eraldub serva otstipu külge kinnituv alamgraaf ülejäänud graafist. 43) a. Tarvilikud ja piisavad tingimused, et graaf oleks puu. https://moodle.ut.ee/mod/url/view.php?id=107318 lk 66. 44) a. Teoreem. Graaf G on puu parajasti siis, kui tema iga kahte erinevat tippu ühendab täpselt üks lihtahel. b. Tõestus. https://moodle.ut.ee/mod/url/view.php?id=107318 lk 67. 45) a. Märgendatud puuks nimetatakse sellist n-tipulist puud, mille igale tipule on
paarisarvulised. 15. Milline on Euleri graafi tunnus orienteeritud graafi korral? Orienteeritud graaf on Euleri graaf, kui ta omab Euleri kontuuri ehk iga tipu sisend- ja väljundaste on võrdsed. 16. Mis on jääkgraaf? Jääkgraaf on graaf, mis saadakse osade kaarte ärajätmisega, kusjuures kõik tipud säilivad. 17. Mis on taandatud graaf? Taandatud graaf on graaf, kus on ära jäetud osad tipud ja nendega seotud kaared. 18. Mis on alamgraaf? Alamgraaf on graaf, mis on mingi graafi taandatud graafi jääkgraaf ehk on sellele graafile samaaegselt nii taandatud graaf kui ka jääkgraaf. 19. Milline graaf on kahealuseline? Graaf on kahealuseline, kui tema kõik tipud jagunevad kaheks mittelõikuvaks osahulgaks selliselt, et graafi iga kaar seob ühe osahulga mingit tippu teise osahulga mingi tipuga. 20. Milline graaf on tasandiline? Graaf on tasandiline, kui ta on paigutatav tasandile selliselt, et ta kaared ei lõiku. 21
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)
lõppeb samas tipus Suunatud tsükliks nimetatakse suunatud kinnist ahelat, kus on vähemalt üks kaar ja ükski kaar ei kordu Suunatud lihttsükliks nimetatakse tsüklit, kus ükski sisetipp ei kordu Suunatud graafi nimetatakse tugevalt sidusaks, kui iga kahe tipu u ja v korral leidub suunatud ahel tipust u tippu v Suunatud graafi niemtatakse nõrgalt sidusaks, kui tema alusgraaf on sidus Suunatud graafi tugevalt sidus komponent on selline tugevalt sidus alamgraaf, mis ei sisaldu üheski teises tugevalt sidusas alamgraafis o Graaf on tugevalt sidus parajasti siis, kui tal on täpselt üks tugevalt sidus komponent Teoreem suundade määramisest: kui sidusas (suunamata) graafis ei leidu ühtegi silda, siis saab graafi servadele määrata suunad nii, et tekkinud suunatud graaf on tugevalt sidus Suunatud graafe =(,) ja '=(',') nimetatakse isomorfseteks, kui
graafi kaared, kuid ei lõpe oma algustipus. Sidus graaf on Euleri graaf, kui tema kõikide tippude aste on paarisarvuline. Graafi 𝐺 = (𝑇, 𝐾) jääkgraaf on graaf 𝑄 = (𝑇, 𝐵), kus 𝐵 ⊂ 𝐾. Seega saadakse jääkgraaf osade kaarte ärajätmisega, kusjuures kõik tipud säilivad. Graafi -..- taandatud graaf on graaf 𝑄 = (𝐷, 𝐵), kus on ära jäetud osad graafi G tipud ja nende tippudega seotud kaared, seega 𝐵 ⊂ 𝐾 𝑗𝑎 𝐷 ⊂ 𝑇. Graaf on teisele alamgraaf, kui ta on sellele graafile samaaegselt nii jäägraaf kui ka taandatud graaf. Graaf on kahealuseline, kui tema tipud jagunevad kaheks mittelõikuvaks osahulgaks selliselt, et graafi iga kaar seob ühe osahulga mingit tippu teise osahulga mingi tipuga. Graaf on tasandiline, kui ta on paigutatav tasandile selliselt, et ta kaared ei lõiku. Orienteeritud graafi baas B on selline minimaalne tippude osahulk BcT, kus hulga B tippudest leidub tee selle graafi mistahes teise tipuni
annaabi.ee 
