Primov algoritmus: Rozdiel medzi revíziami

Nech ''G'' je súvislý ohodnotený graf. V každej iterácii Primovho algoritmu je pridaná hrana, ktorá má jeden vrchol v podgrafe vytvárajúcom kostru a vrchol mimo tohto podgrafu. Pretože ''G'' je súvislý, existuje vždy cesta do každého vrcholu. Výstup ''Y'' Primovho algoritmu je strom, pretože vrchol a hrana, ktoré sú pridané do ''Y'' sú spojené. Nech ''Y1'' je minimálna kostra ''G''. Ak ''Y1=Y'', tak ''Y'' je minimálna kostra. Inak, nech ''e'' je prvá hrana pridaná počas konštrukcie ''Y'', ktorá nie je v ''Y1'', a ''V'' nech je množina vrcholov spojených hranami pridanými pred pridaním ''e''. Potom jeden koncový bod ''e'' je vo ''V'' a druhý nie je. Pretože ''Y1'' je kostra ''G'', existuje cesta v ''Y1'' spájajúca tieto dva koncové vrcholy. Keď prechádzame pozdĺž tejto cesty, musíme naraziť na hranu ''f'' spájajúcu vrchol vo ''V'' s vrcholom, ktorý nie je vo ''V''. Teraz, v iterácii, keď je pridávaná hrana ''e'' do ''Y'', ''f'' by mohla byť pridaná tiež a mohla by byť pridaná namiesto ''e'', ak by jej ohodnotenie bolo menšie ako ''e''. Pretože ''f'' nebola pridaná, ohodnotenie ''f'' nie je menšie ako ohodnotenie ''e''. Nech ''Y2'' je graf získaný z ''Y1'' odstránením ''f'' a pridaním ''e''. Je ľahké ukázať, že ''Y2'' je súvislý, má ten istý počet hrán ako ''Y1'' a celková váha jeho hrán nie je väčšia ako v ''Y1'', preto je to tiež minimálna kostra ''G'' a obsahuje ''e'' a všetky hrany pridané pred ''e'' počas konštrukcie ''V''. Opakovaním vyššie uvedených krokov vieme získať minimálnu kostru grafu ''G'', ktorá je identická s ''Y''. Toto dokazuje, že ''Y'' je minimálna kostra.

 

== Referencie ==

* [[Vojtěch Jarník|V. Jarník]]: ''O jistém problému minimálním'', Práce Moravské Přírodovědecké Společnosti, 6, 1930, pp. 57-63.