Graafid ja matemaatiline loogika eksamimaterjal
, kusjuures puu kaal saab ainult väheneda.
o Järelikult ei saa puu 1 kaal olla väiksem puu kaalust
Primi algoritm vähima kaaluga aluspuu leidmiseks:
o Valime graafist suvalise tipu v. Olgu 0 graaf ainsa tipuga v ja
U=V{v}, st ülejäänud tippude hulk
o Iga = 1, ... , - 1 korral
leiame graafist vähima kaaluga serva , mis ühendab
mingit graafi -1 tippu mingi tipuga
Lisame alamgraafile -1 serva ja tema teise otspunkti .
Eemaldame hulgast
Primi algoritmi korrektsus:
o Rakendatagu Primi algoritmi sidusale kaalutud graafile , milles on n
tippu
o Et on sidus, siis igal sammul leidub serv, mis ühendab alamgraafi
-1 mõne veel ühendamata tipuga
o Algoritmi rakendamise tulemus -1 on puu, sest pole tsükleid ja ta
on sidus. -1 sisaldab graafi kõiki tippu, järelikult on toespuu
annaabi.ee 
