I am trying to compare 2 algorithms. I thought I may try and write a proof for them. (My math sucks, so hence the question.)
Normally in our math lesson last year we would be given a question like <can't use symbols in here so left them out>.
Prove: (2r + 3) = n (n + 4)
Then I would do the needed 4 stages and get the answer at the end.
Where I am stuck is proving prims and Kruskals - how can I get these algorithms in to a form like the mathmatical one above, so I can proceed to prove?
Note: I am not asking people to answer it for me - just help me get it in to a form where I can have a go myself.
I don't think you can directly. Instead, prove that both generate a MST, then prove that any two MST are equal ( or equivalent, since you can have more than one MST for some graphs ). If both algorithms generate MSTs which are shown to be equivalent, then the algorithms are equivalent.