seatud üks reaalarv (kaal) Kui graafi tipp v kuulub servale e, siis öeldakse, et tipp v ja serv e on intsidentsed Graafi tippe u ja v nimetatakse naabertippudeks, kui nad on servaga ühendatud Olgu G=(V,E) graaf tippude hulgaga V={v 1, ..., vn}. Graafi G naabrusmaatriks on n x n-maatriks A=(a ij), kus aij=1, kui graafis G on tipud vi ja vj servaga ühendatud, 0 vastasel juhul Graafi G'=(V',E'), mis on saadud graafist G=(V,E) teatava hulga tippude ja servade kustutamisel, nimetatakse graafi G alamgraafiks Graafi tipuga v intsidentsete servade arvu nimetatakse tipu v astmeks Tipuastmete teoreem: igas graafis on kõigi tippude astmete summa võrdne servade arvu kahekordsega o Järeldus: igas graafis on paaritu astmega tippe paarisarv Regulaarseks graafiks nimetatakse graafi, mille kõigi tippude astmed on võrdsed Ahelaks nimetatakse graafi tippude järjendit v0, v1, ..
Vastavat graafi nimetatakse siis kaalutud graafiks. i. Kui graafi tipp v kuulub servale e, siis öeldakse, et tipp v ja serv e on intsidentsed. j. Serva uv puhul nimetatakse tippe u ja v naabertippudeks. k. Graafi G naabrusmaatriks on n × n-maatriks A = (aij), kus aij = 1, kui tippude vi ja vj vahel on graafis serv, ning aij = 0, kui nende tippude vahel serv puudub. l. Graafi G' = (V', E'), mis on saadud graafist G = (V, E) teatava hulga tippude ja servade kustutamisel, nimetatakse graafi G alamgraafiks. m. Graafi, mille kõigi tippude astmed on võrdsed, nimetatakse regulaarseks graafiks. 32) a. Graafi tipuga v intsidentsete servade arvu nimetatakse tipu v astmeks ehk valentsiks ja tähistatakse sümboliga d(v). b. Teoreem. Igas graafis on kõigi tippude astmete summa võrdne servade arvu kahekordsega. b.i. Tõestus
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). Tulemuseks saan graafi, millel on (n-1) tippu ja (m-a) serva. Eeldan, et väide kehtib saadud graafi korral, st et graafil (n-1) tipu ja (m-a) servaga on (n-1-m+a) sidususkomponenti. Nüüd lisan selle eemaldatud tipu t graafi tagasi selliselt, et tema aste oleks maksimaalselt a. See aga tähendab, et ta on ühendatud maksimaalselt a graafi G sidususkomponendiga. Seega ühendab lisatud
Hamiltoni kontuur: läbib täpselt 1 kord kõik orienteeritud graafi tipud ja lõpeb oma algustipus Hamiltoni tsükkel: läbib täpselt 1 kord kõik orienteerimata graafi tipud ja lõpeb oma algustipus Isomorfsus: 2 graafi on isomorfsed, kui neil on sama tippude ja kaarte arv ning need on seatavad üks-ühesesse vastavusse nii, et mõlemas graafis seovad vastavad kaared vastavaid tippe. (Isomorfsetes graafides võib olla erinev tippude/kaarte tähistus/paigutus.) 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
o DEF: Naabertipud on need tipud, mis on servaga ühendatud. Graafi naabrusmaatriks 31 o Olgu G = (V, E) graaf tippude hulgaga V = {v1, …, vn}. Graafi G naabrusmaatriks on n x n-maatriks A = (aij), kus o Naabrusmaatriks on sümmeetriline peadiagonaali suhtes ja peadiagonaalil on nullid. o Saab rakendada ka multigraafi ja suunatud graafi esitamiseks. Alamgraaf o DEF: Graafi G’ = (V’, E’), mis on saadud graafist G = (V, E) teatava hulga tippude ja servade kustutamisel, nimetatakse graafi G alamgraafiks. Regulaarne graaf o DEF: Graafi, mille kõigi tippude astmed on võrdsed, nimetatakse regulaarseks graafiks. o Iga täisgraaf Kn ja iga nullgraaf On on regulaarne. 34. Graafi tipu aste. Tipuastmete teoreem, järeldus paaritute astmete kohta. [2] Graafi tipu aste o Tipu v aste ehk valents on tipuga v intsidentsete servade arv. Tähis d(v).
tsüklite & kahe tipu vahelise seose leidmiseks. Laiuti otsimine – sobiv kasutada parima lahenduse/lühima tee otsimisel; tee pikkuseks on kaarte arv kahe tipu vahel; kõiki lahendusvariante uuritakse paralleelselt, mitte ei võrrelda hiljem; võetakse lähtetipp; kõigepealt otsitakse tipud, kuhu saab ühe kaare läbimisel; siis kahe kaare läbimisel jne; kui järgmine tee on pikem, siis seda ei fikseerita. Dijkstra algoritm – suunamata graafist tehakse suunatud graaf; graafis ei tohi olla tsüklit, kus kaarte pikkuste summa tuleks negatiivne; igal sammul tehakse parim otsus; need otsused viivad kogu probleemi lahenemiseni; tööks vajalik tippude tabel, kuhu kirjutatakse iga tipu jaoks tema kaugus lähtetipust ja tipu number, kust antud tippu jõuti; kaalutud graafis liidetakse kaalud ning väljastatakse lühim tee; rakendatakse while-tsüklit. 10. Sorteerimisülesanne. Valiksorteerimine (Selection s
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ö
o VTP(VLAN Trunking protocol) VLAN Iga kommutaatori port võib olla VLAN Trunk port Igal kommutaatori pordil on vaikimisi VLAN, ka siis, kui ta on VLAN trunk port o ilma trunk-infota kaadrid loetakse kuuluvaks vaikimisi VLAN-i Untagged - kaader saadetakse ilma tag-ta Tagged - kaader saadetakse VLAN tag-ga Spanning Tree Protocol (STP) IEEE 802,1D, toesepuu STP teeb tsüklilisest graafist puu - osad servad, mis tekitasid tsükli jäetakse kasutusest välja, varuks. graafi tippudeks on võrguseadmed puu sõlmedeks on kommutaatorid puu lehtedeks on STP protokoll mittekasutavad (lõpp)seadmed Igal STP kommutaatoril on 8-baidine BID (bridge identificator) o 2 baiti - prioriteet o 6 baiti - kommutaatori MAC aadress Kommutaator saadab iga 2 s tagant välja BPDU-kaadreid (bridge protocol data unit)
0 0 0 0 0 0 0 0 7. 2 3 5 7 8 9 10 11 0 0 0 0 0 0 0 0 8. 2 3 5 7 8 9 10 11 0 0 0 0 0 0 0 0 9.6.1 Näide kasutamisest Saab lahendada tööde järgnevuse planeerimise ülesannet. Kui tuleb arvestada sellega, et sorteerimise tulemusi võib olla mitu, seega on võimalikud ka mitu erinevat tööde järjekorda. 9.7 Lühim tee kaalutud graafis e Dijkstra algoritm • Suunamata graafist tehakse suunatud graaf • Graafis ei tohi olla tsüklit, kus kaarte pikkuste summa tuleks negatiivne • Töötab ahne algoritmi põhimõttel, st igal sammul tehakse lokaalselt parim otsus, need otsused viivad kogu probleemi lahenemiseni • Tööks vajalik tippude tabel, kuhu kirjutatakse iga tipu jaoks tema kaugus lähtetipust ja tipu number, kust antud tippu jõuti.
Konfigureerimine võtab aega 30-50 sekundit, mille jooksul on võrk maas. Siis hakatakse joonistama graafi (puud). Lepitakse kokku, et üks sõlmedest on juur – kogu liiklus hakkab temast läbi käima. Näiteks valitakse sild, millel on kõige väiksem MAC-aadress ehk 31 kõige vanem MAC-aadress – kõige aeglasem võrk, sest see paneb alumise piiri võrgu kiirusele. Graafist valitakse kõige optimaalsem (lühem, kiirem) tee. Kui kaks teed on täpselt sama head, valitakse juhuslikult üks neist ning teine blokeeritakse ära. Blokeeritud link on füüsiliselt töökorras, kuid seda lihtsalt ei kasutata. Kui teise pordiga midagi juhtub, siis konfigureeritakse võrk ümber ning kasutatakse teist porti. 26. Võrkude topoloogiad. Siin- ja tähtvõrk, joon, puu, ring, täielikult ühendatud (Metcalfi seadus ja võrguefekt) ja mesh
annaabi.ee 
