Graafid ja matemaatiline loogika eksamimaterjal
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
o Kruskali algoritmiga saadakse - 1 serva ja ülimalt tipuga graaf,
mis ei sisalda tsükleid, järelikult ta on puu ja graafi toespuu
o Olgu Kruskali algoritmiga saadud puu K servad 1, ..., -1. Tõestame,
et selle puu kaal on toespuude seas vähim
o Olgu 1 graafi suvaline toespuu
o Vaatleme järgmist sammu: Olgu esimene Kruskali algoritmis
valitud serv puus , mis ei kuulu puusse 1.
o Kui lisame puule 1, siis tekib seal tsükkel, mis sisaldab serva .
Mingi serv selles tsüklis ei kuulu puusse , sest puus pole
tsükleid. Serva kaal ei saa olla väiksem kui kaal, sest muidu oleks
Kruskali algoritm valinud asemel serva .
annaabi.ee 
