离散数学平面图PPT课件

第十七章计划，离散数学，中国地质大学本科，本章解释了本章的主要内容是计划的基本概念、欧拉公式、计划的判断、计划的二重性、本章涉及的所有计划都是指无方向的计划。本章总结了练习，17.1平面的基本概念，1，关于平面的一些基本概念，1，平面的定义17.1G可以嵌入到曲面S中，如果图形g可以在曲面s上绘制，除了在顶点没有交集。G是平面图或平面图，如果G可以嵌入平面的话。g的飞机嵌在号平面图中，没有边界交叉。非平面图是没有平面嵌入的图。(2)是(1)的平面嵌入，(4)是(3)的平面嵌入。一些解释和一些简单的结论一般来说，平面图不一定指平面嵌入，但在讨论一些性质时，它必须指平面嵌入。K5和K3，3不是平面图。定理17.1设定GG.如果g是一个计划，g也是一个计划。让GG准备好。如果G是非平面图，那么G也是非平面图。根据定理，kn (n5)和k3，n (n3)都是非平面图。定理17.2如果G是平面图，通过给G添加平行边或环得到的图仍然是平面图。也就是说，平行边和环不影响图形的平面性。(1)定义定义17.2假设G是一个平面，并且G的面通过G的边缘将G所在的平面分成每个区域。无限表面(外表面)具有无限面积的表面被表示为R0。有限表面(内表面)具有有限面积的表面表示为R2 R1，RK。表面R1的边界围绕由表面R1的所有边组成的环组。面的数量R1边界的长度被记录为deg(R1)。如果G计划有K个平面，它一般可以用R1，R2，Rk，没有必要指出外平面。循环组意味着边界可以是主循环(圆)、简单循环或复杂循环。特别是，还可以组合非连接电路。该计划有4个面，deg (R1)=1，deg (R2)=3，deg (R3)=2，deg (r0)=8。R1、R2、R3、R0、定理17.3平面图G中所有平面的次数之和等于边数m的两倍，也就是说，这个定理中的平面图指的是平面嵌入。E e (g)，当e是面Ri和Rj的公共边界上的边(ij)时，e在计算Ri和Rj的次数时提供1。当E只出现在某个面的边界上时，在计算该面的次数时，E提供2。因此，当计算总次数时，每侧提供2，所以deg(Ri)=2m。证明了简单平面图G中任意两个非相邻顶点之间增加一条新边所得到的图是非平面图，于是G称为极大平面图。注意：如果在一个简单的平面图G中没有相邻的顶点，G显然是一个极大平面图，如K1(平凡图)，K2，K3，K4都是极大平面图。2.最大平面图的主要性质定理17.4最大平面图是连通的，并且在n (n3)阶最大平面图中不能有割点和桥。定理17.5设G是一个N阶(N3)的简单连通平面图，当且仅当G的每个面的次数为3时，G是一个极大平面图。这一部分只证明了必要性，即如果g是n (n3)阶的简单连通平面图，g是最大平面图，则g的每个面的次数是3。由于N3和G是简单的平面图，可以看出G的每个面的次数是3。因为G是一个平面图和一个最大的平面图。可以证明G不能有一个数为3的脸。证明这个想法，假设面的数量Ri deg(Ri)=s4，如图所示。在g中，如果v1和v3不相邻，在Ri中添加边(v1，v3)不会破坏平面性，这与g是最大平面相矛盾。因此v1和v3必须相邻。由于ri，边缘(v1，v3)必须在Ri之外。类似地，v2和v4必须是相邻的，并且边(v2，v4)也必须在Ri之外，因此(v1，v3)和(v2，v4)必须在Ri之外相交，这与g是平面图的说法相矛盾，因此必须有s=3，即没有g的次数大于或等于4的面，因此g的每个面被3条边包围，即每个面的次数是3。只有右边的图表是最大计划。因为这个图中每张脸的次数只有3次。最小非平面图的定义17.4如果从非平面图G中任意删除一条边，得到的图G是平面图，则称G为最小非平面图。从定义中不难看出：K5，K3，3都是极小的非平面图。最小非平面图必须是简单图。例如，以下图形都是最小的非平面图形。对于任何连通平面图g，有n-m r=2，其中n，m和r分别是g的顶点，边和面的数目。证明，当m=0时对边数m(1)作归纳，因为g是连通图，g只能是由孤立顶点组成的平凡图，即n=1，m=0，r=1。这个结论显然是正确的。(2)当m=1时，因为g是连通图，n=2，m=1，r=1，结论显然是正确的。(3)当m=k (k 1)时，它成立。当m=k 1时，g讨论如下。如果G是一棵树，G是非凡的，所以G至少有两片叶子。假设n-m r=2，其中n、m和r分别是G的顶点数、边数和面数，那么n-m r=(n 1)-(m 1) r=n-m r=2如果G不是树，那么G包含一个圆。设边e在G中的一个圆上，设G=G-e，那么G仍然是连通的，m=m-1=k，n=n，r=r-1。假设n-m r=2。因此，n-m r=n-(m 1)-(r 1)=n-m r=2，定理17.7对于具有k(k2)个连通分支的平面图g，具有n-m r=k 1，其中n、m和r分别是g的顶点数、边数和面数。证明了G的连通分支是G1、G2、并且Gi的顶点数、边数和面数分别为ni、mi、ri，I=1，2，分别为K。根据欧拉公式，纳米ri=2，I=1，2，k(17.1)，这很容易知道，因为每个Gi都有一个外表面，而g只有一个外表面，所以g的面的数量，因此，(17.1)的两边同时相加，并且n-m r=k 1是经过排序后得到的。关于欧拉公式的定理17.8将g设置为连通平面图，并且每个面的次数至少为l (L3)，则g的边数和顶点数具有以下关系：从定理17.3(面数之和等于边数的2倍)和欧拉公式，证明解，证明了如果K5是平面图，因为在K5没有环和平行边，每个面的次数大于或等于l3。从定理17.8可以看出，边数10应该满足10(3/(3-2)(5-2)=9。这是一个矛盾，所以K5不是一个平面图。如果K3，3是平面图，因为K3，3中最短圆的长度是l4，那么边数9应该满足9 (4/(4-2) (6-2)=8，这是矛盾的，所以K3，3也不是平面图。定理17.9如果g是具有k(k2)个连通分支的平面图，并且面的数量至少是l(l3)，那么边的数量m和顶点的数量n应该具有以下关系：定理17.10如果g是具有n (n3)阶的m个边的简单平面图，那么m3n6.设g有k (k1)个连通分支。如果g是树或森林，当n3，m=n-k3n6为真。如果g既不是树也不是森林，那么g必须包含一个圆，因为g是一个简单的图，每个面至少由l (L3)条边限定，并且在l=3时达到最大值。从定理17.9可以证明，在定理17.11中，g被设置为n (n3)阶的m个边的最大平面，然后m=3n6。证明了因为最大平面图是连通图，r=2 m-n (17.4)由欧拉公式得到，并且因为g是最大平面图，从定理17.7的必要性可知g的每个面的次数是3，所以：(17.4)被代入(17.5)，并且m=3n-6是排序后得到的。一个重要的定理定理17.12如果G是一个简单的平面图，那么G的最小度数是(G) 5。如果顺序为N6，结论显然成立。如果是N7阶，就用反证法。假设(g) 6，由握手定理已知，证明，因此m3n，这与定理17.10相矛盾。因此，该假设不成立，即g (g) 5的最小度数。这个定理在图着色理论中起着重要的作用。1.准备判断定理1。插入2度顶点并删除2度顶点定义17.5。设置e=(u，V)作为图G的边，从G中删除e并添加一个新的顶点W，使U和V都与W相邻，这称为在G中插入一个2度的顶点W。设W是G中的一个2度的顶点，W与U和V相邻。删除W并添加新的边(U和V)称为在G中删除2度的顶点W17.3平面图的判断。图G1和G2之间的同胚是同胚的，如果这两个图G1和G2在重复插入或删除2度顶点后是同构的或同构的。以上两个图分别与K3，3和K5是同胚的。两个判断定理17.13(库拉索定理1)图G是平面图，当且仅当图G不包含与K5或K3，3相同的子图。定理17.14(库拉索定理2)图G是平面图，当且仅当在图G中没有子图可以收缩到K5或K3，3。17.1证明了彼得森地图不是一个计划。彼得森图的顶点顺序如图(1)所示。证明，也可以证明如下：G用来表示彼得森图，所以G=G-(j，G)，(c，d) G如图(3)所示，很容易知道它与K3，3是同态的，而边(a，f)，(b，G)，(c，h)，(d，I)，(e，j)在图中收缩，得到的图如图(2)所示，它是K5的，从定理17.16可以看出彼得森图是根据定理17.15，g是一个非平面图。通过在K5插入2度顶点，或者在K5外放置一个顶点，使其与K5上的几个顶点相邻，可以生成多少6阶简单连通非同构非平面图？使用插入2度顶点的方法，只能产生一个非平面图，如图(1)所示。回答，在K5外放置一个顶点，使其与K5上的1到5个顶点相邻，得到5个图，如图(2)到(6)所示。它与K5是同胚的，所以它不是平面图。它们都包含K5作为子图。根据库拉索定理，它们都是非平面图，也满足其他要求。从K3，3加上几条边可以生成多少6阶连通的简单非同构非平面图？通过给K3，3增加1 6条边得到的图都包含K3，3作为子图。根据库拉索定理，它们都是非平面图。当添加2、3和4条边时，分别生成两个非同构的非平面图，加上K3、3和3，有10个非平面图满足要求。其中，绿线边表示后来添加的新边。对偶图的定义17.6让G是平面图的平面嵌入，并如下构造G的对偶图G*:将G*的顶点vi*放置在G的平面Ri中。让E是G的任何边。如果E在G的表面Ri和Rj之间的公共边界上，则G*的边e*与E相交，并且与G*相关联的e*的顶点vi*和vj*位于Ri和Rj中，即e*=(vi*，vj*)，e*不与任何其他边相交。如果e是G中的一个桥并且在曲面ri的边界上，则e*是以Ri中G*的顶点vi*为端点的环，即e*=(vi*，vi*)。实线边图是平面图，虚线边图是它的对偶图。从定义中不难看出G的对偶图G*具有以下性质：G*是平面图，嵌入在平面中。G*是连通图。如果边E是G中的环，对应于G*和E的边e*是桥，如果E是桥，对应于G*中的E的边e*是环。在大多数情况下，G*是一个多重图(有平行边的图)。同构平面图(平面嵌入)的对偶图不一定是同构的。平面图和对偶图的阶、边数和边数之间的关系。定理17.15如果G*是连通平面图G的对偶图，n*，m*，r*和n，m，r分别是G*和G的顶点数、边数和面数，则(1)n*=r(2)m*=m(3)r*=n(4)如果G*的顶点v*i位于G的面Ri，则DG * (vi *=deg (ri)。(1)和(2)从G*的结构中是明显的。(3)由于G和G*都是连通的，所以满足欧拉公式： n-m r=2n *-m * r *=2。从(1)和(2)，可以看出r*=2 m*-n*=2 m-r=n(4)将g的表面Ri的边界设置为Ci，将Ci设置为具有k1(k10)个桥和k2个非桥边缘，因此Ci的长度为k2k1，即deg (ri)=k2k1，在vi*处有k1个环对应于k1个桥，k2个非桥边缘对应于来自vi*的k2个边缘，所以DG * (vi *=k22k1=deg (ri)。证明，定理17.16将G*设置为具有k (k2)个连通分支的平面图G的对偶图，n*，m*，r*，n，m，r分别是G*和G的顶点数、边数和面数，(1) n *=r (2) m *=m (3) r *=nk1 (4)将G*的顶点v*i设置为位于G的面Ri中，然后dG*(v*i)=deg(Ri)。3，自对偶图定义17.7集G*为平面图G一个顶点被放置在n1 (n4)边cn1上，使得这个顶点与cn1上的所有顶点相邻。得到的n阶简单图称为n阶轮图。Wn。n个奇数的轮图称为奇数阶轮图。n个偶数的轮图称为偶数阶轮图。轮图都是自对偶图。在这一节的最后，本章的主要内容，计划和计划嵌入。计划的面貌和时间。