"aluspuuks" - 1 õppematerjal

Graafid ja matemaatiline loogika eksamimaterjal

mittesidusaks o G ei sisalda tsükleid, kuid ükskõik millise serva lisamisel tekib tsükkel Puu tingimus lihtahelate kaudu: Graaf G on puu parajasti siis, kui tema iga kahte erinevat tippu ühendab täpselt üks lihtahel Algoritmi F korrektsuse teoreem: [Sisend rahuldab eeltingimusi () Algoritm F lõpetab töö ja tulemus = () rahuldab järeltingimust (, )] Sidusa graafi G toespuuks e. Aluspuuks nimetatakse G sellist alamgraafi, mis on puu ja sisaldab G kõiki tippe Kruskali algoritm vähima kaaluga aluspuu leidmiseks: o Valime graafist G vähima kaaluga serva k1 o Iga i=2, ..., n-1 korral valime graafist G sellise vähima kaaluga serva ki, mis erineb eelmistest ja ei moodusta nendega koos tsüklit Kruskali algoritmi korrektsus: o Algoritm töötab - 1 sammu, sest igal sammul leidub uus tingimusi rahuldav serv