| 查看: 136 | 回复: 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 ] |
回复此楼» 猜你喜欢
Bioresource Technology期刊，第一次返修的时候被退回好几次了
已经有7人回复
-
2025冷门绝学什么时候出结果
已经有4人回复
-
真诚求助：手里的省社科项目结项要求主持人一篇中文核心，有什么渠道能发核心吗
已经有8人回复
-
寻求一种能扛住强氧化性腐蚀性的容器密封件
已经有5人回复
-
论文投稿，期刊推荐
已经有6人回复
-
请问哪里可以有青B申请的本子可以借鉴一下。
已经有4人回复
-
孩子确诊有中度注意力缺陷
已经有14人回复
-
请问下大家为什么这个铃木偶联几乎不反应呢
已经有5人回复
-
请问有评职称，把科研教学业绩算分排序的高校吗
已经有5人回复
-
天津工业大学郑柳春团队欢迎化学化工、高分子化学或有机合成方向的博士生和硕士生加入
已经有4人回复
2楼2008-05-11 09:41:09