南开大学计算机算法设计与分析

1、ABC每个盘子有三个位置,n个共有3n 共有共有 13条路线：条路线：ab , ac , adba , bc , bdda , db , dcea , eb , ec , ed1.1.3 图着色问题 已知：已知：n点无向图点无向图G = , |V| = n 。求：G的最小色数的最小色数(color number)k，使得用，使得用k种颜色对种颜色对G的的顶点着色，可令任二相邻顶点着色不同。顶点着色，可令任二相邻顶点着色不同。 地图着色问题，交通信号灯问题都可以归结为图的顶点着色问题地图着色问题，交通信号灯问题都可以归结为图的顶点着色问题无向图顶点着色问无向图顶点着色问题：题：顶点，边顶点，边最

2、小色数最小色数k k地图着色问题：地图着色问题：国家，相邻国家，相邻关系关系最小色数最小色数k k交通信号灯问题：交通信号灯问题： 路线，交叉路线，交叉关系关系最小相位（组）最小相位（组）数数k k2.图着色图着色(Graph Coloring）问题）问题 图着色问题图着色问题是一个经典的组合算法问题，源于地图是一个经典的组合算法问题，源于地图着色问题。着色问题。 在绘制地图时，总是要求相邻的国家着上不同的在绘制地图时，总是要求相邻的国家着上不同的颜色以示区别。颜色以示区别。1852年一位英国大学生古德里年一位英国大学生古德里（F.Guthrie）提出了一个猜测：为了给任一个平面）提出了一个猜

3、测：为了给任一个平面地图着色，并使任何有公共边界的区域颜色不同，地图着色，并使任何有公共边界的区域颜色不同，至多需要四种颜色。这就是至多需要四种颜色。这就是四色问题四色问题，又称，又称四色猜四色猜想想。古德里仅仅是提出了这个猜想，他和他的老师。古德里仅仅是提出了这个猜想，他和他的老师未能证明。未能证明。图着色图着色(Graph Coloring）问题）问题 二十几年后的二十几年后的1878年，著名数学家凯莱（年，著名数学家凯莱（A.Kayley）发表了一篇发表了一篇“论地图着色论地图着色”的文章，虽然仍没有解决这的文章，虽然仍没有解决这个问题，却掀起了四色猜想的研究热。个问题，却掀起了四色猜想

4、的研究热。 经过一百年的探索，美国伊利诺大学的哈肯（经过一百年的探索，美国伊利诺大学的哈肯（W.Haken）与阿佩尔（与阿佩尔（K.Appel）通过改进算法，借助计算机（共）通过改进算法，借助计算机（共用了用了1200个机时）终于在个机时）终于在1976年完成了四色猜想的证年完成了四色猜想的证明。当地的邮局在寄出的信上除了通常的邮戳明。当地的邮局在寄出的信上除了通常的邮戳(postmark)外，还要加盖外，还要加盖“四色是足够的四色是足够的”一句话以一句话以表示自豪。表示自豪。. 图着色图着色(Graph Coloring）问题）问题 当把地图当把地图(Map)上的一个国家与图上的一个国家与图

5、(Graph)上的一个顶上的一个顶点对应，两个国家的相邻关系对应于无向图上的边，点对应，两个国家的相邻关系对应于无向图上的边，于是，上面关于地图的于是，上面关于地图的“四色问题四色问题”实际上是无向图实际上是无向图的顶点着色问题的特例。的顶点着色问题的特例。 无向图的顶点无向图的顶点着色问题是一个有名的着色问题是一个有名的NP完全问题完全问题，这，这类问题属于类问题属于“计算机难解计算机难解”问题，关于着色问题算法问题，关于着色问题算法的研究已有许多学者的大量成果。的研究已有许多学者的大量成果。 c例如例如Fig.1.3中的中的5点无向图，用贪点无向图，用贪心法着色需要用红心法着色需要用红(R

6、)、黄、黄(Y)、蓝、蓝(B)三种颜色，但实际上，这不是三种颜色，但实际上，这不是该图的最小色数，显然，两种颜该图的最小色数，显然，两种颜色已可满足要求。即：顶点色已可满足要求。即：顶点1、3、4着红色，顶点着红色，顶点2、5着黄色。着黄色。(不同不同编号顺序编号顺序) cv3.算法设计讨论 算法的研究与许多实际应用问题直接相关，它不仅是个理论问题； 一些典型的算法问题的研究，如着色问题、旅行商问题、背包问题等等，常常在应用算法的设计中发挥作用； 用来解一个问题，可以有多种不同的算法，它们的效果可能差别很大，如何设计有效的算法是算法理论的主要目标。 04710904223048760W抽象级抽

7、象级更新速度更新速度算法算法程序设计方法程序设计方法程序设计语言程序设计语言编程工具编程工具A B CA B C算法B有条件优于算法A：在实际应用中问题规模是给定的 nDI) I ( t ) I (P)n(A1)I(PnDI n)q1()1n(2qn)q1(inq)I ( t )I (P)n(An1i1n1iii 1k, 2)2n(T)2n(T1k,10k,0)n(T22n32222)2(T22)2)4n(T2(22)2n(T2)n(Tk1k1k1ii1k K=log2n 22/n32/n)1n()1n(SS)n(T51ii61ii nnk1ii )n(g)n(TC)n(Tk1iii )n(g

8、)n(TC)n(Tk1iii 1a)n(logO1a)n(O)n(Tbalogb)n(logO)n(logOb ba)n(Oba)nlogn(Oba)n(O)n(Talogb)n(O)n(O)n(T2log2 第一章完第一章完int GColor(E)int i,j,k =1,colorn+1;color1 =1;for (i =2; i =n; i+) colori =0;/2开始所有点为未着色开始所有点为未着色 do /用色用色k为尽可能多点着色为尽可能多点着色 for (i =2; i 0) continue; /该点已着色则下一点该点已着色则下一点 for (j =1; j i; j+) if (colorj=k)&(E) break;/如果有点着此色如果有点着此色 且与点且与点i相邻相邻,则则i不能着色不能着色k if (j = i) colori =k; j =2;while (color