"tipuliselt" - 1 õppematerjal

ITT0030 Diskreetne matemaatika II - eksamikonspekt

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. Kruskali algoritm- efektiivseim teadaolev algoritm minimaalse kaaluga aluspuude leidmiseks. Sammud algoritmi kasutamiseks: a). Olgu G kaalutud n-tipuline graaf. b)