Seega ei ole need graafid isomorfsed. Vastus: Need graafid ei ole isomorfsed. ÜLESANNE 4. Graafi G sidususkomponentideks nimetatakse tema maksimaalseid sidusaid alamgraafe. Vähim võimalik graafi sidususkomponent on seega üksik tipp, mille aste on 0(ehk selline tipp, mis pole teistega ühendatud). Väide kehtib vaid juhul kui n m, sest graafil ei saa olla negatiivne arv sidususkomponente ning juhul n = m on tal 0 sidususkomponenti ehk tegemist on tühja graafiga, mis on lubatud olukord. Tõestan väite induktsiooniga. Baas. Väide kehtib n = 0 ja m = 0 korral, n m = 0 ehk graafil on 0 sidususkomponenti. Kuna tegemist on tühja graafiga, siis on tal tõepoolest 0 sidususkomponenti ja väide kehtib n = 0 ja m = 0 korral. Induktsioonisamm. Olgu antud suvaline graaf. Valin selles graafis välja suvalise tipu. Tähistan selle tipu t-ga ja olgu selle tipu aste a. Eemaldan graafist selle tipu t ja selle tipuga seotud servad(a serva)
Korrutan pooled 8-ga läbi. 8 15 8 12 (J 17) Y (X ) Nüüd leian y-i. 2 11 + 4 (J 17) 22 + 4 (J 17) -18 (J 17) Y (X ) Kontroll: 1) vp = 2 11 + 16 4 (J 17) pp = 4 (J 17); pp = vp 2) vp = 5 11 - 5 16 9 (J 17); pp = 9 (J 17); pp = vp Seega on leitud lahendid õiged. Vastus: 11 (J 17) ja 16 (J 17) ÜLESANNE 4. Eeldan graafide joonistamisel, et tegemist on märgendamata graafiga ja samuti et tegemist ei ole multigraafiga, st kaks tippu ei saa olla omavahel seotud rohkem kui ühe kaarega. Samuti eeldan, et tipp ei saa olla iseendaga ühendatud. Iga tipu juurde märgin ka selle tipu astme, et eri graafe oleks lihtsam üksteisest eristada. 1) Alustan võimalusest, kui mul pole ühtegi serva ehk ükski graafi tipp pole teisega ühendatud. 2) 1 servaga graafi moodustamiseks on mul samuti 1 võimalus, sest 1 servaga on võimalik ühendada
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
• Kui mingi sõlme üks alampuudest on tühi, siis kirjutakse vastavasse viidaväljasse tühja viida tähis NULL/nil 8.8 Puude kasutamine Kasutatakse arvuti mälus andmestruktuurina: • Avaldised jt keele osad süntaksipuuna. • Erinevad otsimispuud otsimise kiirendamiseks (kahendotsimispuu) • Kahenkuhi kiireks elementid paigutamiseks ja kättesaamiseks • Ka otsustamispuud, koodipuud jne 9. Graaf. Graafiga seotud mõisted. Suunatud ja suunamata graaf. Atsükliline graaf. Kaalutud graaf. Graafi ülesjoonistamine ja realiseerimine arvutis. Graafi algoritmid: topoloogiline sorteerimine, sügavuti otsimine, laiuti otsimine, lühim tee kaalutud graafis e Dijkstra algoritm): algoritmi kirjeldus koos väikese näitega. 9.1 Graaf • Graafi võib kirjeldada kui andmestruktuuri, mis ei pea olema lineaarne.
kaari pole N äiteks olgu hulk tähes tik A= { a,b} j a hulk B kõigi kahetähelis t e s õnade hulk, mida s aab hulga A tähtedes t koos tada B= { aa,ab,ba,bb} . Loe me, et hulga A täht j a hulga B s õna on relats ioonis kui s elles s õnas s is aldub täht. V as tav graaf on : aa a ab ba b bb J uhul kui hulgad A ja B ühtivad, s iis s aame relats iooni es itada suunatud graafiga mi lle tippude hulk on A , ning mi lles on kaar tipus t a tippu b kõigi relats iooni kuuluvate paaride (a,b) korral. Et relats ioon võib s is aldada paare mi lle komponend id on võrds ed, s iis võib antud graaf s is aldada ka s ilmus eid Ü les an n e Antud on hulk A ={ 1,2,3,4,5,6} . B= A D efineeri me relats iooni aRb nii et b j agub a-ga (j aguvus relats ioon). Es itada s ee relats ioon graafi kuj ul. R elats ioone hulkade A= { a1,a2,...am} j a B= { b1,b2,.
kaari pole N äiteks olgu hulk tähes tik A= { a,b} j a hulk B kõigi kahetähelis t e s õnade hulk, mida s aab hulga A tähtedes t koos tada B= { aa,ab,ba,bb} . Loe me, et hulga A täht j a hulga B s õna on relats ioonis kui s elles s õnas s is aldub täht. V as tav graaf on : aa a ab ba b bb J uhul kui hulgad A ja B ühtivad, s iis s aame relats iooni es itada suunatud graafiga mi lle tippude hulk on A , ning mi lles on kaar tipus t a tippu b kõigi relats iooni kuuluvate paaride (a,b) korral. Et relats ioon võib s is aldada paare mi lle komponend id on võrds ed, s iis võib antud graaf s is aldada ka s ilmus eid Ü les an n e Antud on hulk A ={ 1,2,3,4,5,6} . B= A D efineeri me relats iooni aRb nii et b j agub a-ga (j aguvus relats ioon). Es itada s ee relats ioon graafi kuj ul. R elats ioone hulkade A= { a1,a2,...am} j a B= { b1,b2,.
Vastavus - eksamil tudengi poolt saadud hinne. Millistel tingimustel on osaliselt määratud funktsioon; täielikult määratud funktsioon; sürjektsioon; injektsioon; bijektsioon? BINAARSUHTED 4 Meie poolt vaadeldavad binaarsuhteid võib käsitleda kui vastavuse erijuhtu, kus lähte- ja sihthulk langavad kokku (D()=R()=A). Tähistame järgnevas binaarsuhet tähega R AxA. Binaarsuhet on mugav interpreteerida suhte graafiga - s.o. orienteeritud graaf, kus hulga A elemendid vastavad tippudele ja seosed elementide vahel - kaartele. Suhte võime esitada binaarmaatriksina (naabrusmaatriksina). Näide. Hulga A={a,b,c,d,e} elementideks on arvutikomponendid: a-sisendseade, b- aritmeetika- loogikaseade, c-juhtseade, d-mälu, e-väljundseade. Binaarsuhe R seob kahte elementi, kui esimene seade annab teisele infot arvuti töö käigus. a b c d e
Hulk B - hinnete hulk (B={0,1,2,3,4,5}). Vastavus - eksamil tudengi poolt saadud hinne. Millistel tingimustel on osaliselt määratud funktsioon; täielikult määratud funktsioon; sürjektsioon; injektsioon; bijektsioon? BINAARSUHTED Meie poolt vaadeldavad binaarsuhteid võib käsitleda kui vastavuse erijuhtu, kus lähte- ja sihthulk langavad kokku (D()=R()=A). Tähistame järgnevas binaarsuhet tähega R AxA. Binaarsuhet on mugav interpreteerida suhte graafiga - s.o. orienteeritud graaf, kus hulga A elemendid vastavad tippudele ja seosed elementide vahel - kaartele. Suhte võime esitada binaarmaatriksina (naabrusmaatriksina). Näide. Hulga A={a,b,c,d,e} elementideks on arvutikomponendid: a-sisendseade, b- aritmeetika- loogikaseade, c-juhtseade, d-mälu, e-väljundseade. Binaarsuhe R seob kahte elementi, kui esimene seade annab teisele infot arvuti töö käigus. a b c d e
annaabi.ee 
