Question

Which algorithm can be used to find a Minimal Spanning Tree of any certain graph?
and how can we prove that this algorithm will always find the Minimal Spanning Tree, for all graphs?

Answer 1

minimal or minimum?

Answer 2

if you mean minimum then there are a few. google Kruskal and Primm algarithms and if you need help with either let me know. They are pretty easy and fun!

Answer 3

I can walk you through either proof as well. They are pretty standard in any intro GT book.

Answer 4

Greedy algorithms are usually easy points on a test, so I would learn them both ;)

Answer 5

Yes, Kruskal's and Prim's algorithms find the/a MST,
But why do they always work?, and why do they give the same (or equivalent solutions)?

Answer 6

proof by contradiction

if the smallest edge is not included in the mst, then including the smallest edge would create a multiple edge loop of — it would not be an mst, unless we remove some edges in the loop. if we remove edge that is not the smallest the, the mst would be even smaller, a contradiction

Answer 7

So the mst always includes the smallest edges.