资源预览内容
第1页 / 共61页
第2页 / 共61页
第3页 / 共61页
第4页 / 共61页
第5页 / 共61页
第6页 / 共61页
第7页 / 共61页
第8页 / 共61页
第9页 / 共61页
第10页 / 共61页
亲,该文档总共61页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
Axon着色问题与排队论廖波问题来源 图的着色问题是由地图的着色问题引申而来的:用m种 颜色为地图着色,使得地图上的每一个区域着一种颜 色,且相邻区域颜色不同。 问题处理:如果把每一个区域收缩为一个顶点,把相邻 两个区域用一条边相连接,就可以把一个区域图抽象 为一个平面图。 例如,图12-1(a)所示的区域图可抽象为12-1(b)所 表示的平面图。19世纪50年代,英国学者提出了任何 地图都可以4中颜色来着色的4色猜想问题。过了100 多年,这个问题才由美国学者在计算机上予以证明, 这就是著名的四色定理。例如,在图12-1中,区域用 城市名表示,颜色用数字表示,则图中表示了不同区 域的不同着色问题 。问题来源图的着色 4通常所说的着色问题是指下述两类问题: 41给定无环图G=(V,E),用m种颜色为图中 的每条边着色,要求每条边着一种颜色,并 使相邻两条边有着不同的颜色,这个问题称 为图的边着色问题。 42给定无向图G=(V,E),用m种颜色为图中 的每个顶点着色,要求每个顶点着一种颜色 ,并使相邻两顶点之间有着不同的颜色,这 个问题称为图的顶着色问题。顶点着色基本概念4独立集:对图G=(V,E),设S是V的一个子集,若中任 意两个顶点在G中均不相邻,则称S为G的一个独立集 。 4最大独立集:如果G不包含适合|S|S|的独立集S, 则称S为G的最大独立集。 4极大覆盖:设K是G的一个独立集,并且对于VK的 任一顶点v,K+v都不是G的独立集,则称K是G的一 个极大覆盖。 4极小覆盖:极大独立集的补集称为极小覆盖。V的子集K是G的极小覆盖当且仅当:对于每个顶点v 或者v属于K,或者v的所有邻点属于K(但两者不同 时成立)。顶点着色基本概念4K可着色:G的一个k顶点着色是指k种颜色1,2,k对于G各顶 点的一个分配,如果任意两个相邻顶点都分配到不同的颜色, 则称着色是正常的。换句话说,无环图G的一个正常k顶点着 色是把V分成k个(可能有空的)独立集的一个分类 (V1,V2,Vk)。当G有一个正常k顶点着色时,就成G是k顶点可 着色的。 4G的色数X(G)是指G为k可着色的k的最小值,若X(G)=k ,则称G是k色的。 4事实上,如果我们将同色的顶点列入一个顶点子集,那么求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(逻辑积)。 4例如,指令“选择a与b,或者选择b与c”证为ab+bc。 从形式上看,逻辑和与逻辑积类似与集合的和, 而且关于和成立的代数法则对于这两个运算也成 立。 4布尔恒等式 aa=a 4 a+a=a 4 a+ab=a 4如:求极小覆盖法布尔代数法4例1:求图12-2G的顶色数 解: 4Step1:求极大独立集先求图G的极小覆盖,化简得故G的极小覆盖为 取其补集,得到G的所有 极大独立集: 4Step2:求出一切若干极大独立集和所有顶点的子集显然我们可以选用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着色 法 4I将图G中的结点按度数的递减顺序进行排列(这种 排列可能不是唯一的,因为有些结点的度数相同)。4II用第一种颜色对第一结点着色,并按排列顺序对 与前面着色结点不邻接的每一结点着上同样的颜色。4III用第二种颜色对尚未着色的结点重复II,用第三 种颜色继续这种做法,直到所有的结点全部着上色为 止。穷举法Welch Powell着色 法 4给定图G,用Welch Powell法对图G着色A4A2A3A6A532113穷举法Welch Powell着色 法 4第一步:将图G中的结点按度数的递减顺序排列 :4第二步:用第一种颜色对A5着第一种颜色,并 对与A5不邻接的结点A1也着第一种颜色。4第三步:对结点A3及与A3不邻接的结点A4、A8 着第二种颜色。4第四步:对结点A7及与A7不邻接的结点A2、A6 着第三种颜色。可见,图G是三色的。但图G不可能是二色的, 因为A1, A2, A3相互邻接,故必须着三种颜色。 所以x(G)=3。 回溯法 4由于用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,如此等等。 4如果在n元组C中,所有相邻顶点都不会着相同颜色,就称 此n元组为可行解,否则为无效解。 4回溯法求解图着色问题:首先把所有顶点的颜色初始化为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)。回溯法 4设数组colorn表示顶点的着色情况,回溯法求解m着色问题的 算法如下: 4图着色回溯法: 41将数组colorn初始化为0; 42k=1; 43while (k=1) 43.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。回溯法 4void GraphColor(int n, int c , int m) 4 /所有数组下标从1开始 4 4 for (i=1; i=1) 4 4 colork=colork+1; 4 while (colork=m) 4 if Ok(k) break; 4 else colork=colork+1; /搜索下一个颜色 4 if (colork=m i=n; i+) 4 coutcolori; 4 return; 4 4else if (colork=m /处理下一个顶点 4 else 4 colork=0; 4 k=k-1; /回溯 4 4 4 4 回溯法 4bool Ok(int k) /判断顶点k的着色是否发生冲突4 4 for (i=1; ik; i+) 4 if (cki= =1 4 return true;4 贪心法 例如,图12-4(a)所示的图可以只用两种颜色着色,将顶 点1、3和4着成一种颜色,将顶点2和顶点5着成另外 一种颜色。为简单起见,下面假定k个颜色的集合为 颜色1, 颜色2, , 颜色k。(a) (b)贪心法4贪心策略:选择一种颜色,以任意顶点作为开始顶点,依次考察图中的未被着色 的每个顶点,如果一个顶点可以用颜色1着色,换言之,该顶点的邻接点都还未 被着色,则用颜色1为该顶点着色,当没有顶点能以这种颜色着色时,选择颜色2 和一个未被着色的顶点作为开始顶点,用第二种颜色为尽可能多的顶点着色,如 果还有未着色的顶点,则选取颜色3并为尽可能多的顶点着色,依此类推,如图 12.4(b)所示。 4设数组colorn表示顶点的着色情况,贪心法求解图着色问题的算法如下: 4图着
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号