How to prove that the algorithm solution is optimal?

Asked

Viewed 246 times

6

I need to argue that the solution found after running Prim’s Greedy Algorithm is great. But I don’t know how, someone could help?

algorithm

1 answer

2

Prim’s algorithm serves to find the minimum generating tree of a graph, i.e., a tree with the smallest possible weight of its edges. Source: Wikipedia

It starts with any arbitrary node of the graph and puts it in the tree A. At each next step it inserts the lower-weight edge that has exactly one vertex within the tree A and another outside of A, repeating until all nodes are added.

The easiest way to prove it is by contradiction. But for that you have to use the cycle ownership: "For any cycle C of the graph, if the weight of an edge [and] of the cycle is greater than all other edges of the cycle, then [and] does not belong to the minimum generating tree".

  1. Assume that edge [e] belongs to the minimum generating tree T;
  2. Show that there is another T' generating tree with lower cost that you don’t use [and];
  3. Conclude that edge [and] cannot belong to the minimum generating tree T (contradiction).

Another way to prove it is by induction. The hypothesis is that at each iteration of the algorithm, the tree A is a subgraph of the minimum generating tree T.

  1. This is trivial in the first step, because the A tree has only one node and no edge, and obviously this node needs to be in T.
  2. Now suppose that at some step we have A (T subgraph) and Prim’s algorithm says to include the edge [and]. We need to prove that A U [and] is also a subtree of some T. If [and] belongs to T then this is true, for by induction A is a subtree of T and [and] belongs to T, so A U [and] is a subtree of T.
  3. Now suppose that [and] does not belong to T. Consider what happens when we add [and] to T. This creates a cycle. Since [and] has a vertex in A and a vertex outside of A (because the algorithm added), there has to be an edge [and'] in this cycle that has exactly one vertex in A. The algorithm could have added [and'], but decided to insert [and], which means that the weight(e) <= weight (e'). So if we add [and] the T tree and remove [and'] we end up with a new T tree whose weight is <= the weight of T and which contains [and]. This maintains the induction, and proves the theorem.

Browser other questions tagged algorithm

You are not signed in. Login or sign up in order to post.