平面图及其性质.pptx

《平面图及其性质.pptx》由会员分享，可在线阅读，更多相关《平面图及其性质.pptx（30页珍藏版）》请在优知文库上搜索。

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

2、促进了平来，由于大规模集成电路的发展，也促进了平面图的研究面图的研究。 例如在电路设计中常常要考虑布线是否可例如在电路设计中常常要考虑布线是否可以避免交叉以减少元件间的互感影响。如果必以避免交叉以减少元件间的互感影响。如果必然交叉，那么怎样才能使交叉处尽可能少？或然交叉，那么怎样才能使交叉处尽可能少？或者如何进行分层设计，才使每层都无交叉？者如何进行分层设计，才使每层都无交叉？平面图的定义平面图的定义定义定义5.30 若简单图G=的图形在平面上能画成如下形式：（1）没有两个结点重合；（2）除结点外每条边不相交，则称G是具有平面性的图，或简称为平面图（平面图（Planar Graph）。）。示例

3、示例例如例如 下图（下图（1）（4）是平面图，（）是平面图，（5）不是平面图。）不是平面图。 对于平面图G的定义，通俗的来说，就是能够把G的所有结点和边画在平面上，且使得任何两条边除了端点外没有其他的交点。 应当注意，有些图从表面上看，它的某些边是相交的，但是不能就此肯定它不是平面图。 如图5.6.2(a)表面上看有几条边相交，但是把它画成图5.6.2(b)，则可以看出它是一个平面图。图图5.6.2 平面图示例平面图示例平面图的特点平面图的特点定义定义5.315.31 设G是一个平面图.若G的图形中由边围成的封闭区域不能再分割成两个或两个以上的包含更少边数的子区域，则称这个区域为G的面（Fac

4、e），包围这个区域的边称为面的边界(Bound)，其中有一个面的区域为这个平面图的外部边界组成，这个面称为外部面或无限面(Exterior Face)。面的边界中的边数称为面的度（Degree）（割边在计算时算作两条边！），面R R 的度数记为degdeg( (R R) )。面面 面的概念也可以用下面形象的说法加以描述：假设把一个平面图画在平面上，然后用一把小刀，沿着图的边切开，那么平面就被切成许多块，每一块就是图的一个面。 更确切地说，平面图的一个面就是平面的一块，它用边作边界线，且不能再分成更小的块。割边及与割边相关的概念割边及与割边相关的概念对边割集和割边通俗的理解：对边割集和割边通俗的

5、理解：q 边割集边割集：无向图：无向图G G去掉几条边以后，这个图的连通分支增去掉几条边以后，这个图的连通分支增加了（即加了（即 之前一个图变为现在两个图），而这些边所构成之前一个图变为现在两个图），而这些边所构成的集合称为边割集。的集合称为边割集。q 割边割边：边割集中只有一条边，这条：边割集中只有一条边，这条边就称为边就称为割边。割边。q 割边只能是一个面的边界！割边只能是一个面的边界！q 若一条边不是割边，它必是两个面的公共边界；若一条边不是割边，它必是两个面的公共边界；q 两个以一条边为公共边界的面称为相邻的面。两个以一条边为公共边界的面称为相邻的面。示例解析示例解析 如如图图5.6.

6、35.6.3的图有的图有7 7个结点、个结点、8 8条边，它把平面分成三个面条边，它把平面分成三个面：R R1 1，R R2 2，R R3 3。其中：其中： R R1 1由回路由回路v v1 1v v2 2v v3 3v v4 4v v5 5v v6 6v v5 5v v4 4v v1 1所所围围，R R2 2由回路由回路v v1 1v v4 4v v7 7v v1 1 所围，所围，而而R R3 3在图形之外，称为无限面（外部面），它由回路在图形之外，称为无限面（外部面），它由回路v v1 1v v2 2v v3 3v v4 4v v7 7v v1 1所围，所以所围，所以 degdeg( (R

7、 R1 1) =8 ) =8 ，degdeg( (R R2 2) =3 ) =3 ，degdeg( (R R3 3) =5) =5。 图图5.6.3 有限有限面和面和无限无限面（外部面（外部面）示例面）示例其中，其中，r是是G的面数，的面数，e为边数。为边数。deg()2riiRe定理定理 5.20 一个有限平面图，一个有限平面图，其面的其面的度度之和等于其边数的两倍之和等于其边数的两倍，即，即定理定理5.205.20定理定理5.205.20证明证明31deg( )83516iir 例例如在图5.6.3中, 这正好是边数这正好是边数的两倍。的两倍。 因任何一条边，或者是两个面的公共边，或者是在

8、一个面中作为边界被重复计算两次。故 面的次数之和等于其边数的两倍。欧拉公式欧拉公式定理定理 5.19 设连通平面图设连通平面图G=的顶点数，边数和面数分的顶点数，边数和面数分别为别为v,e和和r则有欧拉公式则有欧拉公式 ver2欧拉公式欧拉公式 1750年欧拉发现，任何一个凸多面体的顶点数v 、边数e和面数r之间满足关系式 ver = 2 这就是著名的欧拉公式。这个结论也可以推广到平面图上来。数学归纳法数学归纳法q 第一数学归纳法一般地，证明一个与自然数n有关的命题P(n），有如下步骤：（1）证明当n取第一个值n n0 0 时命题成立。n n0 0 对于一般数列取值为0或1，但也有特殊情况；（

9、2）假设当n=k（ k n n0 0 ，k为自然数）时命题成立，证明当n=k+1时命题也成立。综合（1）（2），对一切自然数n（n n n0 0 ），命题P(n）都成立。证明证明 对G的边数e进行归纳。 若e e=0，由于G是连通图， 故必有v v 1。 这时只有一个无限面， 即r r1。所以有v v e er r2。 若e e=1=1，这时有两种情况：这时有两种情况： 1) 1) 该该边是自回路，边是自回路， 则则有有v v1 1, ,r r2 2。 所以所以 v ve er r 1 11 12 2 2 2。 2 2) ) 该边不是自回路，该边不是自回路， 则有则有n n2 2， r r1

10、1。 所以所以 v ve er r 2 21 11 1 2 2。 假设假设对对小于小于e e条条边的所有图边的所有图，欧拉，欧拉公式公式成立成立。现现考虑考虑e e条条边的图边的图G G，设，设它它有有v v个个结点。结点。 增加一条边，为使图连通，这时只有如下两种情况： (1)该边的一端是悬挂点(以该点为端点的边数为1的点)，这时增加了一个顶点和一条边，面数不变，满足欧拉公式，即（v+1）-（e+1）+r=v-e+r=2; (2)该边的两端为原图的两个顶点，这时顶点数不增加，但增加了一条边和一个面，所以也满足欧拉公式，即v-(e+1)+(r+1)=v-e+r=2; 综合以上，欧拉公式得证。定

11、理定理5.195.19的推论的推论推论推论 设平面图G=有k个连通分支，它的顶点数，边数和面数分别为v,e和r，则有v-e+r=k+1.定理定理5.215.21定理定理 5.215.21 设设G G是一个阶数（结点数）大于是一个阶数（结点数）大于2 2的简单的简单连通平面图，顶点数和边数分别为连通平面图，顶点数和边数分别为v v，e e， 则有则有 e e33v v6 6 23er36ev 设设G有有r个面，个面， 因为每个面至少由因为每个面至少由3条边围成，所以条边围成，所以G的各的各面的度之和为面的度之和为由定理由定理5.20可知可知代入欧拉公式代入欧拉公式ver = 2消去消去r，可得，

12、可得若全部结点的度均大于5，则有即3ve，再由定理再由定理5.21的公式的公式e3v6可得可得3v3v6，矛盾。，矛盾。16deg()2riivRe定理定理5.215.21推论推论推论推论 在任何简单连通平面图中，至少存在一个其度不超过5的结点。定理定理 5.225.22q定理定理 5.225.22 K K5 5和和K K3 3，3 3都是非平面图都是非平面图图图 5.6.4 图图K5 K5如图如图5.6.4，这里，这里v5，e10，而，而3v6=356910，所以，所以K5不是平面图。不是平面图。证明证明 若K3,3是平面图，则每个面的度为4，因而有4r=2e，即2r=e，代入欧拉公式ver

13、 = 2 ，则应有2v-e=4,但2693，矛盾。 故K3,3不是平面图。 虽然欧拉公式可用来判别某个图是非平面图，但是当结点数和边数较多时，应用欧拉公式进行判别就会相当困难。 一个图是否有平面的 图形表示 是判别平面图的最具说服力的方法，但是又因为工作量太大而不实用。要找到一个好的方法去判断任何一个图是否是平面图，就得对平面图的本质有所了解。 Kuratowski建立了一个定理，定性地说明了平面图的本质。细分图细分图 首先，在图G的边(u,v)上新增加一个2度结点w，称为图G的细分。 严格的说，细分是从G中先删去边(u,v),再增加一个新结点w及边(u,w)和边(v,w)。一条边上也可以同时

14、增加有限个2度结点，所得的新图称为原图的细分图细分图。细分图示例细分图示例 例如，在图5.23中(b)是(a)的一种细分图，(d)是(c)的一种细分图。容易知道，若G1是G的细分图，则G1与G同为平面图或非平面图GKuratowski定理q定理定理 5.235.23（KuratowskiKuratowski定理定理） 一个图是平面图当且仅当它不包含与一个图是平面图当且仅当它不包含与K K3,33,3或或K K5 5的细分的细分图图 同构同构的子图。的子图。例例5.75.7q 例例5.75.7 证明图（证明图（a a）（）（PetersenPetersen图）不是平面图。图）不是平面图。 证明：

15、证明：删去删去PetersenPetersen图（图（a a）中的结点）中的结点b,b,得其细分得其细分图图(b)H.(b)H.而图（而图（b b）H H的细分图（去掉的细分图（去掉2 2度结点度结点a a，c c，g g）与）与K K3.33.3同构同构，由库拉托夫斯基定理可得，由库拉托夫斯基定理可得PetersenPetersen图图不是不是平面图平面图. .例题例题v1v2v3v4v5v6R1R2R0此平面图，共有此平面图，共有3 个面：个面：R0,R1,R2 ；R1 的边界：的边界： v1v3v4v1，deg(R1) =3；R2 的的边界：边界：v1v2v3v1 ，deg(R2)=3 ；R0 的边界为复杂回路：的边界为复杂回路： v1v2v3v4v5v6v5v4v1，deg(R0)=8 。 指出指出下图所示平面下图所示平面图的面、面的边界及面图的面、面的边界及面的度数。的度数。例题例题R1的边界的边界:R2的边界的边界:R3的边界的边界:R0的边界的边界:abcefgabcdde, fgdeg(R1)=deg(R2)=deg(R3)=deg(R0)=1328