《离散数学 第2版 教学课件 ppt 作者 王元元 离散第23讲 平面图的着色与树》由会员分享，可在线阅读，更多相关《离散数学 第2版 教学课件 ppt 作者 王元元 离散第23讲 平面图的着色与树（40页珍藏版）》请在金锄头文库上搜索。
1、,计算机专业基础课程,授课人：王元元 单位：计算机理论教研室,理工大学指挥自动化学院,PowerPoint Template_Sub,二分图,平面图,树,平面图的着色与树,离散数学第23讲,Page 140 to 147,-4-,第23讲 平面图的着色与树,着色问题,图的点着色,平面图的面着色,-5-,第23讲 平面图的着色与树,平面图的面着色问题,四色难题：是否任何平面图均可以4着色？ 容易证明：任何平面图均可以5着色。 为便于研究，先把面着色转化为点着色,-6-,第23讲 平面图的着色与树,对偶图,对连通平面图G实施下列步骤所得到的图G*称为G的对偶图(dual of graph)： (1
2、)在G的每一个面ri的内部作一个G*的顶点vi*。 (2)若G中面ri 与rj 有公共边界，那么过边界的每一边ek作关联vi*与vj*的一条边ek*。 ek*与G*的其它边不相交。 (3)当ek为面ri的边界而非ri与其它面的公共边界时，作vi*的一条环与ek相交(且仅交于一处)。所作的环不与G*的边相交。,-7-,第23讲 平面图的着色与树,对偶图例,-8-,第23讲 平面图的着色与树,对偶图例,同构图的对偶图可能不同构 左边的对偶图有5度顶点, 右边的对偶图却没有 平面图的对偶图仍为平面图,-9-,第23讲 平面图的着色与树,可k着色,定义: 无环图G称为可k-着色的，如果可用k种颜色给G
3、的所有顶点着色，使每个顶点着一种颜色，而同一边的两个端点着不同颜色。 若任意平面图可k-着色，则任意平面图的面可用k种颜色之一着色，使得相邻的面着不同颜色,-10-,第23讲 平面图的着色与树,5色定理,定理: 任何平面图都是可5-着色的。 证： 连通分支、环和平行边与着色问题无关，因此 可只讨论平面连通简单图。 设G为任一平面连通简单图，顶点个数为n 。对n归纳。 当n5时命题显然成立。 设n-1个顶点的平面图都是可5-着色的。考虑n个顶点的图G。,-11-,第23讲 平面图的着色与树,5色定理,由定理9.9，G至少有一个顶点的度不大于5，设v0为这样一个顶点。 设d (v0) 5，那么只要
4、取它相邻顶点所着颜色（至多4种)之外的一种颜色给v0着色，便可完成对G的5-着色。 设d (v0) = 5，如果证明与v0相邻的顶点可用少于五种颜色着色，便可完成对G的5-着色。,-12-,第23讲 平面图的着色与树,5色定理,为叙述简明，令RY表示G-v0中所有着红、黄顶点的集合，BW表示G - v0中所有着黑、白顶点的集合。考虑RY生成的G的子图G(RY)。 若v1，v3分属于G(RY)的两个不同的连通分支，那么只要将v1所在分支的红、黄顶点的着色作一对换(从而v1着黄色)，便可给v0着红色以完成对G的5-着色。,-13-,第23讲 平面图的着色与树,5色定理,若v1和v3同属于一个G(R
5、Y)的连通分支，那么从v1到v3必有一条通路，其各顶点被红、黄两色相间着色。这条通路连同v0便构成回路C：v0, v1, v3, v0, C把BW分成两部分，一部分在回路C之外，一部分在C之内。,回路C,-14-,第23讲 平面图的着色与树,5色定理,于是，BW生成的G的子图也被分成了两个互不连通的部分，一部分在C外，一部分在C内，这就使v2，v4处于BW生成的G的子图的两个不同连通分支，同上将v2所在分支作颜色对换，以便给v0着上白色，完成对G的5-着色。 归纳完成，定理得证。,-15-,第23讲 平面图的着色与树,引言,树的术语起源于植物学和族谱学 树是不包含回路的连通图 今天树在计算机科
6、学、化学、地质学、植物学、心理学等多种学科利用来构造各种各样的问题模型 树在计算机科学中非常有用，例如用最便宜的线路构造计算机网络、多播传输路径、构造存储和传输数据的有效编码、建立决策模型等等,-16-,第23讲 平面图的着色与树,树的基本概念,连通无回路的无向图称为无向树，简称为树(tree)。 树中的悬挂点又称为树叶(leave)， 其它结点称为分支点(branched node)。 单一孤立结点称为空树(null tree)。 诸连通分支均为树的图称为森林(forest)，树也是森林。,-17-,第23讲 平面图的着色与树,树的性质,树和森林都是可2-着色的，从而都是二分图。 树和森林都
7、是平面图，其面数为1。 设图T为一树，其顶点数、边数分别是n, m, 那么nm=1或m=n1。 任何树都至少有两片叶,设T中至多只有一个顶点是叶，那么 2m = (vi) 2(n 1)+1 = 2n 1 m n 1/2 n 1,-18-,第23讲 平面图的着色与树,树的等价定义,(0) T连通无回路。 (1) T无回路且m = n1。 (2) T连通且m = n1。 (3) T无回路，但任意添加边时，T中产生唯一一条回路。 (4) T连通，但删去任一边时便不再连通。 (5) 任意两个不同顶点之间有且仅有一条通路。,-19-,第23讲 平面图的着色与树,树的等价定义,(1)T无回路且m = n1
8、。 (2)T连通且m = n1。,(1)(2) 设T无回路，m = n 1 ，欲证T连通。反设T有k个连通分支(k2)，T1， ，Tk，它们的顶点数分别是n1, , nk,边数分别是m1, , mk，显然 mi = ni 1 (i=1,2,k) 于是 矛盾。因此T连通。,-20-,第23讲 平面图的着色与树,树的等价定义,(2)T连通且m = n1。 (3)T无回路，但任意添加边时，T中产生唯一一条回路。,(2)(3) 设T连通且m=n1 。先证T无回路，为此对n归纳。 n = 1时显然T无回路，因这时m=n1=0。 设顶点数为n1 的满足题设的图无回路，顶点数为n的图T至少有两个悬挂点。去掉
9、一悬挂点构成T。显然T仍连通，且m=m1=n2 = n1 ，因此由归纳假设T无回路。在T上加回所删去的悬挂点得T，故T亦无回路。 再证(3)的第二部分。设在T的顶点vi, vj间添加边e。由于T连通，故原本有vi到vj的通路，此通路连同边e构成Te的一条回路。若此回路不唯一，那么去掉边e后T仍有回路，与以上证明冲突。,-21-,第23讲 平面图的着色与树,树的等价定义,(0)T连通无回路。 (1)T无回路且m = n1。 (2)T连通且m = n1。 (3)T无回路，但任意添加边时，T中产生唯一一条回路。 (4)T连通，但删去任一边时便不再连通。 (5)任意两个不同顶点之间有且仅有一条通路。,
10、(5) (0) 设T的任何两个顶点之间有且仅有一条通路，那么T显然连通。T也是无回路的，否则T中有回路上顶点vi ， vj ，使vi到vj有两条通路，与题设矛盾,-22-,第23讲 平面图的着色与树,树的特性,最小的连通图：删去任一条边，图就不再连通； 最大的无回路图：加上任一条边(不是环也不是平行边)，图中会产生回路。,-23-,第23讲 平面图的着色与树,生成树(spanning tree),定义：如果图T为无向图G的生成子图且T为树，则称T为G的生成树 定理9.17(生成树的存在性定理）：任一连通图G都至少有一棵生成树。 上述定理还可加强为“无向图G是连通的当且仅当G具有生成树”,-24
11、-,第23讲 平面图的着色与树,生成树的性质,设G为连通无向图，那么G的任一回路与任一生成树T的关于G的补GT (即在G中删去T中的边所得的图)，至少有一条公共边。 对任一回路和任一生成树，回路中至少有一条边不在生成树中,证明：设C为G的一回路，它和G的生成树T关于G的补G T 无公共边，那么C是T的子图，从而树T中有回路，矛盾。,-25-,第23讲 平面图的着色与树,生成树的性质,设G为连通无向图，那么G的任一边割集与任一生成树至少有一条公共边。 对任一边割集和任一生成树，边割集不能全在生成树外；,证明：设S为G的割集，但它和G的生成树T无公共边。那么，删去G中所有S的边后所得的图仍以T为子
12、图，从而仍连通，这与S为割集矛盾,-26-,第23讲 平面图的着色与树,枝割集,G的生成树T中的边称为树枝； 对每一树枝t，T t分为两个连通分支T1，T2，那么两端点分别在T1，T2中的边组成G的一个割集，称为枝t割集。 枝t割集和生成树只有一个公共边，就是t （n, m）图G的任一生成树T恒有n 1条枝，从而有n 1个枝t割集，称为枝割集系,枝e1割集：e1, e4, e8； 枝e2割集：e2, e9； 枝e3割集：e3, e4, e8, e9； 枝e5割集：e5, e7, e8； 枝e6割集：e6, e7 ,-27-,第23讲 平面图的着色与树,弦回路,生成树T中的边称为树枝；G T的边
13、称为关于生成树T的弦。每一条弦e与T中的通路构成一回路，称为弦e回路。 图G（n, m）的任一生成树T恒有n 1条枝，从而有m n + 1个弦e回路，称为弦回路系。,弦e4回路：(e4, e1, e3)； 弦e7回路：(e7, e5, e6)； 弦e8回路：(e8, e3, e1, e5)； 弦e9回路：(e9, e2, e3)；,-28-,第23讲 平面图的着色与树,边割集和回路的关系,定理：在连通无向图G中，任一边割集与任一回路均有偶数条公共边。,证明：设C为G的任一回路，S为G的任一割集，从G中删除S的所有边后得到两个互不连通的子图G1，G2。 若回路C上的所有顶点都在G1(或G2)中，
14、那么，C和S无公共边，定理得证。若回路C的一部分顶点在G1中，另一部分在G2中，那么C必定经过S中偶数条边，故C与S有偶数条公共边。,-29-,第23讲 平面图的着色与树,枝割集与弦回路的关系,设G为一连通无向图，T是G的生成树， S = e1, e2, e3 , ek为枝e1割集 e1必且仅在弦e2回路、弦e3回路、弦ek回路中。,枝e1割集：e1, e4, e8； 枝e2割集：e2, e9； 枝e3割集：e3, e4, e8, e9； 枝e5割集：e5, e7, e8； 枝e6割集：e6, e7 ,弦e4回路：(e4, e1, e3)； 弦e7回路：(e7, e5, e6)； 弦e8回路：
15、(e8, e3, e1, e5)； 弦e9回路：(e9, e2, e3)；,-30-,第23讲 平面图的着色与树,枝割集与弦回路的关系,设G为一连通无向图，T是G的生成树， S = e1, e2, e3 , ek为枝e1割集 e1必且仅在弦e2回路、弦e3回路、弦ek回路中。,e1,S枝e1割集：e1, e4, e8； C弦e4回路：e4, e1, e3；,证明：设C为任一弦ei回路(i = 2，3 , k)，例如C为弦e4回路，则e4在S与C中。要证e1也在S和C中。 由定理9.20，C与S有偶数条公共边。 由于S中只有e1为树枝，其余各边均为弦；而C 中只有e4为弦，其它各边均为树枝，所以
16、只有e1在S与C 中。 即S与C 恰有两条公共边e1和e4 ，因此e1在弦e4-回路中。 证明过程对一切ei (i = 2，3,k)均成立，因此定理的前半部分得证,-31-,第23讲 平面图的着色与树,枝割集与弦回路的关系,设G为一连通无向图，T是G的生成树， S = e1, e2, e3 , ek为枝e1割集 e1必且仅在弦e2回路、弦e3回路、弦ek回路中。,证定理后半部分：设C为弦e回路，ee2, e3,ek。C中只有e为弦，S中e2, e3,ek为弦，故eS。 由于S中只有e1为树枝，其余各边均为弦；而C中只有e为弦，其它各边均为树枝，eS，所以若e1在C中，那么C与S只可能有一条公共边e1，此与定理9.20矛盾。 因此，
