"alamtipuks" - 1 õppematerjal

ITT0030 Diskreetne matemaatika II - eksamikonspekt

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. Graafi vähima kaaluga aluspuu leidmisel püütakse seega välja selgitada selline optimaalne aluspuu, kus kõikkide allesjäänud servade kaalude summa oleks minimaalne.