"otstipu" - 1 õppematerjal

Diskreetse matemaatika elemendid, eksami konspekt

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 summa parajasti kaks korda suurem kui servade arv c. Järeldus. Igas graafis on paaritu astmega tippe paarisarv. 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