离散生期末题集合论与图论gra

1、第三章连通度和匹配 基本内容 顶点连通度和边连通度 门格尔定理 匹配、霍尔定理3.3 霍尔定理（相异性条件）定理1 设G=(V1V2，E)是一个偶图，|V1|V2|。G中存在从V1到V2的完全匹配充分必要条件是V1中任意k个顶点(k=1,2, |V1|)至少与V2中的k个顶点相连接。该条件称为相异性条件例4 现有4名教师：张、王、李、赵，要求他们去教4门课程：数学、物理、电工和计算机科学。已知张能教数学和计算机科学；王能教物理和电工；李能教数学、物理和电工；赵只能教电工。如何安排才能使4位教师都能教课，并且每门课都有人教？共有几种方案？ 用相异性条件判断一个偶图是否存在完全匹配常常很不方便，下

2、面的充分条件比较便于实际应用。定理2 设G=(V1V2，E)是一个偶图，|V1|V2|。G中存在从V1到V2的完全匹配的充分条件是存在正整数t，使得V1中每个顶点的度大于等于t，V2中每个顶点的度小于等于t。该条件称为t条件。 定理3 从t条件可以推出相异性条件。 证: 对于V1中的任意的v1，v2，vr，与它们关联的顶点个数m，从v1，v2，vr到V2的边数为e。根据t条件：v1中的每个顶点至少和t个顶点相关联，则ert。V2中的每个顶点至多和V1中的t个顶点相关联，则emt。故有，mtrt，即mt，结论成立。注意：定理3中反过来不能推出t条件。推论1 任何r-正则偶图G(V1V2，E)必有

3、一个完美匹配，其中r1。例某年级共开设7门课程，由7位教师承担。已知每位教师都能担任其中的3门课程。他们将自己能担任的课程报到教务处后，教务处人员发现每门课都恰好有3位教师能担任。问教务处人员能否安排这7位教师每人担任1门课，并且每门课都有人承担。第四章 平面图和图的着色本章内容：平面图及其欧拉公式 非哈密顿平面图（不要求） 和图的着色 库拉托斯基定理、对偶图 图的顶点着色 图的边着色（不要求）第一节 平面图及其欧拉公式内容：背景、平面图、面、偶拉公式、推论1.1 背景 在图论的理论研究和实际应用中，需要考虑一个图能否画在平面上使得它的边仅在端点相交的问题。若一个图能画在平面上使得它的边仅可能

4、在端点相交，则这个图称为平面图。于是在实际问题中，判断一个图是否是一个平面图是非常重要的。 例1在印刷电路的布线中，感兴趣的是知道一个特定的电网络是否可以嵌入平面上。 例2 如图所示（书上）H1，H2，H3表示三座楼房，W，G和E分别表示自来水厂、煤气管道和地下电缆。为了安全起见，要求这些管道不能直接接触交叉。书上图显然不是个好的设计方案。但工程设计要求能达到吗？ 这就提出了这个图是否为平面图的问题。 例3 地图的着色（四色问题） 一个图可以用它的图解来表示，把一个图的图解就看成是这个图本身。但对一个给定的图，其图解的画法并不唯一，即从几何图形上看可以很不一样。一个图的图解不仅可以画在一个平面

5、上，还可以画在球面上或任一给定的曲面上。 下面将考虑这样一类图，其图解画在一个平面上时，有一种画法能使其边仅可能在顶点相交，而在边的内部不相交，这种图称为平面图。1.2 平面图、面定义1 若G的图解已画在平(曲)面S上，而且任何两条边均不相交(除可能在端点相交外)，则图G称为嵌入平(曲)面S内。已嵌入平面S内的图称为平面图。若一个图可以嵌入平面，则称此图是可平面的 说明：可平面图：能画在平面上 ，但还没有画；平面图：已经画在平面上了。以后这两个概念不加区分。例如：图K4是可平面的，因为K4的一种平面嵌入法 ；图K5没有平面嵌入法； K5画不出来，并不等于就是非平面图，必须证明。实际上，K5是典

6、型的不可平面图，还有K3，3。定义2 平面图G把平面分成了若干个区域，这些区域都是连通的，称之为G的面，其中无界的那个连通区域称为G的外部面，其余的单连通区域称为G的内部面。说明：(1)平面图的每个内部面都是G的某个回路围成的单连通区域； (2)一个平面图可以没有内部面，但必有外部面，而且外部面唯一；例如：树作为平面图就没有内部面。(3)图K4所示的图有4个面，f4是外部面，f1，f2，f3都是内部面。 1.3 欧拉公式定理1(欧拉公式)设G=(p，q)是平面连通图，有f个面，则p-q+f=2。证：用数学归纳法证明，施归纳于面f的个数：注意：定理中的连通性是重要的。若G不连通，则定理不成立。但

7、却有下面的结论。推论：设G=(p，q)是一个具有f个面、k个分支的平面图，则p-q+f=k+11.4 欧拉公式的推论这些推论都是平面图的必要条件，不是充分条件。推论1 若G=(p，q)是平面连通图且每个面都是由长为n的回路围成的，则q=n(p-2)/(n-2) 一个最大可平面图是一个可平面图，对此可平面图中不能再加入边而不破坏可平面性。推论2 设G=(p，q)是一个最大可平面图，则G的每个面都是三角形，而且q=3p-6。推论3 若G=(p，q)是一个可平面连通图，而且G的每个面都是一个长为4的回路围成的，则q=2p-4推论4 若G=(p，q)是一个连通的平面图，p3，则q3p6。 若G是2连通

8、的且没有三角形，则q2p4。推论5 证明K5和K3，3都不是可平面图。 推论6 每个平面图G的顶点度的最小值不超过5，即(G)5 。 第二节 库拉托斯基定理、对偶图 内容：细分图、收缩图、二度结点内的同构、初等收缩、对偶替已经证明：(1) K5和K3，3不是平面图，而K5和K3，3的每个真子图显然都是平面图；（ （2）显然，平面图的每个子图是平面图。因此，平面图中不含子图K5和K3，3。2.1 细分图定义1 设G=(V，E)是一个图，则（1）若x=uv是图G一条边，又w不是G的顶点，则当用uw和wv代替边x时，就称边x被细分。（2）若G的某些条边被细分，产生的图称为G的细分图，也称为二度顶点内

9、细分图。定义2 若两个图可以从一个图通过一系列的边细分得到，这两个图称为同胚的(homeomorphism)，也称为二度顶点内同胚。例如：两个回路是同胚的。于是，一个图若含有同胚于K5或K3，3的子图，它就不是平面图。库拉托斯基指出，这个必要条件也是充分的。定理1(库拉托斯基，1930)一个图是可平面的充分必要条件是它没有同胚于K5或K3，3的子图。 平面图还存在着若干其他特征。 为了描述另外的特征，引入下面定义。2.2 收缩图定义3 设G=(V，E)是一个图，则(1)若uw和wv是图G的两条边且deg(w)=2，用一条边uv代替uw和wv时，则称uw和wv被缩减。(2)若G的某些条边被缩减，

10、产生的图称为G的缩减图，也称二度顶点内缩减图。1937年，瓦格纳(K.W.agner)证明了：定理2 一个图是可平面的当且仅当它没有一个可以收缩到K5或K3，3的子图。2.3 二度结点内的同构定义4 给定两个图G1和G2，若它们是同构的，或者通过反复插入或除去度为2的顶点后，使得G1和G2同构，则称这两个图是2度顶点内同构。定理3 一个图是可平面图充分必要条件是图G不包含与K5或K3，3在二度顶点内同构的子图。2.4 初等收缩定义5 一个图G的一个初等收缩由等同两个邻接的顶点u和v得到，即从G中去掉u和v，然后再加上一个新的顶点w，使得w邻接于所有邻接于u和v的顶点。一个图G可收缩到图H，若H

11、可以从G经一系列的初等收缩得到。2.5 对偶图定义6 设G=(V，E)是一个平面图，由G按如下方法构造一个图G*，G*称为G的对偶图： (1)对G的每个面f对应地有G*的一个顶点f*； (2)对G的每条边e对应地有G*的一条边e*：G*的两个顶点f*与g*由边e*联结，当且仅当G中与顶点f*与g*对应的面f与g有公共边e，若某条边x仅在一个面中出现而不是两个面的公共边，则在G*中这个面对应的顶点有一个环。 (3)当平面G已画在平面上时，G的对偶图如下构造：在G的每个面内放一个顶点，若两个面有一条公共边x，则用一条仅仅穿过边x的边x*来联相应的顶点。这样总产生一个平面伪图。在图中，G的边是实线，

12、顶点是小圆圈，而G的对偶图G*的边用虚线画出，顶点用实心黑点画出。说明：(1)显然，G*有一个环当且仅当G有一条桥；而G*有多重边当且仅当G的两个面至少有两条公共边。(2) 若G是一个有p个顶点和q条边及f个面的平面连通图，则G的对偶图G*也是一个平面图；若G不是平面连通图， G的对偶图G*也是一个平面图。(3)若G*是连通平面图：顶点数、边数和面数分别记为p*，q*和f*，则 p*=f，q*=q，f*=p。 若G不是连通平面图：则 p*=f ，q*=q，f*=p-k+1。 (4) 由于一个抽象的可平面图嵌入平面上时，可能有不只一种嵌入方法，因而产生了不只一个对偶图。尽管G的不同嵌入法得到的平

13、面图是同构的，但不同嵌入产生的平面图的对偶图可能不同构。例如（书上）图(a)和(b)是同一个可平面图G的两种不同方法嵌入平面，G中的顶点和边分别用小圆圈和实圆圈画出，而它们的对偶图G*分别在同一图上用黑点和虚线画出顶点和边。由于(a)中有一面是五条边围成的，而(b)没有这样的面，所以(a)产生的对偶图中有一个顶点度为5，而(b)产生的对偶图中没有度为5的顶点，所以这两个对偶图不同构。 定义7 若一个平面图与它的对偶图同构，则称这个平面图是自对偶的。 2.6 例题：例1 判断下面命题的对错，并说明理由。任何平面图G的对偶图G*的对偶图G*与G同构。分析：这个题目应该仔细钻研，结论也值得记忆。证：

14、非连通的平面图G的对偶图G*的对偶图G*与G不同构因为G不连通，而G*连通和G*连通，所以非连通的平面图G的对偶图G*的对偶图G*与G不同构例7 把平面分成n个区域，每两个区域都相邻，问n最大为多少？证：在每个区域放一个顶点，当两区域相邻时，就在相邻的两个顶点间连一条边，如此构造了一个平面图且是完全平面图，而最大的完全平面图为K，所以n最大为4。例给出平面图G的对偶图G*为欧拉图的一个充分必要条件。并证明之。分析：当且仅当G中每个面均由偶数条边围成，因为平面图G的每个面对应G*的每个顶点，而G*为欧拉图的充要条件是G*每个顶点的度数为偶数，围成G每个面的边数与对应的G*中的顶点的度数相等，所以

15、一个平面图G的对偶图G*是欧拉图.证：当且仅当G中每个面均由偶数条边围成，一个平面图G的对偶图G*是欧拉图。显然G*是连通图。设v*为G*中任意一顶点，v*处于G的面R中，因为R由偶数条边围成，所以v*的度数为偶数。由于v*的任意性可知。G*为欧拉图。反之也成立。例设G为连通的简单平面图，顶点数为n，面数为r，证明：若n3，则r2n-4；(2)若G中顶点最小的度为4，则G中至少有6个顶点的度数小于等于5。 证:(1)根据欧拉公式n-m+r=2，其中n，m，r分别是G的顶点数、边数和G的面数。得r=m+2-n，而对于顶点数n3的连通的简单的平面图G，有m3n-6。所以，r2n-4； (2) 假设

16、G中至多含有5个顶点的度数小于等于5。又因为(G)=4，所以由degvim，得m=degvi54+6(n-5)，所以m3n-5。从而 3n-53n-6，矛盾；所以，G中至少有6个顶点的度数小于等于5。例 设无向图G是n（n2）个顶点的极大平面图，证明：G的对偶图G*的边连通度(G)2，并且G*是3-正则图。分析：要证明图G的对偶图G*的边连通度(G)2，也就是说任意删去G*的一条边，G*还是连通的。任意图G的对偶图G*都是连通的，并且对于任意顶点数大于等于3的极大平面图所有面的边数均为3。所以图G*是3-正则图。 证：因为无向图G是n2个顶点的极大平面图，所以图G的所有面的边数均为。根据平面图

17、的对偶图定义，对偶图G*的每个顶点的度数degv*=3，所以G*是-度正则图。 要证明图G的对偶图G*的边连通度（G）2，等价于证明：任意删去G*的一条边e*（设图为G1*），G1*还是连通的。设e*的两端点分别为u*，v*。并设图G中u*和v*对应的平面分别为r1，r2。显然r1和r2 是相邻的，因为图G的平面数是有限的，且所有的面都由三条边围成，所以不走e*，从r1一定存在到r2的路。所以G1*也是连通的，即G的对偶图G*的边连通度(G)2。例10设简单平面图G中顶点数n=7,边数m=15,证明G是连通的。证：用反证法。设G不是连通的，则G至少包含两个连通分支G1，G2，Gk，k2。设Gi

18、 的顶点数为ni，边数为mi，i=1，2，k 。 若存在ni=1，则k必为2，因为只有此时G为一个平凡图并上一个K6才能使其边数为15，可是K6不是平面图（它的子图K5已不是平面图），这与G是平面图矛盾，所以ni1。 若存在ni=2，则Gi中至多有一条边（因为G为简单图），另外5个顶点构成K5时边数最多，但充其量为10条边，这与G有15条边矛盾。综上所述，ni3，于是由mi3ni-6 ，i=1，2，k，求和得： m3n-6k （1）将n=7，m=15代入（1）得：1521-6k。即k1，这与k2矛盾。因此G必为连通图。例12 设G是面数r12的简单平面图，G中每个顶点的度数至少为3。(1) 证

19、明G中存在至多由4条边围成的面；(2) 给出一个例子说明，若G中的面数为12，且每个顶点的度至少为3，则(1)的结论不成立。证：(1)不妨设G是连通的，否则可以对它的每个连通分支进行讨论。因而由欧拉公式有: n-m+r=2 （1）又由已知条件知道r12 且 n2m/3 （2）将式（2）的结果代入式（1）得22m/3m+12 得m30 （3）若所有的面均至少由5条边围成，则5r2m 得 r2m/5 (4）将式（2），（4）的结果代入式（1）得22m/3-m+2m/5 得 m30 （5）式（3）与式（5）矛盾，因而必存在至多由4条边围成的面。 (2)十二面体图有12个面，每个顶点均为3度，每个面由5条边围成，并没有4条边围成的面。 例14 证明:当每个顶点的度数大于等于3时，不存在有7条边的简单连通平面图。 证：设G=(n，m)为简单连通平面图，有r个面。 若m=7，由欧拉公式知n+r=m+2=9 (1