1.Prove that a tree (a connected acyclic graph) with n vertices has n - 1 edges by induction.
Let \( n(k) \) \( \Leftrightarrow \) a tree with n vertices has n-1 edges.
1.A tree with 1 vertice called \( v_1 \) has no edge. If it has some edges, then they must from \( v_1 \) to \( v_1 \). This is a contradiction in acycle. So \( n(1) \) is true.
2.Suppose \( n(k) \) is true. ( \( k\geq 1 \) ) Then we prove \( n(k+1) \).
Suppose \( T \) is a tree with \( n+1 \) vertices, and it must has a vertice that is one degree. We remove this vertice and its edge, then we get a tree \( T’ \) with \( n \) vertices which has \( n-1 \) vertices according to \( n(k) \). So \( T \) has \( n \) edges.
We can add a vertice in a tree from \( n(k) \) , so we have a graph with a connected and acyclic tree with \( k-1 \) vertices and one other vertice called \( v_{k+1} \).
Then we add a path from \( v_{k+1} \) to anyone vertice in the tree, so the new tree with \( k \) vertices we get is connected. It is also acyclic, because old tree is acyclic and \( v_{k+1} \) has only one degree.
Now we note the vertice in the tree by \( v_0…v_{k+1} \). However we add a new path from \( v_a \) to \( v_b \)( \( a,b \in { 1\ldots k+1 } \) ), we will get a new way from root to \( v_b \), which isn’t a tree.
So, \( n(k+1) \) is true.
- So, we prove that a tree (a connected acyclic graph) with n vertices has n - 1 edges.
2. Prove the following theorem:
(1) If T is an optimal binary tree with weights \( w_1 \leq w_2 \leq \ldots \leq w_n \), then \( w_1 \) and \( w_2 \) are on the deepest level and they are brothers on some optimal binary tree.
假设有一棵树, \( w_k \) 在最底层 \( (k \neq 1) \) , 记到达 \( w_k \) 的路径长度为 \( l_k \). \( w_1 \) 不在最底层, 记到达 \( w_1 \) 的路径长度为 \( l_1 \).
显然, 我们可以得到 \( w_k \geq w_1, l_k < l_1 \). 记此时这棵树的权值为 \( W_1 \).
交换 \( w_1 \) 和 \( w_k \) , 此时的权值记为 \( W_2 \).
可以得到 \( W_1-W_2 = w_k \cdot l_k + w_1 \cdot l_1 - w_1 \cdot l_k - w_k \cdot l_1 = (w_k - w_1) \cdot (l_k - l_1) \)
显然大于零, 由此可得, 将 \( w_1 \) 放在最底层, 整棵树的权值更小. 同理 \( w_2 \).
对于最优二叉树T, 权值最小, 那么当然有 \( w_1 \) 和 \( w_2 \)在最底层, 且是兄弟节点, 由此证明(1).
(2) If \( T \) is an optimal binary tree with weights \( w_1 \leq w_2 \leq \ldots \leq w_n \), and replace the parent of \( w_1 \) and \( w_1 \) with a leaf with weight \( w_1 + w_2 \), then the resulting tree \( T’ \) is optimal for the weights \( w_1 + w_2 , w_3 , w_4 , \ldots , w_n \)
由题意得: \( w(T) = w(T’) + w_1 + w_2 \)
假设 \( T’ \) 不是最优二叉树, 那么 \( T’’ \) 是最优的.
将 \( T’’ \) 权为 \( w_1 + w_2 \) 的节点生成两个叶子节点 \( w_1 \) 和 \( w_1 \) , 新树为 \( T_k \)
同理也有 \( w(T_k) = w(T’’) + w_1 + w_2 \)
因为 \( T’’ \) 是最优的, 那么 \( W(T’’) \leq W(T’) \)
如果 \( W(T’’) < W(T’) \), 那么 \( W(T_k) < W(T) \), 与 \( T \) 为最优二叉树矛盾, 所以 \( W(T’’) = W(T’) \), T’为最优树.
3.Prove the following lemma:
Let \( G \) be a weighted connected graph, and let T be a minimum spanning tree for \( T \). If \( e \) is an edge of \( G \) that is not in \( T \), then the weight of \( e \) is at least as great as any edge in the cycle created by adding \( e \) to \( T \).
反证法:假设 \( e \) 小于其中某一条边, 记为 \( e_k \). 记原来的权为 \( W(T) \)
那么我们在树中加入 \( e \), 去掉 \( e_k \), 易知, 得到的还是一个生成树, 记它的权为 \( W(T’) \).
根据假设, 显然有 \( W(T’) < W(T) \), 与 \( T \) 为最小生成树矛盾, 所以假设不成立, \( e \) 大于等于此回路中在树中的任意一条边, 证毕.
4.Prove the following theorem:
Let \( G \) be a weighted connected graph, and let \( V_1 \) and \( V_2 \) be a partition of the vertices of \( G \) into two disjoint nonempty sets. Furthermore, let \( e \) be an edge in \( G \) with minimum weight from among those with one endpoint in \( V_1 \) and the other in \( V_2 \). There is a minimum spanning tree T that has \( e \) as one of its edges.
假设 \( e \) 不在此图的最小生成树(权为 \( W(T) \) )中, 将 \( e \) 加入到该树, 得到一个有回路的树, 且回路会经过 \( V_1 \) 和 \( V_2 \).
现在把这个回路拿出来, 去掉另一条连接 \( V_1 \) 和 \( V_2 \)的边, 得到新生成树, 其权记为 \( W(T’) \).
显然有 \( W(T’) \leq W(T) \), 又因为 \( T \) 为最小生成树, 所以有 \( W(T’) = W(T) \), 既 \( T’ \) 也为最小生成树, 所以 \( e \) 在某个最小生成树中, 证毕.