谁知道二部图的边着色算法?
或者介绍一本有关的书 问题点数：100、回复次数：15Top
1 楼zzwu（未名）回复于 2003-10-02 16:11:59 得分 70
讨论边着色的文章不多见,哈拉里的<图论>中在讨论4色定理时顺便带到了一下.
Top
2 楼zzwu（未名）回复于 2003-10-02 16:15:37 得分 0
不过,二部图的边着色问题似乎应比较方便的,
例如,一眼就可以看出,色数应=最大节点度数.对吧?
Top
3 楼wenjhua（猫痕)(像卡拉一样地活着）回复于 2003-10-03 19:46:22 得分 10
强烈推荐:::::::::::哈拉里的<图论>
着色好象不怎么难啊,,看看图论的书就应该能搞定!!~~~~~~~~~~~~``Top
4 楼tiger0607（瞄一眼）回复于 2003-10-04 13:00:19 得分 0
我想要算法,有介绍算法的书吗?Top
5 楼BlueSky2008（懒惰是程序员的美德）回复于 2003-10-07 00:09:46 得分 10
一般图的边着色是转换成顶点着色来做的。在那七本武功秘籍中第四本：实用算法的分析与程序设计中有介绍的。
Top
6 楼ZhangYv（迎着朝阳,走向地狱）回复于 2003-10-07 10:29:43 得分 10
http://expert.csdn.net/Expert/topic/2059/2059607.xml?temp=.1776087
有个顶点着色的回溯算法，自己找找。Top
7 楼tiger0607（瞄一眼）回复于 2003-10-09 10:18:36 得分 0
边着色好象不能转换为点着色吧？应该是面着色转换为点着色Top
8 楼zzwu（未名）回复于 2003-10-09 12:00:12 得分 0
tiger0607(hanlong):
我想你是对的,面着色可转换为点着色,所以四色定理既适用于面着色,也适用于点着色.
但边着色就明显不行了,如果从一个点引出10根边,就要10种颜色,才能保证相邻边颜色不同.
Top
9 楼zzwu（未名）回复于 2003-10-09 13:00:46 得分 0
我想二部图着色可以这样来进行：先找出二部图中度数最大点P，这样此二部图所需要的颜色也就知道了，然后从P开始，为与它连通的所有边着色．完成后，再考察与P部连通的边．
可用通过以下具体例子来说明算法过程：
--a-----b-----c----
|\ /|\ |
| \ / | \ |
--A--B--C--D--E----
1.找出其中度数最大的点,设其度数为n，再确定此点在二部图的那一方（上方或下方）;
对上图, 找出的就是b点, 度数 n = 3; 部位是上方；
2.记下二部图中与b连接的对方（下方）的n个点,这里是B,C,D
3.为b与这n点的连线分配不同的颜色,c1,c2,...cn;
对上例，就是为 b－B,b-C,b-D 三边分配 c1,c2,c3三种不同的颜色；
4.然后就把工作转到二部图的下方，考察与B,C,D相连的所有点，再考察其中未着色的边，并使用与B已连边颜色不同颜色；
对上例只有一个Ba边，使用的颜色可以是c2,或c3，现设为c2(只要不是c1均可);
5.问题又转到二部图的上方，考察新纪录的点，这里只有a一点
6.考察与a相连的新点，A, 为它着色可以是c１,或c3，现设为c1
以上过程不断重复，总可以把与b连通的边全部着色．
接下来是考察二部图上部与b不连接的其他点（上图就是一个c）,并利用完全相同颜色相同的方法来为与c连通的边进行着色．Top
10 楼BlueSky2008（懒惰是程序员的美德）回复于 2003-10-09 23:00:31 得分 0
边着色转换成顶点着色很简单，图G中每条边对应图G'中一个顶点,如果G中两条边相邻，G'中两个顶点间加一条边。就转化为对G'的顶点着色了。
Top
11 楼zzwu（未名）回复于 2003-10-12 19:50:25 得分 0
BlueSky2008(懒惰是程序员的美德) :
你说的对,我弄错了概念.Top
12 楼zzwu（未名）回复于 2003-10-14 14:22:42 得分 0
其实,平面图的顶点着色法也类似于我上面叙述的边着色,要先按接点度数排序,然后再用类似的方法确定颜色,使所用的色数尽量小.Top
13 楼tiger0607（瞄一眼）回复于 2003-10-18 15:22:49 得分 0
这样转换后还是平面图吗？平面图的着色理论还能用上吗？Top
14 楼zzwu（未名）回复于 2003-10-18 17:04:42 得分 0
不一定是平面图，四色定理只能用于平面图。
Top
15 楼zzwu（未名）回复于 2003-10-18 17:07:11 得分 0
又：上面是着色，没有作转换。
Top
