| 查看: 1237 | 回复: 15 | ||
[求助]
万能的小木虫，帮帮我吧， 一个类似 terminal Steiner tree problem问题
|
|
有一个无向图G(v,e),假设有V有100个顶点。 我现在给定一个n,比如10， 那么，以叶子节点建立一个子图，子图是以V中任意n个叶子连接建立的最小生成树。 请问建立这个最小生成树问题是不是一个NP hard问题，有没有相关的NP问题，用以证明。 查了些文献，似乎是一个 terminal Steiner tree problem，但区别是那个顶点的子集是给定的，而我这个问题只是确定数量。这个更不一定，是不是可以这样说，他那个是np, 我这个就更是np了，假如叶子有m个点，就是多了Cm,n倍而已。 [ Last edited by zhangwzh on 2012-7-25 at 10:54 ] |
回复此楼» 猜你喜欢
调剂
已经有6人回复
-
一志愿 江南大学 085602 化工专硕 338分求调剂
已经有12人回复
-
材料专硕(0856) 339分求调剂
已经有8人回复
-
377求调剂
已经有5人回复
-
0703调剂，一志愿天津大学319分
已经有6人回复
-
一志愿南昌大学，085600，344分求调剂
已经有5人回复
-
308求调剂
已经有8人回复
-
找调剂
已经有9人回复
-
一志愿郑州大学085600求调剂
已经有12人回复
-
316求调剂
已经有3人回复
dybo
木虫 (正式写手)
- 应助: 8 (幼儿园)
- 金币: 5500.2
- 散金: 134
- 红花: 43
- 帖子: 625
- 在线: 239.9小时
- 虫号: 897154
- 注册: 2009-11-08
- 性别: GG
- 专业: 草地科学
2楼2012-08-10 12:04:38
3楼2012-08-10 12:10:49
4楼2012-08-10 12:11:26
5楼2012-08-10 12:13:11
gen007gen
木虫 (正式写手)
- 应助: 28 (小学生)
- 金币: 4954.7
- 散金: 69
- 红花: 3
- 帖子: 413
- 在线: 262.9小时
- 虫号: 1161736
- 注册: 2010-12-03
- 性别: GG
- 专业: 计算机科学的基础理论
zhangwzh6楼2012-08-11 04:31:20
7楼2012-08-12 15:37:37
8楼2012-08-21 15:34:33
gen007gen
木虫 (正式写手)
- 应助: 28 (小学生)
- 金币: 4954.7
- 散金: 69
- 红花: 3
- 帖子: 413
- 在线: 262.9小时
- 虫号: 1161736
- 注册: 2010-12-03
- 性别: GG
- 专业: 计算机科学的基础理论
【答案】应助回帖
★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★
zhangwzh: 金币+20, ★★★★★最佳答案, 谢谢啊，有空一定看看图论，就是一直没时间啊！ 2012-08-22 09:04:35
zhangwzh: 金币+20, ★★★★★最佳答案, 谢谢啊，有空一定看看图论，就是一直没时间啊！ 2012-08-22 09:04:35
|
这个问题显然是NP-hard的。因为maxi leaf spanning tree是这个问题的special case, 而maxi leaf spanning tree是NP-hard的。但是是NP-complete的可能行不大。 你可以到google 搜索maxi leaf spanning tree的定义。 不过我觉得你要想学这些，要先把图论好好看看。因为定义了三次，可是第三次的定义也不是很严谨。其实你的问题可以描述成：给定一个边带权图，求解该图的含有M个叶子节点且总权值最小的子树。 |
9楼2012-08-22 00:16:16
10楼2012-08-22 09:29:54
