Primov algoritmus: Rozdiel medzi revíziami

Pridaných 198 bajtov ,  pred 11 rokmi
d
 
== Dôkaz korektnosti algoritmu ==
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 YPrimovho''Y'' Primovho algoritmu je strom, pretože vrchol a hrana, ktoré sú pridané do ''Y'' sú spojené. Nech Y1je''Y1'' je minimálna kostra ''G''. Ak ''Y1=Y'', takYjetak ''Y'' je minimálna kostra. Inak, nech eje''e'' je prvá hrana pridaná počas konštrukcie ''Y'', ktorá nie je vY1v ''Y1'', a Vnech''V'' nech je množina vrcholov spojených hranami pridanými pred pridaním ''e''. Potom jeden koncový bod eje''e'' je vo Va''V'' a druhý nie je. Pretože Y1je''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 fspájajúcu''f'' spájajúcu vrchol vo Vs''V'' s vrcholom, ktorý nie je vo ''V''. Teraz, v iterácii, keď je pridávaná hrana ''e'' do ''Y'', fby''f'' by mohla byť pridaná tiež a mohla by byť pridaná namiesto ''e'', ak by jej ohodnotenie bolo menšie ako ''e''. Pretože fnebola''f'' nebola pridaná, ohodnotenie ''f'' nie je menšie ako ohodnotenie ''e''. NechY2jeNech ''Y2'' je graf získaný z ''Y1'' odstránením fa''f'' pridanímea pridaním ''e''. Je ľahké ukázať, že Y2je''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álnatiež kostraGaminimálna kostra ''G'' a obsahuje ''e'' a obsahujeeavšetkyvš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.
 
 
47

úprav