35-6 Approximating a maximum spanning tree

Let \(G = (V, E)\) be an undirected graph with distinct edge weights \(w(u, v)\) on each edge \((u, v) \in E\). For each vertex \(v \in V\), let \(\max(v) = \max_{(u, v) \in E} \\{w(u, v)\\}\) be the maximum-weight edge incident on that vertex. Let \(S_G = \\{\max(v): v \in V\\}\) be the set of maximum-weight edges incident on each vertex, and let \(T_G\) be the maximum-weight spanning tree of \(G\), that is, the spanning tree of maximum total weight. For any subset of edges \(E' \subseteq E\), define \(w(E') = \sum_{(u, v) \in E'} w(u, v)\).

a. Give an example of a graph with at least \(4\) vertices for which \(S_G = T_G\).

b. Give an example of a graph with at least \(4\) vertices for which \(S_G \ne T_G\).

c. Prove that \(S_G \subseteq T_G\) for any graph \(G\).

d. Prove that \(w(T_G) \ge w(S_G) / 2\) for any graph \(G\).

e. Give an \(O(V + E)\)-time algorithm to compute a \(2\)-approximation to the maximum spanning tree.

(Omit!)

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用