平面图及其性质ppt课件

1、5.6.1 平面图及其性质,基本内容,平面图的相关概念 欧拉公式 Kuratowski(库拉托夫斯基)定理,平面图的定义,先从一个简单的例子谈起。一个工厂有 3 个车间和 3 个仓库。为了工作需要，车间与仓库之间将设专用的车道。为避免发生车祸，应尽量减少车道的交叉点，最好是没有交叉点，这是否可能,如图5.6.1（a）所示，A，B，是3个车间，M，P是3座仓库。经过努力表明，要想建造不相交的道路是不可能的，但可以使交叉点最少（如图5.6.1（b,1,图5.6.1,引入,这些实际问题涉及到平面图的研究。近年来，由于大规模集成电路的发展，也促进了平面图的研究。 例如在电路设计中常常要考虑布线是否可以

2、避免交叉以减少元件间的互感影响。如果必然交叉，那么怎样才能使交叉处尽可能少？或者如何进行分层设计，才使每层都无交叉,平面图的定义,定义5.30 若简单图G=的图形在平面上能画成如下形式： （1）没有两个结点重合； （2）除结点外每条边不相交，则称G是具有平面性的图，或简称为平面图（Planar Graph,示例,例如 下图（1）（4）是平面图，（5）不是平面图,对于平面图G的定义，通俗的来说，就是能够把G的所有结点和边画在平面上，且使得任何两条边除了端点外没有其他的交点,应当注意，有些图从表面上看，它的某些边是相交的，但是不能就此肯定它不是平面图。 如图5.6.2(a)表面上看有几条边相交，但

3、是把它画成图5.6.2(b)，则可以看出它是一个平面图,图5.6.2 平面图示例,平面图的特点,定义5.31 设G是一个平面图.若G的图形中由边围成的封闭区域不能再分割成两个或两个以上的包含更少边数的子区域，则称这个区域为G的面（Face），包围这个区域的边称为面的边界(Bound)，其中有一个面的区域为这个平面图的外部边界组成，这个面称为外部面或无限面(Exterior Face)。面的边界中的边数称为面的度（Degree）（割边在计算时算作两条边！），面R 的度数记为deg(R,面,面的概念也可以用下面形象的说法加以描述：假设把一个平面图画在平面上，然后用一把小刀，沿着图的边切开，那么平面

4、就被切成许多块，每一块就是图的一个面。 更确切地说，平面图的一个面就是平面的一块，它用边作边界线，且不能再分成更小的块,割边及与割边相关的概念,对边割集和割边通俗的理解： 边割集：无向图G去掉几条边以后，这个图的连通分支增加了（即 之前一个图变为现在两个图），而这些边所构成的集合称为边割集。 割边：边割集中只有一条边，这条边就称为割边。 割边只能是一个面的边界！ 若一条边不是割边，它必是两个面的公共边界； 两个以一条边为公共边界的面称为相邻的面,示例解析,如图5.6.3的图有7个结点、8条边，它把平面分成三个面：R1，R2，R3。其中： R1由回路v1v2v3v4v5v6v5v4v1所围，R2

5、由回路v1v4v7v1 所围，而R3在图形之外，称为无限面（外部面），它由回路v1v2v3v4v7v1所围，所以 deg(R1) =8 ，deg(R2) =3 ，deg(R3) =5,图5.6.3 有限面和无限面（外部面）示例,其中，r是G的面数，e为边数,定理 5.20 一个有限平面图，其面的度之和等于其边数的两倍，即,定理5.20,定理5.20证明,例如在图5.6.3中,这正好是边数的两倍,因任何一条边，或者是两个面的公共边，或者是在一个面中作为边界被重复计算两次。故 面的次数之和等于其边数的两倍,欧拉公式,定理 5.19 设连通平面图G=的顶点数，边数和面数分别为v,e和r则有欧拉公式

6、ver2,欧拉公式 1750年欧拉发现，任何一个凸多面体的顶点数v 、边数e和面数r之间满足关系式 ver = 2 这就是著名的欧拉公式。这个结论也可以推广到平面图上来,数学归纳法,第一数学归纳法 一般地，证明一个与自然数n有关的命题P(n），有如下步骤： （1）证明当n取第一个值n0 时命题成立。n0 对于一般数列取值为0或1，但也有特殊情况； （2）假设当n=k（ k n0 ，k为自然数）时命题成立，证明当n=k+1时命题也成立。 综合（1）（2），对一切自然数n（n n0 ），命题P(n）都成立,证明,对G的边数e进行归纳。 若e=0，由于G是连通图， 故必有v 1。 这时只有一个无限面

7、， 即r1。所以有v er2。 若e=1，这时有两种情况： 1) 该边是自回路， 则有v1,r2。 所以 ver 112 2。 2) 该边不是自回路， 则有n2， r1。 所以 ver 211 2,假设对小于e条边的所有图，欧拉公式成立。现考虑e条边的图G，设它有v个结点。 增加一条边，为使图连通，这时只有如下两种情况： (1)该边的一端是悬挂点(以该点为端点的边数为1的点)，这时增加了一个顶点和一条边，面数不变，满足欧拉公式，即（v+1）-（e+1）+r=v-e+r=2; (2)该边的两端为原图的两个顶点，这时顶点数不增加，但增加了一条边和一个面，所以也满足欧拉公式，即v-(e+1)+(r+

8、1)=v-e+r=2; 综合以上，欧拉公式得证,定理5.19的推论,推论 设平面图G=有k个连通分支，它的顶点数，边数和面数分别为v,e和r，则有v-e+r=k+1,定理5.21,定理 5.21 设G是一个阶数（结点数）大于2的简单连通平面图，顶点数和边数分别为v，e， 则有 e3v6,设G有r个面， 因为每个面至少由3条边围成，所以G的各面的度之和为,由定理5.20可知,代入欧拉公式ver = 2消去r，可得,若全部结点的度均大于5，则有,即3ve，再由定理5.21的公式e3v6可得3v3v6，矛盾,定理5.21推论,推论 在任何简单连通平面图中，至少存在一个其度不超过5的结点,定理 5.2

9、2,定理 5.22 K5和K3，3都是非平面图,图 5.6.4 图K5,K5如图5.6.4，这里v5，e10，而3v6=356910，所以K5不是平面图,证明,若K3,3是平面图，则每个面的度为4，因而有4r=2e，即2r=e，代入欧拉公式ver = 2 ，则应有2v-e=4,但2693，矛盾。 故K3,3不是平面图,虽然欧拉公式可用来判别某个图是非平面图，但是当结点数和边数较多时，应用欧拉公式进行判别就会相当困难。 一个图是否有平面的 图形表示 是判别平面图的最具说服力的方法，但是又因为工作量太大而不实用。要找到一个好的方法去判断任何一个图是否是平面图，就得对平面图的本质有所了解。 Kura

10、towski建立了一个定理，定性地说明了平面图的本质,细分图,首先，在图G的边(u,v)上新增加一个2度结点w，称为图G的细分。 严格的说，细分是从G中先删去边(u,v),再增加一个新结点w及边(u,w)和边(v,w)。一条边上也可以同时增加有限个2度结点，所得的新图称为原图的细分图,细分图示例,例如，在图5.23中(b)是(a)的一种细分图，(d)是(c)的一种细分图。容易知道，若G1是G的细分图，则G1与G同为平面图或非平面图,Kuratowski定理,定理 5.23（Kuratowski定理） 一个图是平面图当且仅当它不包含与K3,3或K5的细分图 同构的子图,例5.7,例5.7 证明图（a）（Petersen图）不是平面图,证明：删去Petersen图（a）中的结点b,得其细分图(b)H.而图（b）H的细分图（去掉2度结点a，c，g）与K3.3同构，由库拉托夫斯基定理可得Petersen图不是平面图,例题,此平面图，共有3 个面：R0,R1,R2 ； R1 的边界： v1v3v4v1，deg(R1) =3； R2 的边界：v1v2v3v1 ，d