离散数学 第2版 教学课件 作者 王元元 离散第23讲 平面图的着色与树.ppt

《离散数学 第2版 教学课件 作者 王元元 离散第23讲 平面图的着色与树.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机专业基础课程授课人：王元元单位：计算机理论教研室理工大学指挥自动化学院PowerPointTemplate_Sub1二分图2平面图3树2第23讲平面图的着色与树平面图的着色与树《离散数学》第23讲Page140to147着色问题图的点着色平面图的面着色4第23讲平面图的着色与树平面图的面着色问题四色难题：是否任何平面图均可以4着色？容易证明：任何平面图均可以5着色。为便于研究，先把面着色转化为点着色5第23讲平面图的着色与树对偶图对连通平面图G实施下列步骤所得到的图G*称为G的对偶图(dua

2、lofgraph)：(1)在G的每一个面ri的内部作一个G*的顶点vi*。(2)若G中面ri与rj有公共边界，那么过边界的每一边ek作关联vi*与vj*的一条边ek*。ek*与G*的其它边不相交。(3)当ek为面ri的边界而非ri与其它面的公共边界时，作vi*的一条环与ek相交(且仅交于一处)。所作的环不与G*的边相交。6第23讲平面图的着色与树对偶图例7第23讲平面图的着色与树对偶图例同构图的对偶图可能不同构左边的对偶图有5度顶点,右边的对偶图却没有平面图的对偶图仍为平面图8第23讲平面图的着色

3、与树可k着色定义:无环图G称为可k-着色的，如果可用k种颜色给G的所有顶点着色，使每个顶点着一种颜色，而同一边的两个端点着不同颜色。若任意平面图可k-着色，则任意平面图的面可用k种颜色之一着色，使得相邻的面着不同颜色9第23讲平面图的着色与树5色定理定理:任何平面图都是可5-着色的。证：连通分支、环和平行边与着色问题无关，因此可只讨论平面连通简单图。设G为任一平面连通简单图，顶点个数为n。对n归纳。当n≤5时命题显然成立。设n-1个顶点的平面图都是可5-着色的。考虑n个顶点的图G。10第23讲平面

4、图的着色与树5色定理由定理9.9，G至少有一个顶点的度不大于5，设v0为这样一个顶点。设d(v0)<5，那么只要取它相邻顶点所着颜色（至多4种)之外的一种颜色给v0着色，便可完成对G的5-着色。设d(v0)=5，如果证明与v0相邻的顶点可用少于五种颜色着色，便可完成对G的5-着色。v0v2v3v4v5v111第23讲平面图的着色与树5色定理为叙述简明，令RY表示G-v0中所有着红、黄顶点的集合，BW表示G-v0中所有着黑、白顶点的集合。考虑RY生成的G的子图G(RY)。若v1，v3分属于G(RY)

5、的两个不同的连通分支，那么只要将v1所在分支的红、黄顶点的着色作一对换(从而v1着黄色)，便可给v0着红色以完成对G的5-着色。v0v2v3v4v5v1v2v3v4v5v112第23讲平面图的着色与树5色定理若v1和v3同属于一个G(RY)的连通分支，那么从v1到v3必有一条通路，其各顶点被红、黄两色相间着色。这条通路连同v0便构成回路C：v0,v1,…,v3,v0,C把BW分成两部分，一部分在回路C之外，一部分在C之内。v0v2v3v4v5v1回路C13第23讲平面图的着色与树5色定理于是，BW

6、生成的G的子图也被分成了两个互不连通的部分，一部分在C外，一部分在C内，这就使v2，v4处于BW生成的G的子图的两个不同连通分支，同上将v2所在分支作颜色对换，以便给v0着上白色，完成对G的5-着色。归纳完成，定理得证。v0v2v3v4v5v1回路C14第23讲平面图的着色与树引言树的术语起源于植物学和族谱学树是不包含回路的连通图今天树在计算机科学、化学、地质学、植物学、心理学等多种学科利用来构造各种各样的问题模型树在计算机科学中非常有用，例如用最便宜的线路构造计算机网络、多播传输路径、构造存储和

7、传输数据的有效编码、建立决策模型等等15第23讲平面图的着色与树树的基本概念连通无回路的无向图称为无向树，简称为树(tree)。树中的悬挂点又称为树叶(leave)，其它结点称为分支点(branchednode)。单一孤立结点称为空树(nulltree)。诸连通分支均为树的图称为森林(forest)，树也是森林。16第23讲平面图的着色与树树的性质树和森林都是可2-着色的，从而都是二分图。树和森林都是平面图，其面数为1。设图T为一树，其顶点数、边数分别是n,m,那么n–m=1或m=n–1。任何树都

8、至少有两片叶设T中至多只有一个顶点是叶，那么2m=(vi)≥2(n–1)+1=2n–1m≥n–1/2>n–117第23讲平面图的着色与树树的等价定义(0)T连通无回路。(1)T无回路且m=n–1。(2)T连通且m=n–1。(3)T无回路，但任意添加边时，T中产生唯一一条回路。(4)T连通，但删去任一边时便不再连通。(5)任意两个不同顶点之间有且仅有一条通路。18第23讲平面图的着色与树树的等价定义(1)T无回路且m=n–1。(2)T连通且m=n–1。(1)(2)设T无回路，m=n