[圖論]也不知道算不算圖論的一題..

看板Math作者 (葫蘆吞象)時間10年前 (2013/12/27 15:08), 編輯推噓2(2推 0噓 16→)
留言18則, 8人參與, 4年前最新討論串1/1
可能表達的不是很清楚,修改一下好了 ------------------------------- 假設現在有N個點,每個點分別有一個數字 點和點之間可能有無向邊,現在的問題是要把點分成數個集合 使得每個集合中的點最大數字加起來要最小,且滿足若兩點之間有邊 則那兩點不能在同一集合 請問有啥好的演算法完成這個問題嗎?除了把所有可能列出以外 或者說想解這類問題應該從哪方面下手呢? ------------------------------------------- 另外,greedy 演算法似乎會有問題 如圖為例子:http://ppt.cc/OS0Q 感謝各位!! -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 111.251.167.31
推
12/27 16:10, , 1F
第二行的集合和第三行的群指的是一樣的意思嗎?
12/27 16:10, 1F
→
12/27 17:25, , 2F
不能放在一起的是「隔壁的點」還是「有路徑相連的點
12/27 17:25, 2F
→
12/27 17:26, , 3F
如果是只要有路徑就不能在一起，問題很簡單啊。
12/27 17:26, 3F
→
12/27 17:26, , 4F
每條路線上面最大的放一起，次大的放一起，第三大的
12/27 17:26, 4F
→
12/27 17:27, , 5F
放一起...分完為止
12/27 17:27, 5F
→
12/27 18:09, , 6F
12/27 18:09, 6F
→
12/27 18:10, , 7F
事實上，最後造出的領頭點集是一個complete graph；
12/27 18:10, 7F
→
12/27 18:14, , 8F
從而保證了此問題用greedy algorithm的可行性。
12/27 18:14, 8F
→
12/27 18:57, , 9F
原po說的應該是 k-partite graph
12/27 18:57, 9F
→
12/28 01:34, , 10F
回1F~是一樣的意思
12/28 01:34, 10F
※ 編輯: ddczx 來自: 111.251.167.31 (12/28 01:51)
→
12/28 02:03, , 11F
嗯；的確是會有問題，我有一個地方想錯了；再想想。
12/28 02:03, 11F
→
12/28 09:14, , 12F
回2F 不是有路徑相連的點 是要兩點間本身有邊才算
12/28 09:14, 12F
推
12/28 12:15, , 13F
若全部頂點權重都是1 那此問題化約至求chromatic num
12/28 12:15, 13F
→
12/28 12:16, , 14F
這是一個NP-complete的問題
12/28 12:16, 14F
→
12/28 13:04, , 15F
所以只能用指數算法的時間完成?
12/28 13:04, 15F
→
12/28 13:11, , 16F
喔喔~我想通怎麼化簡過去了!感謝樓上
12/28 13:11, 16F
→
01/02 15:38, 5年前 , 17F
回1F~是一樣的意思 https://noxiv.com
01/02 15:38, 17F
→
07/07 11:45, 4年前 , 18F
如果是只要有路徑就不能 https://moxox.com
07/07 11:45, 18F
‣ 更多 ddczx 的文章
文章代碼(AID): #1IlITKf2 (Math)