《图的着色问题》PPT课件.ppt

问题来源,图的着色问题是由地图的着色问题引申而来的：用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 如：,求极小覆盖法布尔代数法,例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。,求极小覆盖法布尔代数法,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。 由此可见，求色数其需要求极大独立集以及一切若干极大独立集的和含所有顶点的子集，对于大图，因为图计算量过大而成为实际上难以凑效的算法，所以不是一个好算法，一般我们采用贪心法等近似算法来求解 。,穷举法Welch Powell着色法,I将图G中的结点按度数的递减顺序进行排列(这种排列可能不是唯一的，因为有些结点的度数相同)。 II用第一种颜色对第一结点着色，并按排列顺序对与前面着色结点不邻接的每一结点着上同样的颜色。 III用第二种颜色对尚未着色的结点重复II，用第三种颜色继续这种做法，直到所有的结点全部着上色为止。,穷举法Welch Powell着色法,给定图G，用Welch Powell法对图G着色,A4,A2,A3,A6,A5,3,2,1,1,3,穷举法Welch Powell着色法,第一步：将图G中的结点按度数的递减顺序排列： 第二步：用第一种颜色对A5着第一种颜色，并对与A5不邻接的结点A1也着第一种颜色。 第三步：对结点A3及与A3不邻接的结点A4、A8着第二种颜色。 第四步：对结点A7及与A7不邻接的结点A2、A6着第三种颜色。 可见，图G是三色的。但图G不可能是二色的，因为A1, A2, A3相互邻接，故必须着三种颜色。所以x(G)=3。,回溯法,由于用m种颜色为无向图G=(V,E)着色，其中，V的顶点个数为n，可以用一个n元组C=(c1,c2,cn)来描述图的一种可能着色，其中，ci1, 2, , m，(1in)表示赋予顶点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）着色。 step one:把5元组初始化为（0,0,0,0,0），从根结点开始向下搜索，以颜色1为顶点A着色，生成根结点2时，产生(1,0,0,0,0)，是个有效着色。,回溯法,回溯法,step two:以颜色1为顶点B着色生成结点3时，产生(1,1,0,0,0)，是个无效着色，结点3为d_结点。 Step three：以颜色2为顶点B着色生成结点4，产生(1,2,0,0,0)，是个有效着色。 Step four：分别以颜色1和2为顶点C着色生成结点5和6，产生(1,2,1,0,0)和(1,2,2,0,0)，都是无效着色，因此结点5和6都是d_结点。 Step five：以颜色3为顶点C着色，产生(1,2,3,0,0)，是个有效着色。重复上述步骤，最后得到有效着色(1,2,3,3,1)。,回溯法,设数组colorn表示顶点的着色情况，回溯法求解m着色问题的算法如下： 图着色回溯法： 1将数组colorn初始化为0； 2k=1; 3while (k=1) 3.1 依次考察每一种颜色，若顶点k的着色与其他顶点的着色不发生冲突，则转步骤3.2；否则，搜索下一个颜色；3.2 若顶点已全部着色，则输出数组colorn，返回；3.3 否则， 3.3.1 若顶点k是一个合法着色，则k=k+1，转步骤3处理下一个顶点； 3.3.2 否则，重置顶点k的着色情况，k=k-1，转步骤3。,回溯法,void GraphColor(int n, int c , int m) /所有数组下标从1开始 for (i=1; i=1) colork=colork+1; while (colork=m) if Ok(k) break; else colork=colork+1; /搜索下一个颜色 if (colork=m /回溯 ,回溯法,bool Ok(int k) /判断顶点k的着色是否发生冲突 for (i=1; ik; i+) if (cki= =1 ,贪心法,例如，图12-4(a)所示的图可以只用两种颜色着色，将顶点1、3和4着成一种颜色，将顶点2和顶点5着成另外一种颜色。为简单起见，下面假定k个颜色的集合为颜色1, 颜色2, , 颜色k。 （a） （b）,贪心法,贪心策略：选择一种颜色，以任意顶点作为开始顶点，依次考察图中的未被着色的每个顶点，如果一个顶点可以用颜色1着色，换言之，该顶点的邻接点都还未被着色，则用颜色1为该顶点着色，当没有顶点能以这种颜色着色时，选择颜色2和一个未被着色的顶点作为开始顶点，用第二种颜色为尽可能多的顶点着色，如果还有未着色的顶点，则选取颜色3并为尽可能多的顶点着色，依此类推，如图12.4（b）所示。,设数组colorn表示顶点的着色情况，贪心法求解图着色问题的算法如下： 图着色贪心法： 1color1=1; /顶点1着颜色1 2for (i=2; i=n; i+) /其他所有顶点置未着色状态 colori=0; 3k=0; 4循环直到所有顶点均着色 4.1 k+; /取下一个颜色 4.2 for (i=2; i=n; i+) /用颜色k为尽量多的顶点着色 4.2.1 若顶点i已着色，则转步骤4.2，考虑下一个顶点; 4.2.2 若图中与顶点i邻接的顶点着色与顶点i着颜色k不冲突， 则colori=k; 5输出k;,蚁群算法,设有k只蚂蚁ai(i=1,2,k)分别代表k只蚂蚁的初始城市，每一只蚂蚁代表1种颜色，k只蚂蚁分别遍历所有的城市，ai采用随机赋值的方法，城市用c=1,2,n表示，着色蚂蚁的移动规则如图12-5所示,蚁群算法,ai：表示第i只蚂蚁的起始城市；pmax：蚂蚁i下一步所选城市中最大的概率。 建立邻接矩阵Y为nn的矩阵，表示地区与地区之间的邻接关系，Yic表示城市i与城市c的邻接关系，当城市i与城市c是同一个城市用Yic=0表示，当城市i与城市c不相邻，Yic取一较小值（如Yic=1）；当城市i与城市c相邻Yic取一较大值（如Yic=1）。 ai与c城市的表更新方程：ai到c城市的概率计算公式： 算法： For t1 将k只蚂蚁随机置于k个顶点上 将k只蚂蚁出发点置于当前解集中 For m1 to n/k For i1 to k For c1 to n 按概率pkic选择顶点c 移动蚂蚁i到顶点c 将顶点c置于蚂蚁i的当前解集 检查着色条件 End for End for 检查若未完成的任务 End for tt+1 ic0 End for 输出满意h,图着色问题的应用安排考试问题,设学校共有n门功课需要进行期末考试，因为不少学生不止选修一门课，所以不能把一个同学选修的两门课安排在同一场次进行考试。问学期的期末考试最少需要多少场次才能完成？,问题处理：我们以每门功课为一个顶点，当且仅当两门功课被同一个学生选修时，在响应两个顶点之间连一条边，得到一个图G。我们将n门功课划分成k个子集U1,U2,UK两两子集的功课都不相同。 每个子集Ui（1ik）的顶点两两子集不相邻，即子集内的任意两门功课都不能被一个学生选修。能这种要求划分的子集数K必须最少，即不能划分成k-1个子集。然后我们对每个子集内的顶点涂一种颜色。 同色顶点对应的课程安排在同一场次考试，颜色数即为学期考试所需要的最少场次数。,图着色问题的应用安排考试问题,例：计算机系某学期开设了6门选修课程：数据仓库与数据挖掘，机器学习导论，语音处理与压缩编码，数字媒体动画设计技术，智能信息处理，入侵检测技术，分别用a,b,c,d,e,f表示，我们以每门功课为一个顶点，当且仅当两门功课被同一个学生选修时，在相应两个顶点之间连一条边，学生选修情况如图12-6所示：,图着色问题的应用安排考试问题,分析：利用求极小覆盖的方法求得图的一切极大独立集如下： 显然我们可以选用6种颜色给每个顶点涂色，或者选用5种颜色分别给5个极大独立集涂色，也可以选用4种颜色，例如I1中的a,c涂颜色，I2中的b,d涂颜色2，I3中的f涂颜色3，中的e涂颜色4。 但上述方案的颜色数不是X（G），正确的答案应该是X（G）=3有两种方案： 方案一：给I1中的a和c涂颜色1，I3中的b，f涂颜色2，I4中的d，e涂颜色3，故安排3场考试。 第一场：数据仓库与数据挖掘，智能信息处理 第二场：机器学习，数字媒体动画设计技术 第三场：入侵检测技术，语言处理与压缩编码。 方案二：给I2中的b，d涂颜色1，给I5中的c，e涂颜色2，给I6中的a，f涂颜色3，故安排三场考试： 第一场：机器学习，入侵检测技术 第二场：智能信息处理，语音处理与压缩编码 第三场：数据仓库与数据挖掘，数字媒体动画设计,图着色问题的应用交通管理系统,对于一个多叉路口，设计一个交通信号灯的管理系统：对车辆的可能行驶方向作某种分组，对分组的要求是使任一个组中各个方向行驶的车辆可以同时安全行驶而不发生碰撞。 我们将通行方向作为结点，如果某些通行方向不能同时进行，则在相应的结点间连一条线于是问题就转化为将结点分组，使得相连结点不在同一组里。 例3：如图12-7所示，某交叉路口有A，B，C，D，E,五条街道，请设计一个交通信号灯的管理系统。图12-7 分析：首先考虑可以通行的方向 红：AB，AC，AD，BA，DC，ED 绿：DA，DB 黄：EB，EC，EA 蓝：BC，BD,图着色问题的应用交通管理系统,接下来的通行方向为结点（如图12-8所示），考虑结点分组,图着色问题的应用交通管理系统,贪心算法设计： While有结点未着色 选择一种新颜色； 在未着色的结点中，给尽可能的彼此结点之间没有边的点着色； NEW表示正确的，可以用新颜色着色的结点集合，从V1中找出可用新颜色着色的结点集的程序框架描述为 New= For 每个vV1 do If v与NEW中所有结点间没有边 从V1中去掉v； NEW=NEWv； 对图和集合的操作： 判断一个集合是否为空：isSetEmpty（V1） 置一个集合为空：emptySet（NEW） 从集合中去掉一个元素：removeFromSet（） 向集合里增加一个元素：addToSet（）,图着色问题的应用交通管理系统,算法：检查结点v与结点集合中结点之间在G中是否有边连接 Int colorUp(Graph G) int color=0;V1=G.V; While(!isSetEmpty(V1) / 判断集合V1是否为空 emptySet(NEW); /置集合NEW为空 While(/检查结点v与结点 集合中结点之间在G中是否有边连接 addToSet(NEW,v); /向集合NEW里加元素v removeFromSet(V1,v); /从集合V1中取掉元素v +color; return (color); ,图着色问题的应用交通管理系统,图例中分组情况如下： 绿色：AB，AC，AD，BA，DC，ED 蓝色：BC，BD，EA 红色：DA，DB 黄色：EB，EC,一家公司制造n种化学制品C1,C2,Cn，其中某些制品是互不相容的，如果它们互相接触，则会引起爆炸，作为一种预防措施，公司希望把它的仓库分为间隔，以便把不相容的化学制品储藏在不同的间隔里，试问：这个仓库至少应该分成几个间隔？ 问题处理：构造一个图G，其顶点集是v1,v2,vn两个顶点vi和vj相连当且仅党化学制品Ci和Cj互不相容，则仓库的最小间隔数即为G的顶点数。,图着色问题的应用储藏问题,无环图G的一个k边着色是指k种颜色对于G的各边一个分配。若没有两条边有着色相同的颜色，则称着色是正常的。若G有正常的k边着色，则称k边可着色的。若至少要用k种颜色（即可以正常k边着色而不能k-1边着色）时，则称k为G的边色数，记成。顶点v关联的边中有i色边时，称颜色i色在顶点v出现，在顶点i出现的颜色数目记成C（v）。 通过边顶对换法将图G转换为图G：G图中的边e转换为图G中的一个顶点v；若图G中两条边相邻，则G中对应两个顶点之间连一条边。然后对图G进行顶点着色或求顶色数x(G)，显然：,边着色边顶对换法,例：求图12-9G的边色数 将图12-9G按边顶对换法转换为G(图12-10)，用最少颜色数给G所有顶点上色的一种方案 是 ， 转换成对图G边上色,边着色边顶对换法,问题描述： 给出老师与班级的任课关系，以及教室数的限制，给出一个合理的排课方案。 算法设计： 第一步先求出最佳着色方案，然后再根据教室数的限制求出符合教室数要求的排课方案。 求最佳边着色方案时，先将边转换为点，再采用顶着色的方法来求最佳边着色方法。先设计函数find来求得所有的极大独立集，再通过函数dyeing根据已求得的极大独立集来求最佳着色方法。,边着色问题的应用排课时间表问题,第二步是根据已求得的最佳着色方案和教室数，将着色方案进行调整。 按照教室数和总的课程量来决定同色边集个数，然后再调整各同色边集中的边数。 调整方法为，若两个同色边集Ei,Ej所含边的数目之差大于1，则按照如下方法调整，假设Ei中边数多则此时有两种情况：一是在Ei中能找一条与Ej中各边都不相邻的边加入到Ej中；二是如果没有这样的单边时，则找这样的一条路径，它的起止边都在Ei中，然后将在路径中的Ei,Ej中的边互换。这样形成的新的同色边集Ei和Ej分别替换Ei和Ej。这样一边数差异便缩小了，按照上述方法循环进行直到不存在边数之差大于1的同色边集。,边着色问题的应用排课时间表问题,会场安排问题,问题描述：假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。 这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点，不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数，相应于要找的最小会场数。 算法设计：对于给定的k个待安排的活动，计算使用最少会场的时间表。,数据输入：给出输入数据。第一行有1 个正整数k，表示有k个待安排的活动。接下来的k行中，每行有2个正整数，分别表示k个待安排的活动开始时间和结束时间。时间以0 点开始的分钟计。 结果输出:将计算出的最少会场数输出。 Sample input 51 2312 2825 3527 8036 50 Sample output 3,