| 查看: 137 | 回复: 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人回复
-
到新单位后，换了新的研究方向，没有团队，持续积累2区以上论文，能申请到面上吗
已经有8人回复
-
申请2026年博士
已经有6人回复
-
请问哪里可以有青B申请的本子可以借鉴一下。
已经有5人回复
-
天津工业大学郑柳春团队欢迎化学化工、高分子化学或有机合成方向的博士生和硕士生加入
已经有5人回复
-
2025冷门绝学什么时候出结果
已经有7人回复
-
请问有评职称，把科研教学业绩算分排序的高校吗
已经有6人回复
-
Bioresource Technology期刊，第一次返修的时候被退回好几次了
已经有7人回复
-
请问下大家为什么这个铃木偶联几乎不反应呢
已经有5人回复
-
康复大学泰山学者周祺惠团队招收博士研究生
已经有6人回复
2楼2008-05-11 09:41:09