 |
 |
 |
 |
 |
 |
||
 |
 |
 |
 |
 |
| 5 | 1/1 | 返回列表 |
| 查看: 1230 | 回復: 15 | |||
| 當前只顯示滿足指定條件的回帖，點擊這里查看本話題的所有回帖 | |||
[求助]
萬能的小木蟲，幫幫我吧， 一個類似 terminal Steiner tree problem問題
|
|||
|
有一個無向圖G(v,e),假設(shè)有V有100個頂點。 我現(xiàn)在給定一個n,比如10， 那么，以葉子節(jié)點建立一個子圖，子圖是以V中任意n個葉子連接建立的最小生成樹。 請問建立這個最小生成樹問題是不是一個NP hard問題，有沒有相關(guān)的NP問題，用以證明。 查了些文獻，似乎是一個 terminal Steiner tree problem，但區(qū)別是那個頂點的子集是給定的，而我這個問題只是確定數(shù)量。這個更不一定，是不是可以這樣說，他那個是np, 我這個就更是np了，假如葉子有m個點，就是多了Cm,n倍而已。 [ Last edited by zhangwzh on 2012-7-25 at 10:54 ] |
回復此樓» 猜你喜歡
環(huán)境工程 085701，267求調(diào)劑
已經(jīng)有9人回復
-
085601一志愿西北工業(yè)大學初試346
已經(jīng)有4人回復
-
材料與化工（0856）304求B區(qū)調(diào)劑
已經(jīng)有10人回復
-
本2一志愿C9-333分，材料科學與工程，求調(diào)劑
已經(jīng)有4人回復
-
一志愿中海洋320化學工程與技術(shù)學碩求調(diào)劑
已經(jīng)有6人回復
-
070300化學279求調(diào)劑
已經(jīng)有7人回復
-
085601一志愿中山大學深圳材料工程330求調(diào)劑
已經(jīng)有5人回復
-
293分求調(diào)劑，外語為俄語
已經(jīng)有4人回復
-
0856調(diào)劑
已經(jīng)有3人回復
-
一志愿大連理工大學材料求調(diào)劑
已經(jīng)有6人回復
gen007gen
木蟲 (正式寫手)
- 應(yīng)助: 28 (小學生)
- 金幣: 4954.7
- 散金: 69
- 紅花: 3
- 帖子: 413
- 在線: 262.9小時
- 蟲號: 1161736
- 注冊: 2010-12-03
- 性別: GG
- 專業(yè): 計算機科學的基礎(chǔ)理論
【答案】應(yīng)助回帖
★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★
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的定義。 不過我覺得你要想學這些，要先把圖論好好看看。因為定義了三次，可是第三次的定義也不是很嚴謹。其實你的問題可以描述成：給定一個邊帶權(quán)圖，求解該圖的含有M個葉子節(jié)點且總權(quán)值最小的子樹。 |
9樓2012-08-22 00:16:16
dybo
木蟲 (正式寫手)
- 應(yīng)助: 8 (幼兒園)
- 金幣: 5500.2
- 散金: 134
- 紅花: 43
- 帖子: 625
- 在線: 239.9小時
- 蟲號: 897154
- 注冊: 2009-11-08
- 性別: GG
- 專業(yè): 草地科學
2樓2012-08-10 12:04:38
3樓2012-08-10 12:10:49
4樓2012-08-10 12:11:26
| 最具人氣熱帖推薦 [查看全部] | 作者 | 回/看 | 最后發(fā)表 | |
|---|---|---|---|---|
|
[考研] 材料與化工調(diào)劑一志愿大連海事085600，349 +6 | 吃的不少 2026-03-30 | 6/300 |
|
|---|---|---|---|---|
|
[考研] 材料科學與工程求調(diào)劑 +10 | 深V宿舍吧 2026-03-29 | 10/500 |
|
|
|
[考研] 一志愿華東師范大學有機化學專業(yè)，初試351分，復試被刷求調(diào)劑! +7 | 真名有冰 2026-03-29 | 8/400 |
|
|
|
[考研] 材料科學與工程 317求調(diào)劑 +7 | JKSOIID 2026-03-26 | 7/350 |
|
|
|
[考研] 一志愿哈爾濱工業(yè)大學材料與化工方向336分 +12 | 辰沐5211314 2026-03-26 | 12/600 |
|
|
|
[有機交流] 考研調(diào)劑 +8 | watb 2026-03-26 | 8/400 |
|
|
|
[考研] 332求調(diào)劑 +6 | Lyy930824@ 2026-03-29 | 6/300 |
|
|
|
[考研] 材料與化工272求調(diào)劑 +21 | 阿斯蒂芬2004 2026-03-28 | 21/1050 |
|
|
|
[考研] 375求調(diào)劑 +6 | 雨夏整夜 2026-03-29 | 6/300 |
|
|
|
[考研] 085600，專業(yè)課化工原理，321分求調(diào)劑 +5 | 大饞小子 2026-03-28 | 5/250 |
|
|
|
[考研] 315求調(diào)劑 +4 | akie... 2026-03-28 | 5/250 |
|
|
|
[考研] 壓國家一區(qū)線，求導師收留，有恩必謝！ +7 | 迷人的哈哈 2026-03-28 | 7/350 |
|
|
|
[考研] 復試調(diào)劑 +3 | raojunqi0129 2026-03-28 | 3/150 |
|
|
|
[考研] 299求調(diào)劑 +7 | 嗯嗯嗯嗯2 2026-03-27 | 7/350 |
|
|
|
[考研] 085701環(huán)境工程，267求調(diào)劑 +16 | minht 2026-03-26 | 16/800 |
|
|
|
[考研] 305求調(diào)劑 +5 | 哇盧卡庫 2026-03-26 | 5/250 |
|
|
|
[考研] 292求調(diào)劑 +4 | 求求了收下我吧?/a> 2026-03-26 | 4/200 |
|
|
|
[考研] 321求調(diào)劑 +6 | wasdssaa 2026-03-26 | 6/300 |
|
|
|
[考研] 材料專碩 335 分求調(diào)劑 +4 | 拒絕冷暴力 2026-03-25 | 4/200 |
|
|
|
[考研] 【2026考研調(diào)劑】制藥工程 284分 求相關(guān)專業(yè)調(diào)劑名額 +4 | 袁奐奐 2026-03-25 | 8/400 |
|