,计算机专业基础课程,PowerPoint Template_Sub,二分图,平面图,树,平面图的着色与树,离散数学第23讲,Page 140 to 147,-4-,第23讲 平面图的着色与树,1852年，格思里(Francis Guthrie)注意到美国地图可以用4种颜色染色, 使得相邻区域(有一段公共边界,不只是有一个公共点)有不同颜色;提出四色猜想,-5-,第23讲 平面图的着色与树,1878年，德.莫尔根(De.Morgan)凯莱(Cayley)把它提到伦敦数学学会上，“四色猜想”公诸于世，引起了各国数学界的注意和兴趣。 1879年，开姆玻(Kempe)发表了第一个“证明” 1890年，希伍德(Heawood)发现了开姆玻的一个推理错误，对其证明加以修改，提出并证明了“五色定理”,-6-,第23讲 平面图的着色与树,1969年，奥尔(Ore)和斯坦普尔(Stemple)对少于40个国家的所有地图，证明了“四色猜想”的正确性。然而对任意多个国家，“四色猜想”的正确性仍然没有证明出来。 1976年，美国数学家阿佩尔(K.Appel)和黑肯(W.Hakan)首次应用计算机证明了这一难题，使“四色猜想”成为“四色定理”。他们从1976年1月至6月在三部计算机上用了1200小时，作了近百亿次逻辑判断才得出结果，证明的正确性如果不借助计算机也无法检验。 至今还没有找到能用“纸和笔”给出的证明。但人们已经知道沿着上述方向是不可能使证明得到实质性的简化。,-7-,第23讲 平面图的着色与树,着色问题,图的点着色,平面图的面着色,-8-,第23讲 平面图的着色与树,平面图的面着色问题,四色难题：是否任何平面图均可以4着色？ 容易证明：任何平面图均可以5着色。 为便于研究，先把面着色转化为点着色 任一平面图都有一个对偶图，平面图的面和它的对偶图的结点有着一一对应的关系，所以对平面图面的着色，可归化为对其对偶图点的着色，显然研究平面图点的着色要比研究图的着色更为方便。所以对地图面的着色都是归化为点的着色进行研究的。,-9-,第23讲 平面图的着色与树,对偶图,对连通平面图G实施下列步骤所得到的图G*称为G的对偶图(dual of graph)： (1)在G的每一个面ri的内部作一个G*的顶点vi*。 (2)若G中面ri 与rj 有公共边界，那么过边界的每一边ek作关联vi*与vj*的一条边ek*。 ek*与G*的其它边不相交。 (3)当ek为面ri的边界而非ri与其它面的公共边界时，作vi*的一条环与ek相交(且仅交于一处)。所作的环不与G*的边相交。,-10-,第23讲 平面图的着色与树,对偶图例2,(3)当ek为面ri的边界而非ri与其它面的公共边界时，作vi*的一条环与ek相交(且仅交于一处)。所作的环不与G*的边相交。,(1)在G的每一个面ri的内部作一个G*的顶点vi*。,(2)若G中面ri 与rj 有公共边界，那么过边界的每一边ek作关联vi*与vj*的一条边ek*。 ek*与G*的其它边不相交。,b,d,e,c,a,v2,v3,v1,-11-,第23讲 平面图的着色与树,对偶图例1,(3)当ek为面ri的边界而非ri与其它面的公共边界时，作vi*的一条环与ek相交(且仅交于一处)。所作的环不与G*的边相交。,(1)在G的每一个面ri的内部作一个G*的顶点vi*。,(2)若G中面ri 与rj 有公共边界，那么过边界的每一边ek作关联vi*与vj*的一条边ek*。 ek*与G*的其它边不相交。,-12-,第23讲 平面图的着色与树,对偶图例,同构图的对偶图可能不同构 左边的对偶图有5度顶点, 右边的对偶图却没有 平面图的对偶图仍为平面图,b,d,e,c,a,f,b,d,e,c,a,f,2,5,3,6,1,4,2,5,3,6,1,4,2,5,3,6,1,4,-13-,第23讲 平面图的着色与树,可k着色,定义: 无环图G称为可k-着色的，如果可用k种颜色给G的所有顶点着色，使每个顶点着一种颜色，而同一边的两个端点着不同颜色。 若任意平面图可k-着色，则任意平面图的面可用k种颜色之一着色，使得相邻的面着不同颜色,-14-,第23讲 平面图的着色与树,5色定理,定理: 任何平面图都是可5-着色的。 证： 连通分支、环和平行边与着色问题无关，因此 可只讨论平面连通简单图。 设G为任一平面连通简单图，顶点个数为n 。对n归纳。 当n5时命题显然成立。 设n-1个顶点的平面图都是可5-着色的。考虑n个顶点的图G。 由 定理8.9 顶点数n不少于4的平面连通简单图G，至少 有一个顶点的度数不大于5。 可知G至少有一个顶点的度不大于5，设v0为这样一个顶点。,-15-,第23讲 平面图的着色与树,5色定理,将v0及与它关联的边中删去，得图G0=G-v0有n-1个结点， 根据假设前论G0是5可着色的。 现在将v0及原来与它关联的边仍加到G0上，图又恢复为n个结点的图G，这时有两种可能： 1）设d (v0) 5，那么只要取它相邻顶点所着颜色（至多4种)之外的一种颜色给v0着色，便可完成对G的5-着色。 2）设d (v0) = 5，如果证明与v0相邻的顶点可用少于五种颜色着色，便可完成对G的5-着色。,-16-,第23讲 平面图的着色与树,5色定理,RY表示G-v0中所有着红、黄顶点的集合， BW表示G - v0中所有着黑、白顶点的集合。 去掉v0，考虑RY生成的G的子图G(RY)。有两种可能： a）若v1，v3分属于G(RY)的两个不同的连通分支，那么只要将v1所在分支的红、黄顶点的着色作一对换(从而v1着黄色)，便可给v0着红色以完成对G的5-着色。,v0,v2,v3,v4,v5,v1,-17-,第23讲 平面图的着色与树,5色定理,b) 若v1和v3同属于一个G(RY)的连通分支，那么从v1到v3必有一条通路，其各顶点被红、黄两色相间着色。这条通路连同v0便构成回路C：v0, v1, v3, v0, C把BW分成两部分，一部分在回路C之外，一部分在回路C之内。 这时结点v2在回路C内，而结点v4在回路C外，v2与v4的任何连线必与回路C 相交，与平面图的条件矛盾。,回路C,-18-,第23讲 平面图的着色与树,5色定理,因此，回路C 必将黑白集中的结点分成两个连通分支，使v2与v4分别处于两个连通分支中（也就是v2与v4不连通）。 于是问题回到a)，可将v2(或v4)所在的分支中的黑白色对换，于是与v0邻接的5个结点也只着了4种颜色， v0就可着第5种颜色，完成对G的5-着色。 归纳完成，定理得证。,-19-,第23讲 平面图的着色与树,点着色问题应用,某校计算机系三年级学生在本学期共选6门选修课Ci, i=1, 2, , 6。设S(Ci)为选Ci课的学生集。已知 S(Ci)S(C6) , i=1, 2, , 5， S(Ci)S(Ci+1) , i=1, 2, 3, 4， S(C5)S(C1) . 问这6门课至少几天能考完？,做无向图G=，V=C1, C2, , C6， E=(Ci,Cj)| S(Ci)S(Cj)，如图所示。 给G一种着色（点着色）， Ci与Cj着同色 Ci与Cj不相邻 没有学生既学Ci又学Cj Ci与Cj可同时考 于是最少的考试时间为4天,-20-,第23讲 平面图的着色与树,PowerPoint Template_Sub,二分图,平面图,树,-21-,第23讲 平面图的着色与树,引言,树的术语起源于植物学和族谱学 树是不包含回路的连通图 今天树在计算机科学、化学、地质学、植物学、心理学等多种学科利用来构造各种各样的问题模型 树在计算机科学中非常有用，例如用最便宜的线路构造计算机网络、多播传输路径、构造存储和传输数据的有效编码、建立决策模型等等,-22-,第23讲 平面图的着色与树,树的基本概念,连通无回路的无向图称为无向树，简称为树(tree)。 树中的悬挂点又称为树叶(leave)， 其它结点称为分支点(branched node)。 单一孤立结点称为空树(null tree)。 诸连通分支均为树的图称为森林(forest)，树也是森林。,-23-,第23讲 平面图的着色与树,树的性质,树和森林都是可2-着色的，从而都是二分图。 树和森林都是平面图，其面数为1。 定理8.14 设图T为一树，其顶点数、边数分别是n, m, 那么nm=1或m=n1。 定理8.15 任何不少于两个顶点的树都至少有两片叶,证： 设图T为一树，其顶点数、边数分别是n, m, 又设 T中至多只有一个顶点是叶，那么 2m = (vi) 2(n 1)+1 = 2n 1 m n 1/2 n 1 与定理8.14矛盾，因此T至少有两片叶子。,-24-,第23讲 平面图的着色与树,树的等价定义,(0) T连通无回路。 (1) T无回路且m = n1。 (2) T连通且m = n1。 (3) T无回路，但任意添加边时，T中产生唯一一条回路。 (4) T连通，但删去任一边时便不再连通。 (5) 任意两个不同顶点之间有且仅有一条通路。,-25-,第23讲 平面图的着色与树,树的等价定义,(1)T无回路且m = n1。 (2)T连通且m = n1。,(1)(2) 设T无回路，m = n 1 ，欲证T连通。反设T有k个连通分支(k2)，T1， ，Tk，因为每个Ti中均无回路，因而每个Ti均为树。每个它们的顶点数分别是n1, , nk,边数分别是m1, , mk，显然 mi = ni 1 (i=1,2,k) 于是 矛盾。因此T连通。,-26-,第23讲 平面图的着色与树,树的等价定义,(2)T连通且m = n1。 (3)T无回路，但任意添加边时，T中产生唯一一条回路。,(2)(3) 设T连通且m=n1 。先证T无回路，为此对n归纳。 n = 1时显然T无回路，因这时m=n1=0。 设顶点数为n1 的满足题设的图无回路，顶点数为n的图T至少有两个悬挂点(即度为1的点)（用定理8.15 可证，T 至少有两个悬挂点）。去掉一悬挂点构成T。显然T仍连通，且m=m1=n2 = n1 ，因此由归纳假设T无回路。在T上加回所删去的悬挂点得T，故T亦无回路。 再证(3)的第二部分。设在T的顶点vi, vj间添加边e。由于T连通，故原本有vi到vj的通路，此通路连同边e构成Te的一条回路。若此回路不唯一，那么去掉边e后T仍有回路，与以上证明冲突。,-27-,第23讲 平面图的着色与树,树的等价定义,(0)T连通无回路。 (1)T无回路且m = n1。 (2)T连通且m = n1。 (3)T无回路，但任意添加边时，T中产生唯一一条回路。 (4)T连通，但删去任一边时便不再连通。 (5)任意两个不同顶点之间有且仅有一条通路。,(5) (0) 设T的任何两个顶点之间有且仅有一条通路，那么T显然连通。T也是无回路的，否则T中有回路上顶点vi ， vj ，使vi到vj有两条通路，与题设矛盾,(3) (4) 留给读者自行证明。 (4) (5) 留给读者自行证明。,-28-,第23讲 平面图的着色与树,树的特性,最小的连通图：删去任一条边，图就不再连通； 最大的无回路图：加上任一条边(不是环也不是平行边)，图中会产生回路。,-29-,第23讲 平面图的着色与树,生成树(spanning tree),定义：如果图T为无向图G的生成子图且T为树，则称T为G的生成树 （如果G1是G2的子图，且V1=V2，称G1为G2的生成子图） 定理8.17(生成树的存在性定理）：任一连通图G都至少有一棵生成树。 上述定理还可加强为“无向图G是连通的当且仅当G具有生成树”,-30-,第23讲 平面图的着色与树,生成树的性质？,设G为连通无向图，那么G的任一回路与任一生成树T的关于G的补GT (即在G中删去T中的边所得的图