离散数学平面图课件

1、离 散 数 学离 散 数 学12图的基本概念路与回路4欧拉图与汉密尔顿图平面图6对偶图与着色 图论 3图的矩阵表示57树与生成树12图的基本概念路与回路4欧拉图与汉密尔顿图平面图6对偶图与3定义1：设G=是一个无向图，如果能把G的所有结点和边画在平面上，且使得任何两条边除了端点外没有其他的交点，就称G是一个平面图。 平面图基本概念 平面图平面图非平面图(1)(2)(3)3定义1：设G=是一个无向图，如果能把G的所有结点4定义21) 设G是一连通平面图，由图中的边所包围的区域，在区域内既不包含图的结点，也不包含图的边，这样的区域称为G的一个面，包围该面的边所构成的回路称为这个面的边界。2) 面边

2、界的回路长度称作该面的次数，记作deg(r) 。3) 若面的面积有限称为有限面，否则称为无限面。每个平面图有一个无限面。例如：右图每个面的次数为： 平面图基本概念 ABCDEFr1r2r3r4r5Deg(r1)=3 Deg(r2)=3Deg(r3)=5 Deg(r4)=4Deg(r5)=3e1e3e24定义2 平面图基本概念 ABCDEFr1r2r3r4r5D5定理1：一个有限平面图，面的次数之和等于边数的2倍， 即：deg(r)=2|E| 平面图基本性质 证明：eE,e只能以下面两种情况存在：1.e作为两个面的公共边界2.e作为一个面的边界以上两种情况中，e都被重复计算两次，所以公式成立。A

3、BCDEFr1r2r3r4r55定理1：一个有限平面图，面的次数之和等于边数的2倍， 平面定理2(欧拉定理)：连通平面图G，共有v个结点e条边和r个面，则欧拉公式：v-e+r=2成立。证明：1)若G为平凡图，则v=1,e=0,r=1，v-e+r=2成立。2)若G为一条边，则具有以下两种情况。v=3,e=2,r=1,v-e+r=23)若G为两条边，则有下述几种情况：v=2,e=1,r=1，v-e+r=2v=1,e=1,r=2，v-e+r=2v=2,e=2,r=2，v-e+r=2v=2,e=2,r=2v-e+r=2v=1,e=2,r=3,v-e+r=2定理2(欧拉定理)：连通平面图G，共有v个结点

4、e条边和r个面4)设G为k条边时公式成立，即vk-ek+rk=2成立，则证明在G为k+1条边时是否成立：而：G为k条边，再添加一条边，只有下述两种情况：面数不变点树加1边数加1(Vk+1)-(ek+1)+rk=2成立点数不变面数加1边数加1(Vk)-(ek+1)+(rk+1)=2成立通过上述归纳法证明欧拉公式v-e+r=2成立。4)设G为k条边时公式成立，即vk-ek+rk=2成立，则证8例1：证明K3,3不是平面图 证：假设K3,3是平面图，则满足欧拉公式 v e + r = 2 即：6-9+r=2，解得r=5又因为任取K3,3中三个结点，至少有两个点不邻接，所以不能组成一个面，即K3,3中

5、任何 一个面至少由四条边围成，即：所有面 的次数之和deg(r) =4r=20又由定理1知：deg(r)=2|E|=18即18=20矛盾。所以K3,3不是平面图。 平面图基本性质 不论怎么画，总有交叉点8例1：证明K3,3不是平面图 证：假设K3,3是平面定理3：设G是一个有v个结点e条边的连通简单平面图，若v3,则：e=3v-6。证明：设G的面数为r,当v=3,e=2时，满足e=3v-6，即2=3*3-6=3若v3,e3时，连通简单G中每一个面的次数deg(ri)3G的总次数deg(ri)=2|E|3r,即2e3r,代入欧拉公式可得：e=3v-6。定理3：设G是一个有v个结点e条边的连通简单

6、平面图，若v3例题：证明k5图不是平面图。设G是一个有v个结点e条边的连通简单平面图，若v3,则：e=3v-6。等价于:若不满足e=3v-6，则G不是连通平面图。K5图中,v=5,e=10,10 3*v-6=35-6=9K5为非平面图 平面图基本性质 但定理的条件只是必要条件。如K3,3中v= 6,e =9, e=5，所以deg(r)=5r=35又因为deg(r)=2e=30，而30=35矛盾所以该图不是平面图 平面图基本性质 abcidefghj14例4：证明彼得森图是非平面图证：（1）反证法 平面图基本15（2）利用定理4:一个图是平面图，当且仅当它不包含与K33或K5在2度结点内同构的子

7、图。 平面图基本性质 bcjdehabcidefghjG的子图G删除了egfabcidefghjG与G在2度结点内同构abcidehjG”K33彼得森图不是平面图，因为该图G含有1个子图G，与K33在2度结点内同构。即G与K33具有相同的平面性。15（2）利用定理4:一个图是平面图，当且仅当它不包含与K316小结：判定给定图是否平面图是否满足e=3)，若不满足，则不是平面图；若满足e=3v-6，有可能是，也可能不是平面图（K33），再判断是否有2度顶点内同构于K3,3或K5的子图。 若有则是非平面图，否则是平面图。 平面图基本性质 16小结：判定给定图是否平面图是否满足e=12图的基本概念路与

8、回路4欧拉图与汉密尔顿图平面图6对偶图与着色 图论 3图的矩阵表示57树与生成树12图的基本概念路与回路4欧拉图与汉密尔顿图平面图6对偶图与18 图形着色问题是与平面图密切相关的图论的应用问题，该问题最早起源于地图的着色：一个地图中相邻国家着以不同颜色，那么最小需要多少种颜色？（四色问题）为了叙述图形的着色的有关定理，下面先介绍对偶图的概念，然后再学习图的着色。 对偶图与着色18 图形着色问题是与平面图密切相关的图论的应用问定义1：给定平面图G=,它具有面F1,F2,Fn。若存在图G*=满足下列条件：1.对于图G的每一个面Fi,内部有且仅有一个点vi* V*；2.对于图G的面Fi,Fj的公共边

9、界ek,有且仅有一条边ek*E* 使ek*=(vi*,vj*),且ek与ek*相交；3.当且仅当ek只是一个面Fi的边界时，vi*存在一个环ek*和ek相交。则图G*为G的对偶图。v1*v2*v3*e2* e1*e2e1 F1 F2F3 对偶图与着色定义1：给定平面图G=,它具有面F1,F2,Fn20定义2：如果图G的对偶图G*同构于G，则称G是自对偶图。例如： 从对偶图的概念我们可以看到，对于地图的着色问题可以归纳为对平面图的顶点的着色问题。 因此，四色问题可以归结为：要证明对于任何一个平面图，一定可以用四种颜色对它的顶点进行着色，使得相邻的顶点都有不同的颜色。 对偶图与着色20定义2：如果

10、图G的对偶图G*同构于G，则称G是自对偶图。21定义3：1）图G的正常着色（着色）是指对G的每个结点都指定一种颜色，使得没有两个邻接的结点有同一种颜色。2）如果图G在着色时，用了n种颜色，则称G为n-色的。3）对图G着色时，需要的最少颜色数称作G的着色数，记作x(G)。 图的正常着色21定义3： 图的正常着色221）将图G中的结点按度数的递减次序排列（可能不唯一）。2）用第一种颜色对第一个结点着色，并按顺序对与前面着色点 不邻接的每一点着上同样的颜色；3）用第二种颜色对尚未着色的点重复2），用第三种颜色继续， ，直到所有点全部着上色为止。 韦尔奇.鲍威尔（W.P）着色法A1 A2 A3A7 A

11、8A4 A5 A6度数递减顺序排序：A5，A3，A7，A1，A2，A4，A6，A8221）将图G中的结点按度数的递减次序排列（可能不唯一）。 23定理1：对于n个结点的完全图Kn，有x(Kn)=n。证明：因为完全图中， 每个结点与其他结点都邻接，所以n个结点的着色数不能小于n，又n个结点的着色数最多是n，故x(Kn)=n证明：反证法。设G=，|V|=v,|E|=e，若G中任意结点vi都有d(vi)=6;则d(vi)=6v; 又由： d(vi)=2e 得:2e=6v, 即e=3v3v-6，故G不是平面图，与前提矛盾。所以v=3时，必有一顶点u,使得d(u)=5定理2：设G为一个至少有3个结点的连

12、通平面图，则G中必有一个结点n，使得d(u)=5。 对偶图与着色23定理1：对于n个结点的完全图Kn，有x(Kn)=n。证明24定理3：任意平面图G最多是5色的。证明：1）若v=1,2,3,4,5，显然成立2）设v=k时成立，考察v=k+1时,由定理2可知，必存在结点u，使d(u)=5，在图G中删去u，得到G的子图：G-u，由归纳假设知， G-u具有k个结点，此时定理成立。现将u及其关联边加入到G-u中，得到原图G：(1)若d(u)=4，则与u邻接的结点不超过4个，故必可对u正常着色，得到一个最多5色的图G；(2)若deg(u)=5，设与u邻接的结点按逆时针顺序排列为v1,v2,v3,v4,v

13、5，它们分别着不同的颜色C1,C2,C3,C4,C5(如果它们着了4颜色，则直接将u着第5种颜色。不需要进行下面的分析)设H1,3为G-u中所有着C1,C3的结点集，F2,4为着C2,C4的结点集。 对偶图与着色 u v2(C2) (C3)v3 (C4) v4 v5(C5) v1(C1) u v2(C2) (C3)v3 (C4) v4 v5(C5) v1(C1) u (C5) v2(C2) (C3)v3 (C4) v4 v1(C1)24定理3：任意平面图G最多是5色的。证明：1）若v=1,2a)若v1与v3属于结点集H1,3所导出子图的两个不同的连通分支，将v1所在分图中的C1,C3两种颜色对

14、调，并不影响G-u的正常着色，然后在u上着C1色，即得到图G是5色的。 u v2 v3 v4 v5 v1b)若v1与v3属于结点集H所导出子图的同一个连通分支，从v1到v3必有一条路P，P上所有结点都着C1或C3色，且P与边(v3,u)(u,v1)一起构成了一条回路L，则L包围了v2或v4，但不能同时包围二者，故v2和v4分别属于结集F所导出子图的两个不同连通分支，因此将v2所在分支中C2,C4两种颜色对调，并不影响G-u的正常着色，那样v2与v4都着了C4色， 然后在u上着C2色，即得到图G是5色的。 u v2 v3 v4 v5 v1a)若v1与v3属于结点集H1,3所导出子图的两个不同的连

15、例题：设G是一个简单图，若G的结点表示期末考试课程，边表示关联的两结点对应的科目不能同一时间考试。那么，G的一个适当的着色的意义是什么？最小着色数的意义是什么？分析：图的结点表示考试课程；相邻接的两个结点着不同颜色，表示不能同时考试。即：不邻接的课程可以同一时间考试。所以，G的一个着色表示一张考试安排表。表示如下意义：同一种颜色的结点表示可以在同一时间考试的对应课程；最小的着色数表示安排考试时间的最少次数。26 对偶图与着色计算机组成原理 计算机网络 程序设计数据库原理 软件工程离散数学 编译原理 操作系统例题：设G是一个简单图，若G的结点表示期末考试课程，边表示关例题：某班级学生共选修9门课

16、程。期末考试时，必须提前将这9门课程先考完，每天每人只在下午考一门课程，问：如何确定考完这9门选修课的最少天数？解：采用无向图G=表示上述选课及考试关系。1、构造G:V=v1,v2,v3,v9,vi表示课程。S(i)=s | s是该年级学生且s选修了课程viE= (vi,vj) | 若S(i) S(j)2、对G进行着色。(G)是所需要的最少天数。27 对偶图与着色例题：某班级学生共选修9门课程。期末考试时，必须提前将这9门28 对偶图与着色V1 V2V3V4V6 V5V8V7V9(G)=3所以，按照图中所示的选课情况下，最少需要3天考完这9门选修课。例题：某班级学生共选修9门课程。期末考试时，

17、必须提前将这9门课程先考完，每天每人只在下午考一门课程，问：如何确定考完这9门选修课的最少天数？28 对偶图与着色V1 29 对偶图与着色例题：将无向完全图K6的边随意涂上红色或绿色，证明：无论如何涂色，总存在红色的K3或者绿色的K3。分析：K6的结点为V=v1, v2, v3, v4, v5, v6，每个结点vi关联5条边。对应的邻接点为v2, v3, v4, v5, v6，在涂色过程中，5条边中必然存在3条涂同样颜色的边，设都为红色，3条边对应的结点为：v2,v3, v4，则另外两条边颜色为绿色（也可以红或者绿）。如果v2, v3, v4构成的K3中的1条边再有1条红色边，则必然存在红色K3。如(v2,v4)涂红色，则v1,v2,v4为红色K3，若(v2,v3)涂红色，则v1,v2,v3为红色K3，若(v3,v4)涂红色，则v1,v3,v4为红色K3。如果v2, v3, v4构成的K3中没有红色边，则其本身就是绿色K3。v2v3v4v129 对偶图与着色例题：将无向完全图K6的边随意涂上红色或绿30 对偶图与着色例题：证明