Exercise 1.3

算法设计与分析

STEP I

we sort the weighed edges in ascending order and relabel the weight of the edges by its rank after sort. ( If two edges have the same weight, then they have te same rank )

STEP II

We denote the new weight of the edges $w_i$ as its label above. Obviously,

$$1 \leqslant w_i \leqslant m$$ .
Thus, we could just prove the lemma in the new graph.
Meanwhile, we prove another lemma: We denote that $$V_c(T) = \{ v \in T_c\}$$ , then $$V_c(T)=V_c(T')$$

STEP III

We prove the lemma by mathematical induction.

BASIS STEP:

if $c=1$, obviously the smallest edge of any MST of any graph would be the same, i.e. $$V_1(T)=V_1(T')$$ , and $$M_1(T)=M_1(T')$$ .

RECURSIVE STEP:

Suppose that when $c=k$, $$M_k(T)=M_k(T')$$ and $$V_k(T)=V_k(T')$$ .

When $c=k+1$, there are 2 different conditions:

There is no edge that weighs $k+1$.

So $$M_{k+1}(T)=M_k(T)=M_k(T')=M_{k+1}(T')$$ and $$V_{k+1}(T)=V_k(T)=V_k(T')=V_{k+1}(T')$$

There is one or several edges that weigh $k+1$.

If $$V_{k+1}(T) \neq V_{k+1}(T')$$ , then $$\exists v_0\in V_{k+1}(T), v_0\notin V_{k+1}(T')$$ .

Obviously, the edges that connect $V_k(T)$ and $V_{k+1}(T)$ are weighed $k+1$. so does $T'$.

For $$v_0\in V_{k+1}(T), v_0\notin V_{k+1}(T'), V_k(T)=V_k(T')$$ , from $V_k(T)$, we can simply add another vertex $v_0$ into $V_{k+1}(T')$, which will not from a circle in the MST and is better than choose a later larger weighted edge. Here we find controdiction.

Thus, $$V_{k+1}(T)=V_{k+1}(T')$$ and apperantly $$M_{k+1}(T)=M_{k+1}(T')$$

After all, we can derive that

$$V_c(T)=V_c(T')$$ and $$M_c(T)=M_c(T')$$