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 Algorithm$S$ 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.