24小时热门版块排行榜

返回列表

当前只显示满足指定条件的回帖，点击这里查看本话题的所有回帖

zhangwzh

金虫 (正式写手)

应助: 3 (幼儿园)
金币: 278.5
散金: 856
红花: 3
帖子: 973
在线: 335.1小时
虫号: 605802
注册: 2008-09-18
性别: GG
专业: 计算机网络

[求助] 万能的小木虫，帮帮我吧，一个类似 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 ]

回复此楼

» 猜你喜欢

2025冷门绝学什么时候出结果已经有4人回复
真诚求助：手里的省社科项目结项要求主持人一篇中文核心，有什么渠道能发核心吗已经有8人回复
寻求一种能扛住强氧化性腐蚀性的容器密封件已经有5人回复
论文投稿，期刊推荐已经有6人回复
请问哪里可以有青B申请的本子可以借鉴一下。已经有4人回复
孩子确诊有中度注意力缺陷已经有14人回复
请问下大家为什么这个铃木偶联几乎不反应呢已经有5人回复
请问有评职称，把科研教学业绩算分排序的高校吗已经有5人回复
天津工业大学郑柳春团队欢迎化学化工、高分子化学或有机合成方向的博士生和硕士生加入已经有4人回复
康复大学泰山学者周祺惠团队招收博士研究生已经有6人回复

快了

1楼2012-07-25 10:23:57

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖

gen007gen

木虫 (正式写手)

应助: 28 (小学生)
金币: 4952.7
散金: 69
红花: 3
帖子: 413
在线: 262.9小时
虫号: 1161736
注册: 2010-12-03
性别: GG
专业: 计算机科学的基础理论

【答案】应助回帖

★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★
zhangwzh: 金币+20, ★★★★★最佳答案, 谢谢啊，有空一定看看图论，就是一直没时间啊！ 2012-08-22 09:04:35

引用回帖:

8楼: Originally posted by zhangwzh at 2012-08-21 15:34:33
给定一个带权连通图G（V1,...VN), 其任意两点间的权重由一个给定的N*N矩阵确定，求G中有M个叶子节点的最小树。（M<N）

这个问题是不是NPC问题，如何证明，谢谢。...

这个问题显然是NP-hard的。因为maxi leaf spanning tree是这个问题的special case, 而maxi leaf spanning tree是NP-hard的。但是是NP-complete的可能行不大。

你可以到google 搜索maxi leaf spanning tree的定义。

不过我觉得你要想学这些，要先把图论好好看看。因为定义了三次，可是第三次的定义也不是很严谨。其实你的问题可以描述成：给定一个边带权图，求解该图的含有M个叶子节点且总权值最小的子树。