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. Seejuures võtame iga serva arvesse kaks korda: üks kord ühe, teine kord teise otstipu servade hulgas. Seega on tippude astmete
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 o Tipud v0 ja vk on ahela otstipud
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. 32 o Tõestus. Iga serv suurendab oma kummagi otspunkti astet (ja seega ka astmete summat)
annaabi.ee 
