Ezt hogy lehetne bizonyítani, mitől igaz?

Tegyük fel, hogy van egy összefüggő G gráfunk, aminek minden élére egy nem negatív valós szám van írva (ezeket a számokat az élek költségének is szokták hívni)

Induljunk ki n darab izolált pontból (0 fokú csúcsból) és élek egyenkénti behúzásával építsük meg a fent említett összefüggő G gráfot, úgy hogy azokat az éleket húzzuk be mindig elsőnek, amelyeknek a költsége a legkisebb. Tehát ha pl. 3 különböző költség fordul elő (mondjuk 4,8,9), akkor először a 4 költségű éleket húzzuk be, majd a 8 költségűeket, végül a 9 költségűeket.

2 féle dolog történhet ha behúzunk egy élt:

1.féle: olyan él, aminek behúzása csökkenti a komponensek számát, de nem hoz létre kört

2.féle: olyan él, aminek behúzása kört hoz létre, de a komponensek számát nem változtatja

Az olyan élekből amik nem hoznak létre kört, de csökkentik a komponensek számát, olyanból n-1 darabot kell behúznunk ahhoz hogy összefüggő gráfot kapjunk. Ugye ezek az élek kört sem hoztak létre, így ezek az élek egy körmentes n-1 élű gráfot alkotnak, ami az eredeti G gráfnak egy részgráfja. Ha egy gráfnak n-1 éle van és körmentes, akkor az a gráf egy fa. Vagyis ezek az élek a G gráf egy F feszítőfáját alkotják.

Állítás:

Ez az F feszítőfa a G gráf minimális költségű feszítőfája. (azaz olyan feszítőfája amelyre igaz az, hogy az élek összköltsége az minimális, a lehető legkisebb és nincs másik olyan feszítőfája a gráfnak aminek kisebb lenne az összköltsége)

Ezt kellene bizonyítani, hogy ez az F feszítőfa az miért lesz minimális költségű.

Ezután derül majd ki, hogy ez igazából a Kruskál algoritmus, viszont a bizonyítás az nem megy, hogy miért minimális költégű az F feszítőfa.

Tudnátok ebben segíteni?