de hulk jaguneb kaheks alamhulgaks {1, 4, 6} ja {2, 3, 5} nii, et esimese hulga ühestki tipust ei vii kaart teise hulga ühessegi tippu. Järelikult ei ole või- malik esimese hulga tippudest pääseda teise hulga tippudesse, st graaf ei ole tugevalt sidus. Materjal õpikus. Lk 7981 (tugev ja nõrk sidusus). Lk 85, ülesanded 611. Ülesanne 4. Puu tippude astmed on 1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 4 ja x. Leida x. Lahendus. Puul on 12 tippu, tipuastmete summa on 19 + x. Teiselt poolt on tipuastmete summa valemi S = 2(n - 1) põhjal 2 · (12 - 1) = 22. Seega 19 + x = 22, millest x = 3. Materjal õpikus. Lk 64 (teoreem 2). Lk 74, ülesanded 48. Ülesanne 5. Teha kindlaks, kas järgmine positiivsete täisarvude hulgal mää- ratud relatsioon R = {(m, n) : m2 n = mn2 } on ekvivalents. Lahendus. Kontrollime ekvivalentsi omaduste kehtivust.
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, ..., vk (k0), kus iga kaks järjestikust tippu on servaga ühendatud o Tipud v0 ja vk on ahela otstipud o Ülejäänud tipud on ahela sisetipud
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). o Kui d(v) = 1, siis nimetatakse tippu v rippuvaks tipuks. o Kui d(v) = 0, siis nimetatakse tippu v isoleeritud tipuks. o Maksimaalne võimalik tipu aste n-tipulises graafis on n-1. Tipuastmete teoreem o Teoreem. Igas graafis on kõigi tippude astmete summa võrdne servade arvu kahekordsega.
annaabi.ee 
