) Jääkgraaf: saadakse graafist osade kaarte ärajätmisega, kusjuues kõik tipud säilivad Kahealuseline graaf: graaf on kahealuseline, kui kõik tema tipud jagunevad kaheks mittelõikuvaks osahulgaks nii, et graafi iga kaar seob ühe osahulga mingit tippu teise osahulga mingi tipuga. Kontuur: suletud elementaartee orienteeritud graafis Kromaatiline arv: minimaalne arv, mis näitab, mitme erineva värviga õnnestub graafi tipud värvida nii, et naabertipud oleks eri värvi Lihtahel: lihttee orienteerimata graafis Lihttee: tee, mille koosseisus pole korduvaid kaari (tippe võib) Multigraaf: kordsete kaartega graaf Puu: sidus tsükliteta orienteerimata graaf Pöördgraaf: orienteerimata graafi pöördgraaf on samade tippudega orienteerimata graaf, mis sisaldab kaari nende tippude vahel, kus alggraafis pole kaart ja vastupidi. Sidusus: orienteeritud graaf on sidus, kui igast tema tipust leidub tee igasse teise tippu ja
omavahel ühendatud. Imoforsed graafid omavad samapalju tippe ja kaari ning erinevad üksteisest vaid nimetuse või paigutse poolest. Pöördgraaf sisaldab kaari seal, kus graafil neid pole. Puu on sidu tsükliteta orienteerimata graaf. Puul on n tippu ja n-1 kaart. Kromaatiline arv on minimaalne arv millega saab kõik graafi tipud ära varvida nii, et naabertipud oleksid erivärvi. Graafe saab esitada naabrusmaatriksiga, intsidentsusmaatriksiga. Algebrad: Algebra koosneb alushulgast ja defineeritud tehetest. Tehe on alushulgal kinnine siis, kui rakendada tehet kahe elemendi peale, siis vastus on samuti selle hulga element. Ühe binaarse tehteda algebralist süsteemi nimetatakse grupoidiks. Ühikelement on selline element, millele rakendades tehet suvalise
Orienteerimata graafi G pöördgraaf on samade tippudega orienteerimata graaf, mis sisaldab kaari nende tippude vahel, kus graafis G kaari pole ja vastupidi. Puu on sidus tsükliteta orienteerimata graaf. Kui puul on n tippu, siis tal on (n-1) kaart. Kui puult eemaldada kaar, pole ta enam sidus (pole puu). Kui puule lisada kaar, tekib tsükkel ja pole enam puu. Graafi värvimine on värvide omistamine graafi tippudele selliselt, et mistahes 2 ühendatud kaart oleksid eri värvi (naabertipud eri värvi). Graafi kromaatiline arv on min arv, mis näitab, mitme erineva värviga õnnestub graafi tipud värvida sellised, et naabertipud eri värvi. Kromaatiline arv 1 on ainult tühjal graafil. Kahealuseline graaf -> kromaatiline arv 2 ja vastupidi. On olemas naabrusmaatriks, intsidentsusmaatriks. Klassikalised ülesanded: Köningsbergi sillad (kas on võimalik ületada sillad täpselt 1 kord, jõudes alguspunkti, ei kuna sellisel Euleri graafil pole kõik tippude
29 ( ) 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 =
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.
29. Mis juhtub, kui puule lisada 1 kaar juurde? Kui puule lisada 1 kaar, siis tekib tsükkel ja saadud graaf pole enam puu. 30. Mis on „graafi värvimine“? Graafi värvimine on värvide omistamine graafi tippudele selliselt, et mistahes kaks omavahel kaarega ühendatud tippu oleksid erinevat värvi. 31. Mis on graafi kromaatiline arv? Graafi kromaatiline arv on minimaalne arv, mis näitab, mitme erineva värviga õnnestub graafi tipud värvida selliselt, et naabertipud oleksid erinevat värvi. 32. Millise graafi kromaatiline arv on 1? Kromaatiline arv 1 on ainult tühjal hulgal. 33. Millise graafi kromaatiline arv on 2? Kromaatiline arv 2 on kahealuselisel hulgal. 34. Kui suur võib maksimaalselt olla tasandilise graafi kromaatiline arv?
keegi, siis me paneme algul kanali väärtuseks, et ta on lõpmatult suur. See ei ole kanal, mida saaksime kohe kasutama hakata. Algoritmi väärtus muutub töö käigus. D(v) D väärtus sihtpunktist läbi erinevate võrgusõlmede kuni tipuni v välja. P(v) teepeal olev eelviimane tipp enne viimast v-d. N'- võrgusõlmede hulk, mida oleme algoritmiga läbi vaadanud. Algoritm töötab selliselt: Alguses paneme ühe tipu tippude hulka N ja otsime üles tipu u naabertipud v need mille vahel ei ole rohkem võrgusõlmi ehk lihtsalt kanal. Nende kohta me teame seda kanali väärtust. Kui tippude vahel on rohkem sõlmi kui üks siis nende jaoks me ütleme, et te väärtus on lõpmatult suur. Algoritm töötab sellise põhimõtte järgi, et meil on teada tipp v ja nüüd kui panime juurde sellesse hulka tipu w. Kui leiame, et uuest tipust w on olemas tee tippu v, mille kohta me juba teame teepikkust, siis me võrdleme, kas seni olev
annaabi.ee 
