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 Teeks nimetatakse ahelat, kus ükski serv ei kordu Lihtahelaks nimetatakse ahelat, kus ükski tipp ega serv ei kordu Teoreem lihtahelast: kui graafis G leidub ahel tipust u tippu v, siis leidub graafis G ka lihtahel tipust u tippu v Tippude u ja v vaheliseks kauguseks nimetatakse tippude u ja v vahelise lühima lihtahela pikkust Kinniseks ahelaks nimetatakse ahelat, mis algab ja lõpeb samas tipus Tsükliks nimetatakse kinnist ahelat, kus on vähemalt üks serv ja ükski serv ei kordu
c.i. Tõestus. Selleks, et kõigi tippude astmete summa tuleks paarisarv, peab summas esinema paarisarv paaritut liidetavat. 33) a. Ahel graafis G on selline tippude järjend v0, v1, ..., vk, kus iga kaks järjestikust tippu on servaga ühendatud. Tippe v0 ja vk nimetatakse ahela otstippudeks, ahela ülejäänud tipud v1, ..., vk-1 on sisetipud. b. Kui kõik ahela tipud on erinevad, siis nimetatakse ahelat lihtahelaks. c. Teoreem. Kui graafis G leidub ahel tipust u tippu v, siis leidub graafis G ka lihtahel tipust u tippu v. c.i. Tõestus. https://moodle.ut.ee/mod/url/view.php?id=107318 lk 52. d. Tippude u ja v vahelise lühima lihtahela pikkust nimetatakse tippude u ja v kauguseks. 34) a. Ahelat, mis lõpeb samas tipus, kus algab, nimetatakse tsükliks. b. Tsüklit, mis ei läbi ühtegi tippu kaks korda, nimetatakse lihttsükliks. c. Teoreem
Lihtahel. Teoreem lihtahelast. Kaugus. [2] Ahel, otstipud, sisetipud, lihtahel o DEF: Ahelaks nimetatakse graafi tippude järjendit v0, v1, …, vk, kus iga kaks järjestikust tippu on servaga ühendatud. o Tipud v0 ja vk on ahela otstipud, ülejäänud tipud on sisetipud. o Ahela servade arvu k nimetatakse ahela pikkuseks. o Ahel võib tippe ja servi sisaldada ka korduvalt. o Kui ahel ei sisalda korduvaid tippe ega servi, nimetatakse teda lihtahelaks. Teoreem lihtahelast o Teoreem. Kui graafis G leidub ahel tipust u tippu v, siis leidub graafis G ka lihtahel tipust u tippu v. Kaugus o DEF: Tippude u ja v vahelise lühima lihtahela pikkust nimetatakse tippude u ja v kauguseks. 36. Tsükkel. Lihttsükkel. Teoreem lihtahela ja lihttsükli leidumisest. [2] Tsükkel o Tsükliks nimetatakse ahelat, mis algab ja lõpeb samas tipus. o Tsükli servade arvu nimetatakse tsükli pikkuseks.
annaabi.ee 
