作者seanwu (Blindest)
看板Prob_Solve
標題[問題] 二分圖的邊著色
時間Mon Nov 26 12:43:18 2007
一個二分圖，把每一條邊塗上顏色
任兩條相鄰的邊不能同色，最少要幾種顏色
這個... 有什麼比較好的算法嗎?
又如果是平面圖呢?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 203.68.21.139
1F：推 march20:那也說說你目前用什麼演算法吧 XD 11/27 06:43
2F：推 seanwu:嗯..色數==最大度數d，所以先把所有點的度數利用加邊補到d 11/27 15:27
3F：→ seanwu:然後再做d次匹配，每次的匹配結果就對應一種顏色 11/27 15:28
4F：→ seanwu:再把先前加上的邊拿掉，不影響結果 11/27 15:29
5F：推 march20:口也, 我笨了, 原來是在說 bipartie 11/28 14:48
6F：推 march20:就兩色啊 @@ 11/28 14:48
7F：推 march20:啊, 真的笨了, 是說邊塗色不是點塗色 XD 11/28 14:49
8F：推 march20:感覺上好像是 max-flow 問題 11/28 14:51
9F：推 seanwu:嗯我現在最差得做N次匹配...變成O(N^4)了.. 11/28 14:59
10F：→ seanwu:其實一般來說是夠用的, 另外比較知道的是平面圖的情況 11/28 15:00
11F：推 spen37:為什麼我覺得答案直接是最大相鄰邊數?承認我沒學過圖論orz 11/30 17:29
12F：→ seanwu:樓上，二分圖來說沒錯啊XD，是要找出著色法(嗯我敘述不清.. 11/30 22:50
13F：→ a127a127:問一下 為甚麼要補邊= = 不補不是也一樣= =? 12/02 00:12
14F：→ seanwu:我不補邊就壞了...實際原因我也不知道...XD 12/03 20:45