第62讲-平面图的面着色.pptx

第第7章章 几类特殊的图几类特殊的图7.6 平面图的面着色平面图的面着色本讲内容本讲内容平面图的面着色平面图的面着色1任意无向图的节点着色任意无向图的节点着色2任意任意无向无向图的边着色图的边着色37.6 平面图的面着色平面图的面着色“四色猜想四色猜想”(4CC,Four Color Conjecture).本节主要内容是平面图的面着色问题本节主要内容是平面图的面着色问题,顺便顺便介绍任意无向图的节点着色以及边着色等介绍任意无向图的节点着色以及边着色等有关内容有关内容.1.平面图的面着色平面图的面着色Def 设设G是平面图是平面图,若对若对G的每个面涂上一种的每个面涂上一种颜色且相邻的面出现不同的颜色颜色且相邻的面出现不同的颜色,则称对该则称对该平面图的平面图的面着色面着色(face coloring),所需颜色的所需颜色的最少种数称为面着色数最少种数称为面着色数(region chromatic number).Remark 任意平面图均有无限面任意平面图均有无限面.2.任意任意无向无向图的节点着色图的节点着色(1)任意任意无向无向图的节点着色图的节点着色Def 设设G是任意无向图是任意无向图,若对若对G的每个节点涂的每个节点涂上一种颜色且相邻的节点出现不同的颜色上一种颜色且相邻的节点出现不同的颜色,则称对该图的节点着色则称对该图的节点着色(vertex coloring),简简称称着色着色(coloring),所需颜色的最少种数称为所需颜色的最少种数称为节点着色数节点着色数,简称着色数简称着色数(chromatic number),记为记为 Theorem 7-13 G无自环无自环,则则可以利用韦尔奇可以利用韦尔奇 鲍威尔鲍威尔(Welch Powell)算法算法对图的节点着色对图的节点着色,进而求出的上界进而求出的上界.Step 1 将节点按度数从大到小的顺序排列将节点按度数从大到小的顺序排列.Step 2 用第一种颜色对第一个节点着色用第一种颜色对第一个节点着色,并并且按照其余未着色节点顺序且按照其余未着色节点顺序,对不邻接的每对不邻接的每一个节点着上同样的颜色一个节点着上同样的颜色.Step 3 用第二种颜色对尚未着色的节点重用第二种颜色对尚未着色的节点重复复Step 2,继续下去继续下去,直到所有的点都着色为直到所有的点都着色为止止.例例8-19(2)平面图的节点着色平面图的节点着色平面图的节点着色与一般无向图的节点着平面图的节点着色与一般无向图的节点着色是相同的色是相同的.平面图的面着色平面图的面着色,可以转换为其可以转换为其对偶图对偶图(也是平面图也是平面图)的节点着色的节点着色.Theorem 7-14(五色定理五色定理)设设G是简单平面图是简单平面图,则则Hint 对对G的节点个数的节点个数n归纳归纳.3.任意无向图的边着色任意无向图的边着色Def 设设G是任意无向图是任意无向图,若对若对G的每条边涂上的每条边涂上一种颜色且相邻的边出现不同的颜色一种颜色且相邻的边出现不同的颜色,则称则称对该图的对该图的边着色边着色(edge coloring),所需颜色的所需颜色的最少种数称为边着色数最少种数称为边着色数(edge-chromatic number).图中的图中的两条边相邻两条边相邻是指它们有公共的节点是指它们有公共的节点.最后对与最后对与Ramsey理论密切相关的图的边理论密切相关的图的边“涂色涂色”的问题进行简单说明的问题进行简单说明.Ramsey问题问题(Ramsey problem)任给一群人任给一群人,其中有其中有p个人彼此认识或有个人彼此认识或有q个人彼此不认个人彼此不认识识,这种人群至少多少人这种人群至少多少人?Ramsey问题中的答案记为问题中的答案记为R(p,q).例例7-20 证明证明:任意任意6个人中个人中,有有3个人彼此认个人彼此认识或有识或有3个人彼此不认识个人彼此不认识.R(3,3)=6(1930).其他其他Ramsey数数?R(3,4)=9,R(3,5)=14,R(4,4)=18(1955).R(3,6)=18(1964,1966).R(3,7)=23(1968).R(3,9)=36(1982).R(3,8)=28(1992).R(4,5)=25(1993).43R(5,5)49(1989,1995)http:/ accessed 14 June,2013.小结与作业小结与作业平面图的面着色平面图的面着色任意图的节点着色任意图的节点着色任意图的边着色任意图的边着色习题习题7.6 1,3,9作业作业Any Questions?