作者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