| 查看: 139 | 回复: 1 | |||
| 当前主题已经存档。 | |||
| 当前只显示满足指定条件的回帖，点击这里查看本话题的所有回帖 | |||
[交流]
【求助】谁会证明这些题目，版主，麻烦您将我钱币全部转给解答者（仅限今下午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 ] |
回复此楼» 猜你喜欢
之前让一硕士生水了7个发明专利，现在这7个获批发明专利的维护费可从哪儿支出哈？
已经有7人回复
-
博士申请都是内定的吗？
已经有7人回复
-
读博
已经有5人回复
-
博士读完未来一定会好吗
已经有29人回复
-
投稿精细化工
已经有4人回复
-
高职单位投计算机相关的北核或SCI四区期刊推荐，求支招！
已经有4人回复
-
导师想让我从独立一作变成了共一第一
已经有9人回复
-
心脉受损
已经有5人回复
-
Springer期刊投稿求助
已经有4人回复
-
小论文投稿
已经有3人回复
2楼2008-05-11 09:41:09