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 ]

回复此楼

» 猜你喜欢

面上可以超过30页吧？已经有8人回复
体制内长辈说体制内绝大部分一辈子在底层，如同你们一样大部分普通教师忙且收入低已经有18人回复
网上报道青年教师午睡中猝死、熬夜猝死的越来越多，主要哪些原因引起的？已经有5人回复
“人文社科而论，许多学术研究还没有达到民国时期的水平” 已经有6人回复
版面费该交吗已经有13人回复
为什么中国大学工科教授们水了那么多所谓的顶会顶刊，但还是做不出宇树机器人？已经有10人回复
什么是人一生最重要的？已经有4人回复

快了

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

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

zhangwzh

金虫 (正式写手)

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

引用回帖:

6楼: Originally posted by gen007gen at 2012-08-11 04:31:20
楼主能不能把问题用比较严谨的定义一下。我不太清楚你的问题是什么么？
首先，给定一个无向图G=（V,E）,这个无向图怎么会有叶子呢，只有树才有叶子。还有，什么叫把一个图部署到另一个图上，能否用比较严谨的数学公 ...

谢谢关心。数学不好，我大概描述下：
给定一个无向带权树G(V,E),对于每一条相邻的边(u,v)∈E,其权值w(u,v)为1，对不相邻的两个节点m,n, 其w(m,n)为在G上的边全之和（等于跳数）；设有G中全部叶子节点的集合Vs（Vs中结点个数大于V’）；一棵给定结构的树G’(V’,E’)，初始化E’权值均为0；是否存在这样的一个映射f：对于每个V’中的节点u映射到子集Vs节点us，对于树G’中E’，设(u,v)∈E’,则用w(us,vs)表示连接u、v节点的代价，使得树的代价最小？