Posted by: atri | November 9, 2009

Lect 27: Analysis of Kruskal’s and Prim’s algorithm (post #2)

(Guest post by Long Nguyen)

November 6th lecture centered around the optimality of Kruskal’s algorithm and Prim’s Algorithms.  We spend most of the time proving the Lemma (Assume all the edge cost are distinct. Let \emptyset\neq S \subset V, and e=(v,w) is the min cost edges (v\in S and w\in V\setminus S), then e  is in all MST).

We talked about Optimality of Kruskal’s Algorithm.  We assume S is not empty, V\setminus S is not empty, and e is the first crossing edge considered. The Kruskal’s Algorithms produces no cycle by designed and we just need to show that (V,T) is connected. (S is defined to be the set of nodes connected to one end-point of $e$.–Atri)

We talked about Optimality of Prim’s AlgorithmS is defined for us.  By induction, we show that (S,T) is a tree.

We then proceeded to prove the Lemma.

Proof idea: Contradiction and an exchange argument.  For contradiction we assume T (MST) doesn’t have e. (e is min cost crossing edge).

Rest of the proof: Show that e^{\prime}\neq e exist st. T contains e^{\prime}.   T^{\prime}= (T\setminus \{e^{\prime}\}) \cup \{e\} is a spanning tree and \mathrm{cost}(T^{\prime}) < \mathrm{cost}(T) which is a contradiction as T is MST.


Existence of e^{\prime}:


T is connected  implies  a crossing e^{\prime} = (v^{\prime}, w^{\prime}) (edge we’re after.)

  • c_{e^{\prime}} > c_e (e is cheapest crossing edge and edge weights are distinct).
  • \mathrm{cost}(T^{\prime})= \mathrm{Cost}(T)-c_{e^{\prime}}+c_e so \mathrm{cost}(T^{\prime}) < \mathrm{cost}(T).

This neglect fact that w and w^{\prime} is connected in V\setminus S. [To be more precise, we need to show that (V,T^{\prime}) is connected. –Atri] If it is not removing e^{\prime} from and replacing it with e causes  T to become disconnected.  So we must make sure that removing e^{\prime} and adding  e does not disconnect T^{\prime}.  Also if T^{\prime} has a cycle if T does.

We ended lecture there.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: