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. Tippude astmete summa leidmisel loeme iga tipu juures kokku kõik servad
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, ..., vk (k0), kus iga kaks järjestikust tippu on servaga ühendatud
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). o Kui d(v) = 1, siis nimetatakse tippu v rippuvaks tipuks. o Kui d(v) = 0, siis nimetatakse tippu v isoleeritud tipuks.
annaabi.ee 
