平面图及其性质课件

5.6.1平面图及其性质

5.6.1平面图及其性质基本内容平面图的相关概念欧拉公式Kuratowski(库拉托夫斯基)定理基本内容平面图的相关概念2平面图的定义先从一个简单的例子谈起。一个工厂有3个车间和3个仓库。为了工作需要，车间与仓库之间将设专用的车道。为避免发生车祸，应尽量减少车道的交叉点，最好是没有交叉点，这是否可能？平面图的定义先从一个简单的例子谈起。一个工厂有33

如图5.6.1（a）所示，A，B，Ｃ是3个车间，M，Ｎ，P是3座仓库。经过努力表明，要想建造不相交的道路是不可能的，但可以使交叉点最少（如图5.6.1（b））。1图5.6.1如图5.6.1（a）所示，A，B，Ｃ是3个车间，M，4引入

这些实际问题涉及到平面图的研究。近年来，由于大规模集成电路的发展，也促进了平面图的研究。

例如在电路设计中常常要考虑布线是否可以避免交叉以减少元件间的互感影响。如果必然交叉，那么怎样才能使交叉处尽可能少？或者如何进行分层设计，才使每层都无交叉？引入这些实际问题涉及到平面图的研究。近年来，由于大规5平面图的定义定义5.30

若简单图G=<V,E>的图形在平面上能画成如下形式：（1）没有两个结点重合；（2）除结点外每条边不相交，则称G是具有平面性的图，或简称为平面图（PlanarGraph）。平面图的定义定义5.306示例例如

下图（1）~（4）是平面图，（5）不是平面图。对于平面图G的定义，通俗的来说，就是能够把G的所有结点和边画在平面上，且使得任何两条边除了端点外没有其他的交点。示例例如对于平面图G的定义，通俗的来说，就是7

应当注意，有些图从表面上看，它的某些边是相交的，但是不能就此肯定它不是平面图。如图5.6.2(a)表面上看有几条边相交，但是把它画成图5.6.2(b)，则可以看出它是一个平面图。图5.6.2平面图示例应当注意，有些图从表面上看，它的某些边是相交的，但是8平面图的特点定义5.31

设G是一个平面图.若G的图形中由边围成的封闭区域不能再分割成两个或两个以上的包含更少边数的子区域，则称这个区域为G的面（Face），包围这个区域的边称为面的边界(Bound)，其中有一个面的区域为这个平面图的外部边界组成，这个面称为外部面或无限面(ExteriorFace)。面的边界中的边数称为面的度（Degree）（割边在计算时算作两条边！），面R的度数记为deg(R)。平面图的特点定义5.319面

面的概念也可以用下面形象的说法加以描述：假设把一个平面图画在平面上，然后用一把小刀，沿着图的边切开，那么平面就被切成许多块，每一块就是图的一个面。

更确切地说，平面图的一个面就是平面的一块，它用边作边界线，且不能再分成更小的块。面面的概念也可以用下面形象的说法加以描述：假设把一10割边及与割边相关的概念对边割集和割边通俗的理解：

边割集：无向图G去掉几条边以后，这个图的连通分支增加了（即之前一个图变为现在两个图），而这些边所构成的集合称为边割集。

割边：边割集中只有一条边，这条边就称为割边。割边只能是一个面的边界！若一条边不是割边，它必是两个面的公共边界；两个以一条边为公共边界的面称为相邻的面。割边及与割边相关的概念对边割集和割边通俗的理解：11示例解析

如图5.6.3的图有7个结点、8条边，它把平面分成三个面：R1，R2，R3。其中：R1由回路v1v2v3v4v5v6v5v4v1所围，R2由回路v1v4v7v1

所围，而R3在图形之外，称为无限面（外部面），它由回路v1v2v3v4v7v1所围，所以

deg(R1)=8，deg(R2)=3，deg(R3)=5。

图5.6.3有限面和无限面（外部面）示例示例解析如图5.6.3的图有7个结点、8条边，它把12其中，r是G的面数，e为边数。定理5.20

一个有限平面图，其面的度之和等于其边数的两倍，即定理5.20其中，r是G的面数，e为边数。定理5.20定理5.2013定理5.20证明例如在图5.6.3中,

这正好是边数８的两倍。

因任何一条边，或者是两个面的公共边，或者是在一个面中作为边界被重复计算两次。故面的次数之和等于其边数的两倍。定理5.20证明例如在图5.6.3中,这正好是边数８的两14欧拉公式定理5.19设连通平面图G=<V,E>的顶点数，边数和面数分别为v,e和r则有欧拉公式

v－e＋r＝2欧拉公式

1750年欧拉发现，任何一个凸多面体的顶点数v、边数e和面数r之间满足关系式

v－e＋r=2这就是著名的欧拉公式。这个结论也可以推广到平面图上来。欧拉公式定理5.19欧拉公式15数学归纳法第一数学归纳法一般地，证明一个与自然数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）都成立。数学归纳法第一数学归纳法16证明

对G的边数e进行归纳。

若e=0，由于G是连通图，故必有v＝1。这时只有一个无限面，即r＝1。所以有v－e＋r＝2。

若e=1，这时有两种情况：

1)该边是自回路，则有v＝1,r＝2。

所以v－e＋r＝1－1＋2＝2。

2)该边不是自回路，则有n＝2，r＝1。所以v－e＋r＝2－1＋1＝2。

证明17

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

综合以上，欧拉公式得证。假设对小于e条边的所有图，欧拉公式成立。现考虑e条边18定理5.19的推论推论

设平面图G=<V,E>有k个连通分支，它的顶点数，边数和面数分别为v,e和r，则有v-e+r=k+1.定理5.19的推论推论19定理5.21定理5.21

设G是一个阶数（结点数）大于2的简单连通平面图，顶点数和边数分别为v，e，则有

e≤3v－6

设G有r个面，因为每个面至少由3条边围成，所以G的各面的度之和为由定理5.20可知代入欧拉公式v－e＋r=2消去r，可得定理5.21定理5.21设G是一个阶数（结点数）大于220若全部结点的度均大于5，则有即3v≤e，再由定理5.21的公式e≤3v－6可得3v≤3v－6，矛盾。定理5.21推论推论

在任何简单连通平面图中，至少存在一个其度不超过5的结点。若全部结点的度均大于5，则有即3v≤e，再由定理5.21的公21定理5.22定理5.22

K5和K3，3都是非平面图图5.6.4图K5K5如图5.6.4，这里v＝5，e＝10，而3v－6=3×5－6＝9≤10，所以K5不是平面图。定理5.22定理5.22图5.6.4图K522证明若K3,3是平面图，则每个面的度为4，因而有4r=2e，即2r=e，代入欧拉公式v－e＋r=2，则应有2v-e=4,但2×6－9＝3，矛盾。

故K3,3不是平面图。证明若K3,3是平面图，则每个面的度为4，因而有4r23

虽然欧拉公式可用来判别某个图是非平面图，但是当结点数和边数较多时，应用欧拉公式进行判别就会相当困难。

一个图是否有平面的图形表示是判别平面图的最具说服力的方法，但是又因为工作量太大而不实用。要找到一个好的方法去判断任何一个图是否是平面图，就得对平面图的本质有所了解。

Kuratowski建立了一个定理，定性地说明了平面图的本质。虽然欧拉公式可用来判别某个图是非平面图，但是当结点24细分图

首先，在图G的边(u,v)上新增加一个2度结点w，称为图G的细分。

严格的说，细分是从G中先删去边(u,v),再增加一个新结点w及边(u,w)和边(v,w)。一条边上也可以同时增加有限个2度结点，所得的新图称为原图的细分图。细分图首先，在图G的边(u,v)上新增加一个2度结点25细分图示例

例如，在图5.23中(b)是(a)的一种细分图，(d)是(c)的一种细分图。容易知道，若G1是G的细分图，则G1与G同为平面图或非平面图细分图示例例如，在图5.23中(b)是(a)的一种细26Kuratowski定理定理5.23（Kuratowski定理）一个图是平面图当且仅当它不包含与K3,3或K5的细分图同构的子图。Kuratowski定理定理5.23（Kuratowski27例5.7例5.7证明图（a）（Petersen图）不是平面图。证明：删去Petersen图（a）中的结点b,得其细分图(b)H.而图（b）H的细分图（去掉2度结点a，c，g）与K3.3同构，由库拉托夫斯基定理可得Petersen图不是平面图.例5.7例5.7证明图（a）（Petersen图）不是平面28例题v1v2v3v4v5v6R1R2R0此平面图，共有3个面：R0,R1,R2

；R1

的边界：v1v3v4v1，deg(R1)=3；R2的边界：v1v2v3v1

，deg(R2)=3；R0

的边界为复杂回路：v1v2v3v4v5v6v5v4v1，deg(R0)=8。指出下图所示平面图的面、面的边界及面的度数。例题v1v2v3v4v5v6R1R2R0此平面图，共有3个29例题R1的边界:R2的边界:R3的边界:R0的边界:abcefgabcdde,fgdeg(R1)=deg(R2)=deg(R3)=deg(R0)=1328例题R1的边界:abcefgabcdde,fgdeg(R130

5.6.1平面图及其性质

5.6.1平面图及其性质基本内容平面图的相关概念欧拉公式Kuratowski(库拉托夫斯基)定理基本内容平面图的相关概念32平面图的定义先从一个简单的例子谈起。一个工厂有3个车间和3个仓库。为了工作需要，车间与仓库之间将设专用的车道。为避免发生车祸，应尽量减少车道的交叉点，最好是没有交叉点，这是否可能？平面图的定义先从一个简单的例子谈起。一个工厂有333

如图5.6.1（a）所示，A，B，Ｃ是3个车间，M，Ｎ，P是3座仓库。经过努力表明，要想建造不相交的道路是不可能的，但可以使交叉点最少（如图5.6.1（b））。1图5.6.1如图5.6.1（a）所示，A，B，Ｃ是3个车间，M，34引入

这些实际问题涉及到平面图的研究。近年来，由于大规模集成电路的发展，也促进了平面图的研究。

例如在电路设计中常常要考虑布线是否可以避免交叉以减少元件间的互感影响。如果必然交叉，那么怎样才能使交叉处尽可能少？或者如何进行分层设计，才使每层都无交叉？引入这些实际问题涉及到平面图的研究。近年来，由于大规35平面图的定义定义5.30

若简单图G=<V,E>的图形在平面上能画成如下形式：（1）没有两个结点重合；（2）除结点外每条边不相交，则称G是具有平面性的图，或简称为平面图（PlanarGraph）。平面图的定义定义5.3036示例例如

下图（1）~（4）是平面图，（5）不是平面图。对于平面图G的定义，通俗的来说，就是能够把G的所有结点和边画在平面上，且使得任何两条边除了端点外没有其他的交点。示例例如对于平面图G的定义，通俗的来说，就是37

应当注意，有些图从表面上看，它的某些边是相交的，但是不能就此肯定它不是平面图。如图5.6.2(a)表面上看有几条边相交，但是把它画成图5.6.2(b)，则可以看出它是一个平面图。图5.6.2平面图示例应当注意，有些图从表面上看，它的某些边是相交的，但是38平面图的特点定义5.31

设G是一个平面图.若G的图形中由边围成的封闭区域不能再分割成两个或两个以上的包含更少边数的子区域，则称这个区域为G的面（Face），包围这个区域的边称为面的边界(Bound)，其中有一个面的区域为这个平面图的外部边界组成，这个面称为外部面或无限面(ExteriorFace)。面的边界中的边数称为面的度（Degree）（割边在计算时算作两条边！），面R的度数记为deg(R)。平面图的特点定义5.3139面

面的概念也可以用下面形象的说法加以描述：假设把一个平面图画在平面上，然后用一把小刀，沿着图的边切开，那么平面就被切成许多块，每一块就是图的一个面。

更确切地说，平面图的一个面就是平面的一块，它用边作边界线，且不能再分成更小的块。面面的概念也可以用下面形象的说法加以描述：假设把一40割边及与割边相关的概念对边割集和割边通俗的理解：

边割集：无向图G去掉几条边以后，这个图的连通分支增加了（即之前一个图变为现在两个图），而这些边所构成的集合称为边割集。

割边：边割集中只有一条边，这条边就称为割边。割边只能是一个面的边界！若一条边不是割边，它必是两个面的公共边界；两个以一条边为公共边界的面称为相邻的面。割边及与割边相关的概念对边割集和割边通俗的理解：41示例解析

如图5.6.3的图有7个结点、8条边，它把平面分成三个面：R1，R2，R3。其中：R1由回路v1v2v3v4v5v6v5v4v1所围，R2由回路v1v4v7v1

所围，而R3在图形之外，称为无限面（外部面），它由回路v1v2v3v4v7v1所围，所以

deg(R1)=8，deg(R2)=3，deg(R3)=5。

图5.6.3有限面和无限面（外部面）示例示例解析如图5.6.3的图有7个结点、8条边，它把42其中，r是G的面数，e为边数。定理5.20

一个有限平面图，其面的度之和等于其边数的两倍，即定理5.20其中，r是G的面数，e为边数。定理5.20定理5.2043定理5.20证明例如在图5.6.3中,

这正好是边数８的两倍。

因任何一条边，或者是两个面的公共边，或者是在一个面中作为边界被重复计算两次。故面的次数之和等于其边数的两倍。定理5.20证明例如在图5.6.3中,这正好是边数８的两44欧拉公式定理5.19设连通平面图G=<V,E>的顶点数，边数和面数分别为v,e和r则有欧拉公式

v－e＋r＝2欧拉公式

1750年欧拉发现，任何一个凸多面体的顶点数v、边数e和面数r之间满足关系式

v－e＋r=2这就是著名的欧拉公式。这个结论也可以推广到平面图上来。欧拉公式定理5.19欧拉公式45数学归纳法第一数学归纳法一般地，证明一个与自然数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）都成立。数学归纳法第一数学归纳法46证明

对G的边数e进行归纳。

若e=0，由于G是连通图，故必有v＝1。这时只有一个无限面，即r＝1。所以有v－e＋r＝2。

若e=1，这时有两种情况：

1)该边是自回路，则有v＝1,r＝2。

所以v－e＋r＝1－1＋2＝2。

2)该边不是自回路，则有n＝2，r＝1。所以v－e＋r＝2－1＋1＝2。

证明47

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

综合以上，欧拉公式得证。假设对小于e条边的所有图，欧拉公式成立。现考虑e条边48定理5.19的推论推论

设平面图G=<V,E>有k个连通分支，它的顶点数，边数和面数分别为v,e和r，则有v-e+r=k+1.定理5.19的推论推论49定理5.21定理5.21

设G是一个阶数（结点数）大于2的简单连通平面图，顶点数和边数分别为v，e，则有

e≤3v－6

设G有r个面，因为每个面至少由3条边围成，所以G的各面的度之和为由定理5.20可知代入欧拉公式v－e＋r=2消去r，可得定理5.21定理5.21设G是一个阶数（结点数）大于250若全部结点的度均大于5，则有即3v≤e，再由定理5.21的公式e≤3v－6可得3v≤3v－6，矛盾。定理5.21推论推论

在任何简单连通平面图中，至少存在一个其度不超过5的结点。若全部结点的度均大于5，则有即3v≤e，再由定理5.21的公51定理5.22定理5.22

K5和K3，3都是非平面图图5.6.4图K5K5如图5.6.4，这里v＝5，e＝10，而3v－6=3×5－6＝9≤10，所以K5不是平面图。定理5.22定理5.22图5.6.4图K552证明若K3,3是平面图，则每个面的度为4，因而有4r=2e，即2r=e，代入欧拉公式v－e＋r=2，则应有2v-e=4,但2×6－9＝3，矛盾。

故K3,3不是平面图。证明若K3,3是平面图，则每个面的度为4，因而有4r53

虽然欧拉公式可用来判别某个图是非平面图，但是当结点数和边数较多时，应用欧拉公式进行判别就会相当困难。

一个图是否有平面的图形表示是判别平面图的最具说服力的方法，但是又因为工作量太大而不实用。要找到一个好的方法去判断任何一个图是否是平面图，就得对平面图的本质有所了解。

Kuratowski建立了一个定理，定性地说明了平面图的本质。虽然欧拉公式可用来判别某个图是非平面图，