图的着色问题课件.ppt

1、问题来源图的着色问题是由地图的着色问题引申而来的：用图的着色问题是由地图的着色问题引申而来的：用m m种颜色为地图着色，使得地图上的每一个区域种颜色为地图着色，使得地图上的每一个区域着一种颜色，且相邻区域颜色不同。着一种颜色，且相邻区域颜色不同。问题处理：如果把每一个区域收缩为一个顶点，把问题处理：如果把每一个区域收缩为一个顶点，把相邻两个区域用一条边相连接，就可以把一个区相邻两个区域用一条边相连接，就可以把一个区域图抽象为一个平面图。域图抽象为一个平面图。例如，图例如，图12-112-1（a a）所示的区域图可抽象为）所示的区域图可抽象为12-112-1（b b）所表示的平面图。所表示的平面

2、图。1919世纪世纪5050年代，英国学者提出年代，英国学者提出了任何地图都可以了任何地图都可以4 4中颜色来着色的中颜色来着色的4 4色猜想问题。色猜想问题。过了过了100100多年，这个问题才由美国学者在计算机多年，这个问题才由美国学者在计算机上予以证明，这就是著名的四色定理。例如，在上予以证明，这就是著名的四色定理。例如，在图图12-112-1中，区域用城市名表示，颜色用数字表示，中，区域用城市名表示，颜色用数字表示，则图中表示了不同区域的不同着色问题则图中表示了不同区域的不同着色问题 。1PPT课件问题来源2PPT课件图的着色 通常所说的着色问题是指下述两类问题：通常所说的着色问题是指

3、下述两类问题：1 1给定无环图给定无环图G G=(=(V V,E E)，用，用m m种颜色为图中种颜色为图中的每条边着色，要求每条边着一种颜色，并的每条边着色，要求每条边着一种颜色，并使相邻两条边有着不同的颜色，这个问题称使相邻两条边有着不同的颜色，这个问题称为图的边着色问题。为图的边着色问题。2 2给定无向图给定无向图G G=(=(V V,E E)，用，用m m种颜色为图中种颜色为图中的每个顶点着色，要求每个顶点着一种颜色，的每个顶点着色，要求每个顶点着一种颜色，并使相邻两顶点之间有着不同的颜色，这个并使相邻两顶点之间有着不同的颜色，这个问题称为图的顶着色问题。问题称为图的顶着色问题。3PP

4、T课件顶点着色基本概念 独立集独立集：对图：对图G=(V,E)，设，设S是是V的一个子集，若的一个子集，若中任意两个顶点在中任意两个顶点在G中均不相邻，则称中均不相邻，则称S为为G的一的一个独立集。个独立集。最大独立集最大独立集：如果：如果G不包含适合不包含适合|S|S|的独立的独立集集S，则称，则称S为为G的最大独立集。的最大独立集。极大覆盖极大覆盖：设：设K是是G的一个独立集，并且对于的一个独立集，并且对于V-K的任一顶点的任一顶点v，K+v都不是都不是G的独立集，则称的独立集，则称K是是G的一个极大覆盖。的一个极大覆盖。极小覆盖极小覆盖：极大独立集的补集称为极小覆盖。：极大独立集的补集称

5、为极小覆盖。V的子集的子集K是是G的极小覆盖当且仅当：对于每个顶的极小覆盖当且仅当：对于每个顶点点v或者或者v属于属于K，或者，或者v的所有邻点属于的所有邻点属于K（但两（但两者不同时成立）者不同时成立）。4PPT课件顶点着色基本概念K K可着色可着色：G G的一个的一个k k顶点着色是指顶点着色是指k k种颜色种颜色1,2,1,2,k,k对于对于G G各顶点的各顶点的一个分配，如果任意两个相邻顶点都分配到不同的颜色，则称着一个分配，如果任意两个相邻顶点都分配到不同的颜色，则称着色是正常的。换句话说，无环图色是正常的。换句话说，无环图G G的一个正常的一个正常k k顶点着色是把顶点着色是把V

6、V分成分成k k个（可能有空的）独立集的一个分类个（可能有空的）独立集的一个分类(V V1,1,V V2,2,VkVk)。当。当G G有一个有一个正常正常k k顶点着色时，就成顶点着色时，就成G G是是k k顶点可着色的。顶点可着色的。G G的色数的色数X X（G G）是指）是指G G为为k k可着色的可着色的k k的最小值，若的最小值，若X X（G G）=k=k，则称，则称G G是是k k色的。色的。事实上，如果我们将同色的顶点列入一个顶点子集，那么求事实上，如果我们将同色的顶点列入一个顶点子集，那么求X X（G G）就转为求满足下列条件的最少子集数就转为求满足下列条件的最少子集数k k：（

7、1 1）两两子集中的顶点不同；）两两子集中的顶点不同；（2 2）子集中的两两顶点不相邻。）子集中的两两顶点不相邻。显然有：显然有：（i i）若）若G G为平凡图，则为平凡图，则X X（G G）=1=1；（iiii）若）若G G为偶图，则为偶图，则X X（G G）=2=2 （iiiiii）对任意图）对任意图G G，有，有X X（G G）+1+1（这里（这里表示为顶点表示为顶点数最大值）数最大值）5PPT课件顶点着色顶点着色求顶色数的算法设计求顶色数的算法设计我们由我们由“每个同色顶点集合中的两两顶点不相邻每个同色顶点集合中的两两顶点不相邻”可以看出，同色顶可以看出，同色顶点集实际上是一个独立集，

8、当我们用第点集实际上是一个独立集，当我们用第1 1种颜色上色时，为了尽可种颜色上色时，为了尽可能扩大颜色能扩大颜色1 1的顶点个数，逼近所用颜色数最少的目的，事实上就的顶点个数，逼近所用颜色数最少的目的，事实上就是找出图是找出图G G的一个极大独立集并给它涂上颜色的一个极大独立集并给它涂上颜色1 1。用第。用第2 2种颜色上色种颜色上色时，同样选择另一个极大独立集涂色，时，同样选择另一个极大独立集涂色，.，当所有顶点涂色完毕，当所有顶点涂色完毕，所用的颜色数即为所选的极大独立集的个数。所用的颜色数即为所选的极大独立集的个数。当然，上述颜色数未必就是当然，上述颜色数未必就是X X（G G），而且

9、其和能够含所有顶点的极大），而且其和能够含所有顶点的极大独立集个数未必唯一。于是我们必须从一切若干极大独立集的和独立集个数未必唯一。于是我们必须从一切若干极大独立集的和含所有顶点的子集中，挑选所用极大独立集个数最小者，其个数含所有顶点的子集中，挑选所用极大独立集个数最小者，其个数即为所用的颜色数即为所用的颜色数X X（G G）。）。由此可以得算法步骤：由此可以得算法步骤：Step1Step1：求：求G G图的所有极大独立集；图的所有极大独立集；Step2Step2：求出一切若干极大独立集的和含所有顶点的子集；：求出一切若干极大独立集的和含所有顶点的子集；Step3Step3：从中挑选所用极大独

10、立集个数最小值，即为：从中挑选所用极大独立集个数最小值，即为X X（G G）。）。6PPT课件求极小覆盖法布尔代数法求极小覆盖法布尔代数法求极小覆盖的方法求极小覆盖的方法-布尔代数法布尔代数法：对于每个顶点对于每个顶点v，选择，选择v或者选择或者选择v的所有邻的所有邻点。首先把点。首先把“选择顶点选择顶点v”这个指令记为符号这个指令记为符号v，然后对给定的指令然后对给定的指令x和和y，指令，指令“x或或y”和和“x与与y”分别记为分别记为x+y（逻辑和）和（逻辑和）和x.y（逻辑积）。（逻辑积）。例如，指令例如，指令“选择选择a与与b，或者选择，或者选择b与与c”记为记为ab+bc。从形式上看

11、，逻辑和与逻辑积类似与集。从形式上看，逻辑和与逻辑积类似与集合的合的和和，而且关于，而且关于和和成立的代数法则对成立的代数法则对于这两个运算也成立。于这两个运算也成立。布尔恒等式布尔恒等式 aa=a a+a=a a+ab=a 如：如：bcdab bcdbcabcdabdab bcbdbcaabbdababd)bc)(a(ab7PPT课件求极小覆盖法布尔代数法求极小覆盖法布尔代数法例例1 1：求图：求图12-2G12-2G的顶色数的顶色数 解：解：Step1Step1：求极大独立集：求极大独立集 先求图先求图G G的极小覆盖，的极小覆盖，化简得化简得故故G G的极小覆盖为的极小覆盖为取其补集，得

12、到取其补集，得到G G的所有的所有 极大独立集：极大独立集：Step2Step2：求出一切若干极大独立集和所有顶点的子集：求出一切若干极大独立集和所有顶点的子集 显然我们可以选用显然我们可以选用4 4种颜色给每个顶点涂色，或者选种颜色给每个顶点涂色，或者选用用3 3种颜色分别给种颜色分别给3 3个极大独立集涂色，例如为个极大独立集涂色，例如为b,d,fb,d,f 中中的的b b、d d、f f涂颜色涂颜色1 1，为，为a,fa,f 中的中的a a涂颜色涂颜色2 2，为，为a,c,ga,c,g 中中的的c c和和g g涂颜色涂颜色3 3，为，为aa，e e，gg中的中的e e涂颜色涂颜色4 4。

13、)()()()()()(bdfgcegfbcdfeacegdbdefcacegbbdabcdfbdefbdefbcacegdeg,fdcbfedbgedcbgeca,geagcafafdb8PPT课件求极小覆盖法布尔代数法求极小覆盖法布尔代数法Step3Step3：从中挑选所用极大独立集个数最小者，：从中挑选所用极大独立集个数最小者，即为即为X X（G G）但上述子集的颜色数都不是但上述子集的颜色数都不是X X（G G），正确的应），正确的应该是该是X X（G G）=3=3，该子集为：给，该子集为：给b,d,fb,d,f 中的中的b,d,fb,d,f涂颜色涂颜色1 1，为，为a,e,ga,e,

14、g 中中a,e,ga,e,g涂颜色涂颜色2 2为为a,c,ga,c,g 中的中的c c涂颜色涂颜色3 3。由此可见，求色数其需要求极大独立集以由此可见，求色数其需要求极大独立集以及一切若干极大独立集的和含所有顶点的子及一切若干极大独立集的和含所有顶点的子集，对于大图，因为图计算量过大而成为实集，对于大图，因为图计算量过大而成为实际上难以凑效的算法，所以不是一个好算法，际上难以凑效的算法，所以不是一个好算法，一般我们采用贪心法等近似算法来求解一般我们采用贪心法等近似算法来求解 。9PPT课件穷举法Welch Powell着色法 I I将图将图G G中的结点按度数的递减顺序进行排列中的结点按度数的

15、递减顺序进行排列(这种排列可能不是唯一的，因为有些结点的度这种排列可能不是唯一的，因为有些结点的度数相同数相同)。IIII用第一种颜色对第一结点着色，并按排列顺用第一种颜色对第一结点着色，并按排列顺序对与前面着色结点不邻接的每一结点着上同样序对与前面着色结点不邻接的每一结点着上同样的颜色。的颜色。IIIIII用第二种颜色对尚未着色的结点重复用第二种颜色对尚未着色的结点重复IIII，用第三种颜色继续这种做法，直到所有的结点全用第三种颜色继续这种做法，直到所有的结点全部着上色为止。部着上色为止。10PPT课件穷举法Welch Powell着色法 给定图给定图G，用，用Welch Powell法对图

16、法对图G着着色色A4A2A3A6A53211311PPT课件穷举法Welch Powell着色法 第一步：将图第一步：将图G G中的结点按度数的递减顺序排中的结点按度数的递减顺序排列：列：第二步：用第一种颜色对第二步：用第一种颜色对A A5 5着第一种颜色，着第一种颜色，并对与并对与A A5 5不邻接的结点不邻接的结点A A1 1也着第一种颜色。也着第一种颜色。第三步：对结点第三步：对结点A A3 3及与及与A A3 3不邻接的结点不邻接的结点A A4 4、A A8 8着第二种颜色。着第二种颜色。第四步：对结点第四步：对结点A A7 7及与及与A A7 7不邻接的结点不邻接的结点A A2 2、

17、A A6 6着第三种颜色。着第三种颜色。可见，图可见，图G G是三色的。但图是三色的。但图G G不可能是二色不可能是二色的，因为的，因为A A1,1,A A2,2,A A3 3相互邻接，故必须着三相互邻接，故必须着三种颜色。所以种颜色。所以x x(G G)=3)=3。86421735,AAAAAAAA12PPT课件回溯法 由于用由于用m m种颜色为无向图种颜色为无向图G G=(=(V V,E E)着色，其中，着色，其中，V V的顶点个的顶点个数为数为n n，可以用一个，可以用一个n n元组元组C C=(c(c1,1,c c2,2,c cn n)来描述图的一来描述图的一种可能着色，其中，种可能着

18、色，其中，cici1,2,1,2,m m，(1(1i in n)表示表示赋予顶点赋予顶点i i的颜色。的颜色。例如，例如，5 5元组元组(1,2,2,3,1)(1,2,2,3,1)表示对具有表示对具有5 5个顶点的无个顶点的无向图向图12.312.3（a a）的一种着色，顶点）的一种着色，顶点1 1着颜色着颜色1 1，顶点，顶点2 2着颜色着颜色2 2，顶点，顶点3 3着颜色着颜色2 2，如此等等。，如此等等。如果在如果在n n元组元组C C中，所有相邻顶点都不会着相同颜色，就称中，所有相邻顶点都不会着相同颜色，就称此此n n元组为可行解，否则为无效解。元组为可行解，否则为无效解。回溯法求解图

19、着色问题：首先把所有顶点的颜色初始化为回溯法求解图着色问题：首先把所有顶点的颜色初始化为0 0，然后依次为每个顶点着色。如果其中，然后依次为每个顶点着色。如果其中i i个顶点已经着色，个顶点已经着色，并且相邻两个顶点的颜色都不一样，就称当前的着色是有并且相邻两个顶点的颜色都不一样，就称当前的着色是有效的局部着色；否则，就称为无效的着色。如果由根节点效的局部着色；否则，就称为无效的着色。如果由根节点到当前节点路径上的着色，对应于一个有效着色，并且路到当前节点路径上的着色，对应于一个有效着色，并且路径的长度小于径的长度小于n n，那么相应的着色是有效的局部着色。这，那么相应的着色是有效的局部着色。

20、这时，就从当前节点出发，继续探索它的儿子节点，并把时，就从当前节点出发，继续探索它的儿子节点，并把13PPT课件回溯法 儿子结点标记为当前结点。在另一方面，儿子结点标记为当前结点。在另一方面，如果在相应路径上搜索不到有效的着色，就把当如果在相应路径上搜索不到有效的着色，就把当前结点标记为前结点标记为d_d_结点，并把控制转移去搜索对应结点，并把控制转移去搜索对应于另一种颜色的兄弟结点。如果对所有于另一种颜色的兄弟结点。如果对所有m m个兄弟个兄弟结点，都搜索不到一种有效的着色，就回溯到它结点，都搜索不到一种有效的着色，就回溯到它的父亲结点，并把父亲结点标记为的父亲结点，并把父亲结点标记为d_d

21、_结点，转移结点，转移去搜索父亲结点的兄弟结点。这种搜索过程一直去搜索父亲结点的兄弟结点。这种搜索过程一直进行，直到根结点变为进行，直到根结点变为d_d_结点，或者搜索路径长结点，或者搜索路径长度等于度等于n n，并找到了一个有效的着色为止。，并找到了一个有效的着色为止。例：利用回溯法给下图（例：利用回溯法给下图（a a）着色。）着色。step one:step one:把把5 5元组初始化为（元组初始化为（0,0,0,0,00,0,0,0,0），从），从根结点开始向下搜索，以颜色根结点开始向下搜索，以颜色1 1为顶点为顶点A A着色，生着色，生成根结点成根结点2 2时，产生时，产生(1,0,

22、0,0,0)(1,0,0,0,0)，是个有效着色。，是个有效着色。14PPT课件回溯法 15PPT课件回溯法 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)，都是无效着，都是

23、无效着色，因此结点色，因此结点5和和6都是都是d_结点。结点。Step five：以颜色：以颜色3为顶点为顶点C着色，产生着色，产生(1,2,3,0,0)，是个有效着色。重复上述步骤，最后得到有效着是个有效着色。重复上述步骤，最后得到有效着色色(1,2,3,3,1)。16PPT课件回溯法 设数组设数组colorn表示顶点的着色情况，回溯法求解表示顶点的着色情况，回溯法求解m着色问题的算着色问题的算法如下：法如下：图着色回溯法图着色回溯法：1将数组将数组colorn初始化为初始化为0；2k=1;3while(k=1)3.1 依次考察每一种颜色，若顶点依次考察每一种颜色，若顶点k的着色与其他顶点的

24、着色不发的着色与其他顶点的着色不发生冲突，则转步骤生冲突，则转步骤3.2；否则，搜索下一个颜色；否则，搜索下一个颜色；3.2 若顶点已全部着色，则输出数组若顶点已全部着色，则输出数组colorn，返回；，返回；3.3 否则，否则，3.3.1 若顶点若顶点k是一个合法着色，则是一个合法着色，则k=k+1，转步骤，转步骤3处理下一个处理下一个顶点；顶点；3.3.2 否则，重置顶点否则，重置顶点k的着色情况，的着色情况，k=k-1，转步骤，转步骤3。17PPT课件回溯法回溯法 1.void GraphColor(int n,int c ,int m)2./所有数组下标从所有数组下标从1开始开始3.f

25、or(i=1;i=1)6.colork=colork+1;7.while(colork=m)8.if Ok(k)break;9.else colork=colork+1;/搜索下一个颜色搜索下一个颜色10.if(colork=m&k=n)/求解完毕，输出解求解完毕，输出解11.for(i=1;i=n;i+)12.coutcolori;13.return;14.15.else if(colork=m&kn)16.k=k+1;/处理下一个顶点处理下一个顶点17.else colork=0;k=k-1;/回溯回溯 18.19.18PPT课件回溯法 bool Ok(int k)/判断顶点判断顶点k的着

26、色是否发生冲突的着色是否发生冲突 for(i=1;ik;i+)if(cki=1&colori=colork)return false;return true;19PPT课件贪心法 例如，图例如，图12-4(a)所示的图可以只用两种颜色着色，所示的图可以只用两种颜色着色，将顶点将顶点1、3和和4着成一种颜色，将顶点着成一种颜色，将顶点2和顶点和顶点5着成另外一种颜色。为简单起见，下面假定着成另外一种颜色。为简单起见，下面假定k个颜色的集合为个颜色的集合为颜色颜色1,颜色颜色2,颜色颜色k。（a）（b）20PPT课件贪心法 贪心策略：选择一种颜色，以任意顶点作为选择一种颜色，以任意顶点作为开始顶点

27、，依次考察图中的未被着色的每个开始顶点，依次考察图中的未被着色的每个顶点，如果一个顶点可以用颜色顶点，如果一个顶点可以用颜色1 1着色，换着色，换言之，该顶点的邻接点都还未被着色，则用言之，该顶点的邻接点都还未被着色，则用颜色颜色1 1为该顶点着色，当没有顶点能以这种为该顶点着色，当没有顶点能以这种颜色着色时，选择颜色颜色着色时，选择颜色2 2和一个未被着色的和一个未被着色的顶点作为开始顶点，用第二种颜色为尽可能顶点作为开始顶点，用第二种颜色为尽可能多的顶点着色，如果还有未着色的顶点，则多的顶点着色，如果还有未着色的顶点，则选取颜色选取颜色3 3并为尽可能多的顶点着色，依此并为尽可能多的顶点着

28、色，依此类推，如图类推，如图12.412.4（b b）所示。）所示。21PPT课件设数组设数组colorn表示顶点的着色情况，贪心法求解图着色问题的算法如表示顶点的着色情况，贪心法求解图着色问题的算法如下：下：图着色贪心法：图着色贪心法：1color1=1;/顶点顶点1着颜色着颜色12for(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 若顶点若顶

29、点i已着色，则转步骤已着色，则转步骤4.2，考虑下一个顶点，考虑下一个顶点;4.2.2 若图中与顶点若图中与顶点i邻接的顶点着色与顶点邻接的顶点着色与顶点i着颜色着颜色k不冲突，不冲突，则则colori=k;5输出输出k;22PPT课件蚁群算法设有设有k只蚂蚁只蚂蚁ai(i=1,2,k)分别代表分别代表k只蚂蚁的初始只蚂蚁的初始城市，每一只蚂蚁代表城市，每一只蚂蚁代表1种颜色，种颜色，k只蚂蚁分别遍只蚂蚁分别遍历所有的城市，历所有的城市，ai采用随机赋值的方法，城市用采用随机赋值的方法，城市用c=1,2,n表示，着色蚂蚁的移动规则如图表示，着色蚂蚁的移动规则如图12-5所示所示23PPT课件蚁

30、群算法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城市的表更新方

31、程：城市的表更新方程：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 输出满意输出满意h24PPT课件图着色问题的

32、应用安排考试问题 设学校共有设学校共有n门功课需要进行期末考试，因为不少门功课需要进行期末考试，因为不少学生不止选修一门课，所以不能把一个同学选修的学生不止选修一门课，所以不能把一个同学选修的两门课安排在同一场次进行考试。问学期的期末考两门课安排在同一场次进行考试。问学期的期末考试最少需要多少场次才能完成？试最少需要多少场次才能完成？25PPT课件 问题处理：我们以每门功课为一个顶点，当且仅问题处理：我们以每门功课为一个顶点，当且仅当两门功课被同一个学生选修时，在响应两个顶当两门功课被同一个学生选修时，在响应两个顶点之间连一条边，得到一个图点之间连一条边，得到一个图G G。我们将。我们将n n

33、门功课门功课划分成划分成k k个子集个子集U U1,1,U U2,2,U UK K两两子集的功课都不两两子集的功课都不相同。相同。每个子集每个子集UiUi（11i ik k）的顶点两两子集不相邻，）的顶点两两子集不相邻，即子集内的任意两门功课都不能被一个学生选修。即子集内的任意两门功课都不能被一个学生选修。能这种要求划分的子集数能这种要求划分的子集数K K必须最少，即不能划分必须最少，即不能划分成成k-1k-1个子集。然后我们对每个子集内的顶点涂一个子集。然后我们对每个子集内的顶点涂一种颜色。种颜色。同色顶点对应的课程安排在同一场次考试，颜色同色顶点对应的课程安排在同一场次考试，颜色数即为学期

34、考试所需要的最少场次数。数即为学期考试所需要的最少场次数。26PPT课件图着色问题的应用安排考试问题例：计算机系某学期开设了例：计算机系某学期开设了6门选修课程：数据门选修课程：数据仓库与数据挖掘，机器学习导论，语音处理与仓库与数据挖掘，机器学习导论，语音处理与压缩编码，数字媒体动画设计技术，智能信息压缩编码，数字媒体动画设计技术，智能信息处理，入侵检测技术，分别用处理，入侵检测技术，分别用a,b,c,d,e,f表示，表示，我们以每门功课为一个顶点，当且仅当两门功我们以每门功课为一个顶点，当且仅当两门功课被同一个学生选修时，在相应两个顶点之间课被同一个学生选修时，在相应两个顶点之间连一条边，学

35、生选修情况如图连一条边，学生选修情况如图12-6所示：所示：27PPT课件图着色问题的应用安排考试问题分析：利用求极小覆盖的方法求得图的一切极大独立集如下：分析：利用求极小覆盖的方法求得图的一切极大独立集如下：显然我们可以选用显然我们可以选用6种颜色给每个顶点涂色，或者选用种颜色给每个顶点涂色，或者选用5种颜色分别给种颜色分别给5个极大独立集涂色，也可以选用个极大独立集涂色，也可以选用4种颜色，例如种颜色，例如I1中的中的a,c涂颜色，涂颜色，I2中的中的b,d涂颜色涂颜色2，I3中的中的f涂颜色涂颜色3，中的，中的e涂颜色涂颜色4。但上述方案的颜色数不是但上述方案的颜色数不是X（G），正确的

36、答案应该是），正确的答案应该是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，

37、故安排三场考试：，故安排三场考试：第一场：机器学习，入侵检测技术第一场：机器学习，入侵检测技术 第二场：智能信息处理，语音处理与压缩编码第二场：智能信息处理，语音处理与压缩编码 第三场：数据仓库与数据挖掘，数字媒体动画设计第三场：数据仓库与数据挖掘，数字媒体动画设计,;,;,;,;,;,654321faIecIedIfbIdbIcaI28PPT课件图着色问题的应用交通管理系统 对于一个多叉路口，设计一个交通信号灯的管理系统：对车辆的可能对于一个多叉路口，设计一个交通信号灯的管理系统：对车辆的可能行驶方向作某种分组，对分组的要求是使任一个组中各个方向行驶的行驶方向作某种分组，对分组的要求是使任一

38、个组中各个方向行驶的车辆可以同时安全行驶而不发生碰撞。车辆可以同时安全行驶而不发生碰撞。我们将通行方向作为结点，如果某些通行方向不能同时进行，则在相我们将通行方向作为结点，如果某些通行方向不能同时进行，则在相应的结点间连一条线于是问题就转化为将结点分组，使得相连结点不应的结点间连一条线于是问题就转化为将结点分组，使得相连结点不在同一组里。在同一组里。例例3：如图：如图12-7所示，某交叉路口有所示，某交叉路口有A，B，C，D，E,五条街道，请五条街道，请设计一个交通信号灯的管理系统。设计一个交通信号灯的管理系统。图图12-7分析：首先考虑可以通行的方向分析：首先考虑可以通行的方向红：红：AB，

39、AC，AD，BA，DC，ED绿：绿：DA，DB黄：黄：EB，EC，EA蓝：蓝：BC，BDDECEBEAECDBDADDBCBABDACABA,29PPT课件图着色问题的应用交通管理系统 接下来的通行方向为结点（如图接下来的通行方向为结点（如图12-8所示），考虑结点分组所示），考虑结点分组30PPT课件图着色问题的应用交通管理系统 贪心算法设计：贪心算法设计：While有结点未着色有结点未着色选择一种新颜色；选择一种新颜色；在未着色的结点中，给尽可能的彼此结点之间没有边的点着色；在未着色的结点中，给尽可能的彼此结点之间没有边的点着色；NEW表示正确的，可以用新颜色着色的结点集合，从表示正确的，

40、可以用新颜色着色的结点集合，从V1中找出可用中找出可用新颜色着色的结点集的程序框架描述为新颜色着色的结点集的程序框架描述为New=For 每个每个vV1 doIf v与与NEW中所有结点间没有边中所有结点间没有边 从从V1中去掉中去掉v；NEW=NEWv；对图和集合的操作：对图和集合的操作：判断一个集合是否为空：判断一个集合是否为空：isSetEmpty（V1）置一个集合为空：置一个集合为空：emptySet（NEW）从集合中去掉一个元素：从集合中去掉一个元素：removeFromSet（）（）向集合里增加一个元素：向集合里增加一个元素：addToSet（）（）31PPT课件图着色问题的应用交

41、通管理系统 算法：检查结点检查结点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 +co

42、lor;return(color);32PPT课件图着色问题的应用交通管理系统 图例中分组情况如下：图例中分组情况如下：绿色：绿色：AB，AC，AD，BA，DC，ED 蓝色：蓝色：BC，BD，EA 红色：红色：DA，DB 黄色：黄色：EB，EC33PPT课件 一家公司制造一家公司制造n n种化学制品种化学制品C C1,1,C C2,2,CnCn，其，其中某些制品是互不相容的，如果它们互相接中某些制品是互不相容的，如果它们互相接触，则会引起爆炸，作为一种预防措施，公触，则会引起爆炸，作为一种预防措施，公司希望把它的仓库分为间隔，以便把不相容司希望把它的仓库分为间隔，以便把不相容的化学制品储藏在不

43、同的间隔里，试问：这的化学制品储藏在不同的间隔里，试问：这个仓库至少应该分成几个间隔？个仓库至少应该分成几个间隔？问题处理：构造一个图问题处理：构造一个图G G，其顶点集是，其顶点集是v v1,1,v v2,2,v vn n两个顶点两个顶点vivi和和vjvj相连当且仅相连当且仅党化学制品党化学制品CiCi和和CjCj互不相容，则仓库的最小互不相容，则仓库的最小间隔数即为间隔数即为G G的顶点数。的顶点数。图着色问题的应用储藏问题 34PPT课件 无环图无环图G G的一个的一个k k边着色是指边着色是指k k种颜色对于种颜色对于G G的各的各边一个分配。若没有两条边有着色相同的颜色，边一个分配

44、。若没有两条边有着色相同的颜色，则称着色是正常的。若则称着色是正常的。若G G有正常的有正常的k k边着色，则边着色，则称称k k边可着色的。若至少要用边可着色的。若至少要用k k种颜色（即可以种颜色（即可以正常正常k k边着色而不能边着色而不能k-1k-1边着色）时，则称边着色）时，则称k k为为G G的边色数，记成。顶点的边色数，记成。顶点v v关联的边中有关联的边中有i i色边时，色边时，称颜色称颜色i i色在顶点色在顶点v v出现，在顶点出现，在顶点i i出现的颜色数出现的颜色数目记成目记成C C（v v）。）。通过边顶对换法将图通过边顶对换法将图G G转换为图转换为图G G：G G图

45、中的边图中的边e e转换为图转换为图G G 中的一个顶点中的一个顶点v v；若图；若图G G中两条边相中两条边相邻，则邻，则G G 中对应两个顶点之间连一条边。然后中对应两个顶点之间连一条边。然后对图对图G G 进行顶点着色或求顶色数进行顶点着色或求顶色数x x(G G)，显然：，显然：边着色边顶对换法边顶对换法)()(GXGX35PPT课件例：求图例：求图12-9G的边色数的边色数将图将图12-9G按边顶对换法转换为按边顶对换法转换为G(图图12-10)，用最少颜色数给，用最少颜色数给G所有顶点所有顶点上色的一种方案上色的一种方案 是是 ，转换成对图转换成对图G边上色边上色边着色边顶对换法边

46、顶对换法),(7315462vvvvvvv4)(GX),(7315462eeeeeee4)(GX7327635653454514354324121211,vvvevvvevvvevvvevvvevvvevvve36PPT课件 问题描述：问题描述：给出老师与班级的任课关系，以及教室数给出老师与班级的任课关系，以及教室数的限制，给出一个合理的排课方案。的限制，给出一个合理的排课方案。算法设计：算法设计：第一步先求出最佳着色方案，然后再根据教室第一步先求出最佳着色方案，然后再根据教室数的限制求出符合教室数要求的排课方案。数的限制求出符合教室数要求的排课方案。求最佳边着色方案时，先将边转换为点，求最佳

47、边着色方案时，先将边转换为点，再采用顶着色的方法来求最佳边着色方法。先再采用顶着色的方法来求最佳边着色方法。先设计函数设计函数find来求得所有的极大独立集，再通来求得所有的极大独立集，再通过函数过函数dyeing根据已求得的极大独立集来求根据已求得的极大独立集来求最佳着色方法。最佳着色方法。边着色问题的应用排课时间表问题 37PPT课件 第二步是根据已求得的最佳着色方案和教室数，将着第二步是根据已求得的最佳着色方案和教室数，将着色方案进行调整。色方案进行调整。按照教室数和总的课程量来决定同色边集个数，按照教室数和总的课程量来决定同色边集个数，然后再调整各同色边集中的边数。然后再调整各同色边集

48、中的边数。调整方法为，若两个同色边集调整方法为，若两个同色边集Ei,EjEi,Ej所含边的数所含边的数目之差大于目之差大于1 1，则按照如下方法调整，假设，则按照如下方法调整，假设EiEi中边数中边数多则此时有两种情况：一是在多则此时有两种情况：一是在EiEi中能找一条与中能找一条与EjEj中各中各边都不相邻的边加入到边都不相邻的边加入到EjEj中；二是如果没有这样的单中；二是如果没有这样的单边时，则找这样的一条路径，它的起止边都在边时，则找这样的一条路径，它的起止边都在EiEi中，中，然后将在路径中的然后将在路径中的Ei,EjEi,Ej中的边互换。这样形成的新中的边互换。这样形成的新的同色边

49、集的同色边集EiEi和和EjEj分别替换分别替换EiEi和和EjEj。这样一边。这样一边数差异便缩小了，按照上述方法循环进行直到不存在数差异便缩小了，按照上述方法循环进行直到不存在边数之差大于边数之差大于1 1的同色边集。的同色边集。边着色问题的应用排课时间表问题 38PPT课件会场安排问题会场安排问题 问题描述：问题描述：假设要在足够多的会场里安排一批活动，并希望假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的贪心算法使用尽可能少的会场。设计一个有效的贪心算法进行安排。进行安排。这个问题实际上是著名的图着色问题。若将每一这个问题实际上是著名的图着色问题。若将每一个

50、活动作为图的一个顶点，不相容活动间用边相个活动作为图的一个顶点，不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数，相连。使相邻顶点着有不同颜色的最小着色数，相应于要找的最小应于要找的最小会场数。会场数。算法设计：算法设计：对于给定的对于给定的k k个待安排的活动，计算使用最少会场个待安排的活动，计算使用最少会场的时间表。的时间表。39PPT课件 数据输入：数据输入：给出输入数据。第一行有给出输入数据。第一行有1 1 个正整数个正整数k k，表示有，表示有k k个待安排个待安排的活动。接下来的的活动。接下来的k k行中，每行有行中，每行有2 2个正整数，分别表示个正整数，分别表示k k个