图的着色问题

问题来源图的着色问题是由地图的着色问题引申而来的：用m种颜色为地图着色，使得地图上的每一个区域着一种颜色，且相邻区域颜色不同。问题处理：如果把每一个区域收缩为一个顶点，把相邻两个区域用一条边相连接，就可以把一个区域图抽象为一个平面图。例如，图12-1（a）所示的区域图可抽象为12-1（b）所表示的平面图。19世纪50年代，英国学者提出了任何地图都可以4中颜色来着色的4色猜想问题。过了100多年，这个问题才由美国学者在计算机上予以证明，这就是著名的四色定理。例如，在图12-1中，区域用城市名表示，颜色用数字表示，则图中表示了不同区域的不同着色问题。问题来源图的着色•通常所说的着色问题是指下述两类问题：•1．给定无环图G=(V,E)，用m种颜色为图中的每条边着色，要求每条边着一种颜色，并使相邻两条边有着不同的颜色，这个问题称为图的边着色问题。•2．给定无向图G=(V,E)，用m种颜色为图中的每个顶点着色，要求每个顶点着一种颜色，并使相邻两顶点之间有着不同的颜色，这个问题称为图的顶着色问题。顶点着色－基本概念•独立集：对图G=(V,E)，设S是V的一个子集，若中任意两个顶点在G中均不相邻，则称S为G的一个独立集。•最大独立集：如果G不包含适合|S'|＞|S|的独立集S'，则称S为G的最大独立集。•极大覆盖：设K是G的一个独立集，并且对于V-K的任一顶点v，K+v都不是G的独立集，则称K是G的一个极大覆盖。•极小覆盖：极大独立集的补集称为极小覆盖。V的子集K是G的极小覆盖当且仅当：对于每个顶点v或者v属于K，或者v的所有邻点属于K（但两者不同时成立）。顶点着色－基本概念•K可着色：G的一个k顶点着色是指k种颜色1,2,…,k对于G各顶点的一个分配，如果任意两个相邻顶点都分配到不同的颜色，则称着色是正常的。换句话说，无环图G的一个正常k顶点着色是把V分成k个（可能有空的）独立集的一个分类(V1,V2,…,Vk)。当G有一个正常k顶点着色时，就成G是k顶点可着色的。•G的色数X（G）是指G为k可着色的k的最小值，若X（G）=k，则称G是k色的。•事实上，如果我们将同色的顶点列入一个顶点子集，那么求X（G）就转为求满足下列条件的最少子集数k：（1）两两子集中的顶点不同；（2）子集中的两两顶点不相邻。显然有：（i）若G为平凡图，则X（G）=1；（ii）若G为偶图，则X（G）=2（iii）对任意图G，有X（G）≤Δ+1（这里Δ表示为顶点数最大值）顶点着色－求顶色数的算法设计我们由“每个同色顶点集合中的两两顶点不相邻”可以看出，同色顶点集实际上是一个独立集，当我们用第1种颜色上色时，为了尽可能扩大颜色1的顶点个数，逼近所用颜色数最少的目的，事实上就是找出图G的一个极大独立集并给它涂上颜色1。用第2种颜色上色时，同样选择另一个极大独立集涂色，...，当所有顶点涂色完毕，所用的颜色数即为所选的极大独立集的个数。当然，上述颜色数未必就是X（G），而且其和能够含所有顶点的极大独立集个数未必唯一。于是我们必须从一切若干极大独立集的和含所有顶点的子集中，挑选所用极大独立集个数最小者，其个数即为所用的颜色数X（G）。由此可以得算法步骤：Step1：求G图的所有极大独立集；Step2：求出一切若干极大独立集的和含所有顶点的子集；Step3：从中挑选所用极大独立集个数最小值，即为X（G）。求极小覆盖法－布尔代数法求极小覆盖的方法-布尔代数法：对于每个顶点v，选择v或者选择v的所有邻点。首先把“选择顶点v”这个指令记为符号v，然后对给定的指令x和y，指令“x或y”和“x与y”分别记为x+y（逻辑和）和x.y（逻辑积）。•例如，指令“选择a与b，或者选择b与c”记为ab+bc。从形式上看，逻辑和与逻辑积类似与集合的∪和∩，而且关于∪和∩成立的代数法则对于这两个运算也成立。•布尔恒等式aa=a•a+a=a•a+ab=a•如：bcdabbcdbcabcdabdabbcbdbcaabbdababd)bc)(a(ab求极小覆盖法－布尔代数法•例1：求图12-2G的顶色数解：•Step1：求极大独立集先求图G的极小覆盖，化简得故G的极小覆盖为取其补集，得到G的所有极大独立集：•Step2：求出一切若干极大独立集和所有顶点的子集显然我们可以选用4种颜色给每个顶点涂色，或者选用3种颜色分别给3个极大独立集涂色，例如为{b,d,f}中的b、d、f涂颜色1，为{a,f}中的a涂颜色2，为{a,c,g}中的c和g涂颜色3，为{a，e，g}中的e涂颜色4。))()()()()()((bdfgcegfbcdfeacegdbdefcacegbbdabcdfbdefbdefbcacegdeg},,,{},,,,{},,,,,{},,,,{fdcbfedbgedcbgeca},,{},,,{},,{},,,{geagcafafdb求极小覆盖法－布尔代数法Step3：从中挑选所用极大独立集个数最小者，即为X（G）但上述子集的颜色数都不是X（G），正确的应该是X（G）=3，该子集为：给{b,d,f}中的b,d,f涂颜色1，为{a,e,g}中a,e,g涂颜色2为{a,c,g}中的c涂颜色3。由此可见，求色数其需要求极大独立集以及一切若干极大独立集的和含所有顶点的子集，对于大图，因为图计算量过大而成为实际上难以凑效的算法，所以不是一个好算法，一般我们采用贪心法等近似算法来求解。穷举法－WelchPowell着色法•I．将图G中的结点按度数的递减顺序进行排列(这种排列可能不是唯一的，因为有些结点的度数相同)。•II．用第一种颜色对第一结点着色，并按排列顺序对与前面着色结点不邻接的每一结点着上同样的颜色。•III．用第二种颜色对尚未着色的结点重复II，用第三种颜色继续这种做法，直到所有的结点全部着上色为止。穷举法－WelchPowell着色法•给定图G，用WelchPowell法对图G着色A4A2A3A6A532113穷举法－WelchPowell着色法•第一步：将图G中的结点按度数的递减顺序排列：•第二步：用第一种颜色对A5着第一种颜色，并对与A5不邻接的结点A1也着第一种颜色。•第三步：对结点A3及与A3不邻接的结点A4、A8着第二种颜色。•第四步：对结点A7及与A7不邻接的结点A2、A6着第三种颜色。可见，图G是三色的。但图G不可能是二色的，因为A1,A2,A3相互邻接，故必须着三种颜色。所以x(G)=3。86421735,,,,,,,AAAAAAAA回溯法•由于用m种颜色为无向图G=(V,E)着色，其中，V的顶点个数为n，可以用一个n元组C=(c1,c2,…,cn)来描述图的一种可能着色，其中，ci∈{1,2,…,m}，(1≤i≤n)表示赋予顶点i的颜色。例如，5元组(1,2,2,3,1)表示对具有5个顶点的无向图12.3（a）的一种着色，顶点1着颜色1，顶点2着颜色2，顶点3着颜色2，如此等等。•如果在n元组C中，所有相邻顶点都不会着相同颜色，就称此n元组为可行解，否则为无效解。•回溯法求解图着色问题：首先把所有顶点的颜色初始化为0，然后依次为每个顶点着色。如果其中i个顶点已经着色，并且相邻两个顶点的颜色都不一样，就称当前的着色是有效的局部着色；否则，就称为无效的着色。如果由根节点到当前节点路径上的着色，对应于一个有效着色，并且路径的长度小于n，那么相应的着色是有效的局部着色。这时，就从当前节点出发，继续探索它的儿子节点，并把回溯法儿子结点标记为当前结点。在另一方面，如果在相应路径上搜索不到有效的着色，就把当前结点标记为d_结点，并把控制转移去搜索对应于另一种颜色的兄弟结点。如果对所有m个兄弟结点，都搜索不到一种有效的着色，就回溯到它的父亲结点，并把父亲结点标记为d_结点，转移去搜索父亲结点的兄弟结点。这种搜索过程一直进行，直到根结点变为d_结点，或者搜索路径长度等于n，并找到了一个有效的着色为止。例：利用回溯法给下图（a）着色。stepone:把5元组初始化为（0,0,0,0,0），从根结点开始向下搜索，以颜色1为顶点A着色，生成根结点2时，产生(1,0,0,0,0)，是个有效着色。回溯法回溯法steptwo:以颜色1为顶点B着色生成结点3时，产生(1,1,0,0,0)，是个无效着色，结点3为d_结点。Stepthree：以颜色2为顶点B着色生成结点4，产生(1,2,0,0,0)，是个有效着色。Stepfour：分别以颜色1和2为顶点C着色生成结点5和6，产生(1,2,1,0,0)和(1,2,2,0,0)，都是无效着色，因此结点5和6都是d_结点。Stepfive：以颜色3为顶点C着色，产生(1,2,3,0,0)，是个有效着色。重复上述步骤，最后得到有效着色(1,2,3,3,1)。回溯法•设数组color[n]表示顶点的着色情况，回溯法求解m着色问题的算法如下：•图着色回溯法：•1．将数组color[n]初始化为0；•2．k=1;•3．while(k=1)•3.1依次考察每一种颜色，若顶点k的着色与其他顶点的着色不发生冲突，则转步骤3.2；否则，搜索下一个颜色；3.2若顶点已全部着色，则输出数组color[n]，返回；3.3否则，3.3.1若顶点k是一个合法着色，则k=k+1，转步骤3处理下一个顶点；3.3.2否则，重置顶点k的着色情况，k=k-1，转步骤3。回溯法1.voidGraphColor(intn,intc[][],intm)2.//所有数组下标从1开始3.{for(i=1;i=n;i++)//将数组color[n]初始化为04.color[i]=0;k=1;5.while(k=1)6.{color[k]=color[k]+1;7.while(color[k]=m)8.ifOk(k)break;9.elsecolor[k]=color[k]+1;//搜索下一个颜色10.if(color[k]=m&&k==n)//求解完毕，输出解11.{for(i=1;i=n;i++)12.coutcolor[i];13.return;14.}15.elseif(color[k]=m&&kn)16.k=k+1;//处理下一个顶点17.else{color[k]=0;k=k-1;//回溯}18.}19.}回溯法•boolOk(intk)//判断顶点k的着色是否发生冲突•{•for(i=1;ik;i++)•if(c[k][i]==1&&color[i]==color[k])•returnfalse;•returntrue;•}贪心法例如，图12-4(a)所示的图可以只用两种颜色着色，将顶点1、3和4着成一种颜色，将顶点2和顶点5着成另外一种颜色。为简单起见，下面假定k个颜色的集合为{颜色1,颜色2,…,颜色k}。（a）（b）贪心法•贪心策略：选择一种颜色，以任意顶点作为开始顶点，依次考察图中的未被着色的每个顶点，如果一个顶点可以用颜色1着色，换言之，该顶点的邻接点都还未被着色，则用颜色1为该顶点着色，当没有顶点能以这种颜色着色时，选择颜色2和一个未被着色的顶点作为开始顶点，用第二种颜色为尽可能多的顶点着色，如果还有未着色的顶点，则选取颜色3并为尽可能多的顶点着色，依此类推，如图12.4（b）所示。设数组color[n]表示顶点的着色情况，贪心法求解图着色问题的算法如下：图着色贪心法：1．color[1]=1;//顶点1着颜色12．for(i=2;i=n;i++)//其他所有顶点置未着色状态color[i]=0;3．k=0;4．循环直到所有顶点均着色4.1k++;//取下一个颜色4.2for(i=2;i=n;i++)//用颜色k为尽量多的顶点着色4.2.1若顶点i已着色，则转步骤4.2，考虑下一个顶点;4.2.2若图中与顶点i邻接的顶点着色与顶点i着颜色k不冲突，则color[i]=k;5．输出k;蚁群算法设有k只蚂蚁ai(i=1,2,…,k)分别代表k只蚂蚁的初始城市，每一只蚂蚁代表1种颜色，k只蚂蚁分别遍历所有的城市