"otstippu" - 1 õppematerjal

ITT0030 Diskreetne matemaatika II - eksamikonspekt

f). Suvalise kahe tipu vahel leidub alati täpselt 1 lihtahel. Mets- graaf, mis ei sisalda tsükleid (ent ei pruugi olla ka sidus). Lehed- Lehed on puu tipud, mille astmeks on 1 (e. deg(e) = 1). Sild- Sidusa graafi G=(V,E) serva e E nimetatakase sillaks, kui selle serva eemaldamisel muutuks graaf mittesidusaks. Rakenduses esineb sageli ka juurega puid st. tippude hulgast on välja eraldatud üks tipp, juur. Serva seda otstippu, mis asub juurele lähemal, nimetatakse sellisel juhul ülemtipuks, teist otstippu aga alamtipuks. [34]. Graafi vähima kaaluga aluspuud. Graafi aluspuu- sidusa graafi G aluspuu on vähima servade arvuga alamgraaf, mis ühendab kõiki graafi tippe. Cayley teoreemist järeldub, et igal n-tipuliselt täisgraafil on kokku nn-2 erinevat aluspuud. Graafi serva kaal- on servale omistatud teatav positiivne reaalarv.