平面图PPT课件VIP

-,1,平面图,-,2,问题：假定有三个仓库x1，x2，x3和三个车站y1，y2，y3。为了便于货物运输，准备在仓库与车站间修筑铁路，如图(a)所示,其中边代表铁路。问是否存在一种使铁路不交叉的路线设计方案，以避免修建立交桥。,但如果在x2与y1之间也要修一条铁路，则可验证满足要求的方案不存在。,-,3,定义：若图G可画在一个平面上使除顶点外边不交叉，则称G可嵌入平面，或称G为可平面图。可平面图G的边不交叉的一种画法称为G的一个平面嵌入，G的平面嵌入表示的图称为平面图。,例：,=,平面图,-,4,可平面图,不可平面图,=,不可平面图,=,-,5,（1）G是非连通图，每个连通分支可嵌入平面，G称为可平面图。反之，不然。（2）若G是连通图，但G有割点，从割点处割开，每个小块是可平面，G就是可平面的。反之，不然。因此一般情况下讨论连通度大于2的情形。（3）若G是一个平面图，G的任何一个子图都是平面图。,-,6,可平面嵌入和可球面嵌入等价,定理：图G可平面嵌入的充要条件是G可球面嵌入。证明：考虑球极平面投影，球面S与平面P相切，过切点的直径的另外一段为Z,定义映射f:SP设p是平面P上的点，s是球面S上的点，仅当z,s,p三点共线的时候有f(s)=p,f(z)=无穷远。f是可逆映射.,-,7,若G是图G在S上的嵌入，不妨设Z不在G的边和顶点上，由f的性质，G在平面上的像即为G在P上的嵌入。反之，若G”是图G在平面P上的嵌入，则由f的性质，G”在S上的原像即为图G在S上的嵌入。,-,8,注意:,一个图可嵌入平面的充分必要条件是每个连通分支可嵌入平面如一个连通图有割点,这从割点切开得到的图是可嵌入的,则这个图是可平面的,否则不可平面因此,可平面图只需要讨论2-连通图.,-,9,定义：设G是一个平面图，G将所嵌入的平面划分为若干个区域，每个区域的内部连同边界称为G的面，无界的区域称为外部面或无限面。每个平面图有且仅有一个外部面。设f是G的一个面，构成f的边界的边数（割边计算两次）称为f的次数，记为deg(f)。,-,10,如果两个面有共同的边界，称这两个面相邻。如果边不是割边，它一定是某两个面的共同边界。,-,11,例：,有5个面：f1，f2，f3，f4，f5（f5为外部面）,图不连通，其外部面的次数为5,deg(f1)=1,deg(f2)=2,deg(f3)=3,deg(f4)=6,deg(f5)=10,-,12,定理：设具有m条边的平面图G的所有面的集合为,则,证明任取G的一条边e。若e是两个面的公共边，则在计算面的次数时，e被计算两次。若e不是公共边，则e是G的割边，由面的次数的定义，e也被计算两次。所以所有面的次数之和是边数的2倍，即结论成立。,-,13,平面图的Euler公式,问题1：树是特殊的平面图。树的顶点数，边数之间有关系，而树的面数就是1.它们能满足n-m+r=2,是否对一般的平面图也满足这个关系问题2：如果一个平面图有不同的平面嵌入，不同的平面嵌入面数是否一样呢？（面数是平面图的最重要的特征之一）下面的定理就回答了这个问题。,-,14,平面图的Euler公式,定理：（Euler公式）设G是具有n个点m条边r个面的连通平面图，则有nm+r=2,证明：对r用归纳法。,当r=1时，G无圈又连通，从而是树，有n=m+1，于是n-m+r=（m+1）-m+1=2。,-,15,归纳假设：设r=k的连通平面图满足n-m+r=2.设G是任意一个r=k+1的连通平面图。当r=k+1时，此时G至少两个面，从而有圈C。删去C中一条边，记所得之图为G。并设G的点数、边数和面数依次为n,m和r,易知G仍连通，但只有k个面，由归纳假设有n-m+r=2。又因为n=n，m=m-1，r=r1，所以有n-（m-1）+（r-1）=2,-,16,定理2：对具有k个连通分支的平面图G,有n-m+r=k+1证明：假设平面图G的k个连通分支G_i的顶点数，边数，面数分别为n_i,m_i,r_i,i=1,2,k.根据定理1有n_i-m_i+r_i=2,则(n_1+n_2+n+k)-(m_1+m_k)+(r_1+r_k)=2k,-,17,而n_1+n_k=n,m_1+m_k=m,r_1+r_k=r+(k-1),理由是对每个连通分支的外部面来说，对G只有一个外部面，也就是被重复多算了k-1次。因此n-m+r=k+1,-,18,定理：设G是具有n个点的连通平面图,是G中所有面的集合，若对任意的f均有deg(f)l3，则m,证明：由于面的次数不少于l,也就是每个面的周界所含的边数不少于l,则面边结合图的总的边数至少是rl,也就是面的次数之和至少是rl,而平面图的面数之和为2m，所以rl=3)，则边数m与顶点数n有如下关系m,-,21,推论：G是n（=3)阶m条边的简单平面图，则m=3,显然对每个面f,都有d(f)=3.由公式2m=sumd(f)=3r又由欧拉公式得到n-m+r=2即3n-3m+3r=6于是3n-6=m,-,22,（2）G有k个连通分支，对每个连通分支用（1）的结果，然后推出m=3)阶圈，则m=l(n-2)/(l-2).证明：必须先证明：每条边均在两个面的公共边上。反证：如G有一条边不是两个面的公共边，则这条边必不在回路上。于是它所在面不是由圈组成，而是由闭迹组成，矛盾。由于G的的每个面均是l阶圈，而G的每个面均在两个面上，于是,-,25,lr=2m,r=2m/n有公式n-m+r=2,解得m=l(n-2)/(l-2),-,26,极大平面图,定义:一个图G是连通的可平面图,但任意不相邻的两个顶点间加一条边都不可平面的,则称这个图是极大可平面图.定理:设G是极大可平面图,则G的每个面都是一个三角形.,-,27,性质1：G是连通的性质2：G不存在割边性质3：设G为n（n3）阶极大平面图，则G的每个面的次数均为3.证明：充分性：设G是G的平面嵌入，且每个面皆3次，由公式所有的面的次数之和=2m,则3r=2m,由欧拉公式n-m+r=2,则m=3n-6.而平面图的边的上界是3n-6,G的边已经达到上界，故G是极大平面图。,-,28,必要性：,-,29,推论：平面图G是极大平面图的充分必要条件是m=3n-6.定理2:设G是顶点数大于等于4的极大可平面图,则G的最小度数大于等于3.证明：任取G中一个点v，由于G是平面图，则G-v也是平面图。设G是G的平面嵌入，则v在G的位置必在G-v的某个面f的内部.又G是极大平面图，f的边界上至少有三个顶点，且这些点必须与v都相邻，故d(v)大于等于3.由v的任意性知，G的最小度数至少是3.,-,30,可平面图的判断,由于我们已经知道K5和K3,3都不是平面图，我们把它们的边的内点处添加一些新的点，这些得到的图仍然不是平面图。我们称这样得到的图是原来图的同胚图。如果一个图含有一个与K5或K3,3的同胚子图，则这个图一定不是平面图。问题是：这是不是必要条件呢？,-,31,定义:在一个图的任意一边的中间加上一个新点,将原来的一条边变成两条边,这样得到的图叫原来图的细分.如果两个图可由同一个图细分得到,称这两个图同胚.判定定理:G是可平面的当且仅当G中不含与K5和K3,3同胚的子图.判定定理2：G为平面图的充要条件是G中无可收缩成K5或K3,3的子图。,-,32,平面图的厚度,定义：如果一个图不是平面图，我们可以把它的边嵌入到几个平面，使得每个平面上的边不交叉，即把图的边集划分成且每个边导出的子图皆为平面图，t的最小值称为图G的厚度。平面图的厚度为1.非平面图，其厚度最少为2.单星妖怪的厚度为2.其外面的五角星和连接内面五角星的边成一平面图，内五角星成一平面图。,-,33,对一般图，厚度如何求是一个尚未解决的问题，至今既未给出计算厚度的公式，亦未建立有效的算法。对于厚度下界的估计有下面的定理。定理：如代表G