[交流] 【求助】谁会证明这些题目，版主，麻烦您将我钱币全部转给解答者（仅限今下午6点前）

这是“近似算法”的开卷考试题，哪个大虾能够证明的。回帖告知，你的大恩大德，我在此提前拜谢了。 1. Show that the rank function r(• in any matroid (E, C) has the following four properties. (1)        r(ø = 0; (2)        r(• is monotone increasing; (3)        r(• is submodular; (4)        for any x E, r({x}) = 1. 2. Suppose for any set of terminals, there exists a minimum spanning tree with vertex degree at most d. Then there exists a Steinerized spanning tree with (d -1) opt Steiner points where opt is the number of Steiner points in an optimal solution for the problem of Steiner Tree with the Minimum Number of Steiner Points. 3. Let I be a maximal independent set and C a minimum connected dominating set in a unit disk graph. Show that | C |   4 | I | + 1. 4. Suppose G is a connected graph with edge weight. Let Q1, Q2 ,…, Qk form a base of cycles in G and ei the longest edge in Qi. Show that the minimum spanning tree of G has length at least length(G) -  . 5. Given a rectangle with some point-holes inside. Design a 2-approximation for minimum length rectangular partition for this rectangle. [ Last edited by laizuliang on 2008-5-24 at 10:10 ]

回复此楼