《平面图的面着色课件》由会员分享，可在线阅读，更多相关《平面图的面着色课件（23页珍藏版）》请在金锄头文库上搜索。
1、第第62讲讲 平面图的面着色平面图的面着色平面图的面着色课件第第7章章 几类特殊的图几类特殊的图7.6 平面图的面着色平面图的面着色平面图的面着色课件本讲内容本讲内容平面图的面着色平面图的面着色1任意无向图的节点着色任意无向图的节点着色2任意任意无向无向图的边着色图的边着色3平面图的面着色课件7.6 平面图的面着色平面图的面着色“四色猜想四色猜想”(4CC, Four Color Conjecture).本节主要内容是平面图的面着色问题本节主要内容是平面图的面着色问题, ,顺便顺便介绍任意无向图的节点着色以及边着色等介绍任意无向图的节点着色以及边着色等有关内容有关内容. .平面图的面着色课件1
2、. 平面图的面着色平面图的面着色Def 设设G是平面图是平面图, 若对若对G的每个面涂上一种的每个面涂上一种颜色且相邻的面出现不同的颜色颜色且相邻的面出现不同的颜色, 则称对该则称对该平面图的平面图的面着色面着色(face coloring), 所需颜色所需颜色的最少种数称为面着色数的最少种数称为面着色数(region chromatic number).平面图的面着色课件Remark 任意平面图均有无限面任意平面图均有无限面.平面图的面着色课件2.任意任意无向无向图的节点着色图的节点着色(1) 任意任意无向无向图的节点着色图的节点着色Def 设设G是任意无向图是任意无向图, 若对若对G的每个
3、节点涂的每个节点涂上一种颜色且相邻的节点出现不同的颜色上一种颜色且相邻的节点出现不同的颜色,则称对该图的节点着色则称对该图的节点着色(vertex coloring), 简称简称着色着色(coloring), 所需颜色的最少种数所需颜色的最少种数称为节点着色数称为节点着色数, 简称着色数简称着色数(chromatic number),记为记为 平面图的面着色课件平面图的面着色课件Theorem 7-13 G无自环无自环, 则则可以利用韦尔奇可以利用韦尔奇 鲍威尔鲍威尔(Welch Powell)算法算法对图的节点着色对图的节点着色, 进而求出的上界进而求出的上界.平面图的面着色课件Step 1
4、 将节点按度数从大到小的顺序排列将节点按度数从大到小的顺序排列.Step 2 用第一种颜色对第一个节点着色用第一种颜色对第一个节点着色,并并且按照其余未着色节点顺序且按照其余未着色节点顺序, 对不邻接的每对不邻接的每一个节点着上同样的颜色一个节点着上同样的颜色.Step 3 用第二种颜色对尚未着色的节点重用第二种颜色对尚未着色的节点重复复Step 2, 继续下去继续下去, 直到所有的点都着色为直到所有的点都着色为止止.平面图的面着色课件例例8-19平面图的面着色课件平面图的面着色课件平面图的面着色课件(2) 平面图的节点着色平面图的节点着色平面图的节点着色与一般无向图的节点着平面图的节点着色与
5、一般无向图的节点着色是相同的色是相同的. 平面图的面着色平面图的面着色,可以转换为可以转换为其对偶图其对偶图(也是平面图也是平面图)的节点着色的节点着色. Theorem 7-14(五色定理五色定理) 设设G是简单平面是简单平面图图,则则Hint 对对G的节点个数的节点个数n归纳归纳.平面图的面着色课件3. 任意无向图的边着色任意无向图的边着色Def 设设G是任意无向图是任意无向图, 若对若对G的每条边涂上的每条边涂上一种颜色且相邻的边出现不同的颜色一种颜色且相邻的边出现不同的颜色, 则称则称对该图的对该图的边着色边着色(edge coloring), 所需颜色所需颜色的最少种数称为边着色数的
6、最少种数称为边着色数(edge-chromatic number).图中的图中的两条边相邻两条边相邻是指它们有公共的节点是指它们有公共的节点. 平面图的面着色课件平面图的面着色课件最后对与最后对与Ramsey理论密切相关的图的边理论密切相关的图的边“涂色涂色”的问题进行简单说明的问题进行简单说明. Ramsey问题问题(Ramsey problem) 任给一群人任给一群人,其中有其中有p个人彼此认识或有个人彼此认识或有q个人彼此不认个人彼此不认识识,这种人群至少多少人这种人群至少多少人?Ramsey问题中的答案记为问题中的答案记为R(p, q).平面图的面着色课件例例7-20 证明证明: 任意
7、任意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) , Last accessed 14 June, 2013.平面图的面着色课件小结与作业小结与作业平面图的面着色平面图的面着色任意图的节点着色任意图的节点着色任意图的边着色任意图的边着色习题习题7.6 1, 3, 9作业作业平面图的面着色课件Any Questions?平面图的面着色课件平面图的面着色课件
