平面图的概念与应用

Published on 2016 - 06 - 22

基本概念

平面图与非平面图

假设A~F表示6个村庄,要在这些村庄之间修筑如图1(a)所示的路,且使得任何两条路都不交叉,能找到满足条件的方案吗?答案是不可能的,无论怎么画(如图1(b)所示),总是有边相交。而图1(c)所示的无向图表面上存在相交的边,但可以把它改画成图1(d),这样就不存在相交的边了。

平面图(Planar Graph):设一个无向图为G(V,E),如果能把它画在平面上,且除V中的顶点外,任意两条边均不相交,则称该图为平面图。对平面图G,画出其无边相交的图,称为G的平面嵌入(Planar Embedding)。无平面嵌入的图称为非平面图(Nonplanar Graph)

图2(a)所示的四阶完全图K4,存在两条相交的边,但可以将这两条相交的边改画成不相交,因此K4是平面图。

又如2(c)是从K5中去掉了一条边,对其中相交的边可以改画成不相交,如图2(d)所示,因此该图也是平面图。

完全二部图K1,n(n≥1)和K2,n(n≥2)都是平面图,如图3(a)、3(b)和3(c)所示。其中,图3(a)中K1,n的标准画法已经是平面嵌入了,图3(b)左图所示的K2,n不是平面嵌入,但可以改画成右图所示的平面嵌入画法,图3(c)所示的K3,n同样可以改画成平面嵌入画法。

现在可以提前指出的是,在研究平面图理论中居重要地位的两个图K5和K3,3,如图4所示,都是非平面图。

区域与边界

一个平面图将平面划分成若干个部分,每个部分称为一个区域。下面给出区域的严格定义。

区域(Region):设G为一平面图(且已经是平面嵌入),若由G的一条或多条边所界定的范围内不含图G的顶点和边,则该范围内的平面部分称为G的一个区域(也称为面,Face),记为R。一个平面图所划分的区域中,总有一个区域是无界的,该区域称为外部区域(Exterior Region),通常记为R0。其他区域称为内部区域(Interior Region)。

区域个数:将平面图所划分的平面区域个数简称为平面图的区域个数,并用r表示。

例如,图5(a)所示的平面图,将平面分成6个区域,如图5(b)所示,因此,该平面图的区域个数r=6。其中R0为外部区域,R1~R5为内部区域。

边界(Boundary):在一个平面图中,顶点和边都与某个区域R关联的子图称为R的边界。边界实际上是平面图的一个回路,但不一定是圈(即简单回路)。

区域的度数:区域R的边界中,边的个数称为区域R的度数,记为deg(R)。

图5(b)所示的区域R1的边界为圈:(u,v,t,w,u),R1的度数为4;外部区域R0的边界为回路:(u,v,t,x,r,s,x,t,w,u),它不是一个圈,因为顶点t和x重复了,R0的度数为9。

极大平面图与极小非平面图

极大平面图:设G为平面图,若在G的任意不相邻的顶点u、v之间加边(u,v),所得图为非平面图,则称G为极大平面图。

例如,图2(c)所示的平面图就是极大平面图,该图只有一对顶点间没有边,如果加上这条边,则在图2(d)中,无论这条边怎么画,总是会和某些边相交。加上一条边后,该图变成了5阶完全图K5,因此K5是一个非平面图。

极小非平面图:如果在非平面图G中任意删除一条边,所得图为平面图,则称G为极小非平面图。

例如,在5阶完全图K5中,任意删除一条边后,都是平面图,因此K5就是一个极小非平面图。

平面图的对偶图

设G是平面图,且已经是平面嵌入了,按照如下方式构造图G*,称G*为图G的对偶图(Dual Graph)。

  1. 在G的区域Ri中放置G*的顶点。
  2. 设e∈E(G),若e是G的区域Ri和Rj的公共边界,则在G*中,顶点vi*和顶点vj*之间有一条边,记为e*e*与e相交,且e*不与图G中其他边相交。
  3. 若e为G中的桥,且为区域Ri的边界,则在G*的顶点上,存在一条从自身环。

例如,对图6(a)所示的平面图,构造对偶图的过程和结果分别如图6(b)和6(c)所示。在图6中,空心圆圈为平面图G中的顶点,实心圆圈为对偶图G*中的顶点。

由对偶图的定义不难看出,平面图G的对偶图G*有以下性质。

  1. G*是平面图,而且在构造时各条边就互不相交,即构造时就是其平面嵌入。
  2. G*是连通图。
  3. 若边e为G中的环,则G*与e对应的边e*为桥;若e为桥,则G*中与e对应的边e*为环。
  4. 在多数情况下,G*中含有较多的平行边。

关于平面图的一些定理

关于平面图,有如下一些定理(证明略)。

  • 定理1 若图G是平面图,则G的任何子图都是平面图。
  • 定理2 若图G是平面图,则在G中加平行边和自身环后得到的图还是平面图。
  • 定理3 平面图G中所有区域的度数之和等于边数m的两倍,即:

  • 定理4 设G为n(n≥3)阶简单连通的平面图,G为极大平面图,当且仅当G的每个区域的度数均为3。

根据定理4可以判定图7(a)和7(b)为一般平面图,图7(c)为极大平面图。

平面图G与它的对偶图G*的顶点数,边数和区域数有如下定理给出的关系。

  • 定理5 设G*是连通平面图G的对偶图,n*m*r*和n、m、r分别为G*和G的顶点数、边数和面数,则有:①n*=r,m*=m;②r*=n;③设G*的顶点位于G的区域Ri中,则deg()=deg(Ri),即对偶图中顶点的度数等于平面图中区域Ri的度数。

欧拉公式及其应用

欧拉公式

欧拉在研究凸多面体时发现:凸多面体顶点数减去棱数加上面数等于2。图8分别画出了正四面体、正六面体、正八面体和正十二面体。以正十二面体为例,其顶点(即棱角)数为20,棱数为30,面数为12,即:20-30+12=2。

后来欧拉又发现:连通平面图的阶数、边数、区域个数之间也存在同样的关系。这就是欧拉公式。

定理6(欧拉公式) 如果G是一个阶为n、边数为m且含有r个区域的连通平面图,则有恒等式:

例如,对于图5(a)所示的连通平面图,其阶为9,边数为13,含有6个区域,则:9-13+6=2。

定理7(欧拉公式的推广) 对于具有k(k≥2)个连通分支的平面图G,有:n-m+r=k+1。其中,n、m、r分别为G的阶数、边数和区域数。

欧拉公式的应用

以下通过一道ACM/ICPC试题的分析,详细介绍欧拉公式的应用。

例1 美好的欧拉回路(That Nice Euler Circuit)

  • 题目来源:

Asia 2004, Shanghai (Mainland China), ZOJ2394, POJ2284

  • 题目描述:

Joey发明了一种名为欧拉(为了纪念伟大的数学家欧拉)的画图机器。在Joey上小学时,他知道了欧拉是从一个著名的问题开始研究图。这个问题是在一张纸上一笔画出一个图形(笔尖不离开纸面),并且笔尖要回到起点。欧拉证明了当且仅当画出的平面图形具备以下两个属性,才能按照要求画出这种图形:①图形是连通的;②每个顶点度数为偶数。

Joey的欧拉机器也是这样工作的。机器中包含了一支与纸面接触的铅笔,机器的控制中心发出一系列指令指示铅笔如何画图。纸面可以看成是无限的二维平面,也就是说不必担心笔尖会超出边界。

开始画图时,机器发出一条指令,格式为(X0,Y0),这意味着铅笔将移动到起点(X0,Y0)。接下来的每条指令的格式均为(X′,Y′),表示铅笔将从当前位置移动到新位置(X′,Y′),从而在纸面上画出一条线段。新位置与前面每条指令中的位置都不相同。最后,欧拉机器总是发出一条指令,将铅笔移动到起点(X0,Y0)。另外,欧拉机器画出来的线绝不会重叠,但有可能会相交。

当所有指令发布并执行后,在纸上已经画出一个完美的图形,由于笔尖没有离开纸面,画出来的图形可以看成是一个欧拉回路。

试计算这个欧拉回路将平面分成了多少个区域。

  • 输入描述:

输入文件中至多包含25个测试数据。每个测试数据的第1行为一个整数N,N≥4,表示测试数据中指令的数目;接下来有N对整数,每对整数占一行,用空格隔开,表示每条指令中的位置;第1对整数为起点位置。假定每个测试数据中指令的数目不超过300,所有位置的坐标范围在(-300,300)。N=0表示输入结束。

  • 输出描述:

对每个测试数据,输出一行,格式为:"Case x: There are w pieces."。其中x为测试数据的序号,从1开始计起。

注意:样例输入所描述的两个例子如图9所示。

  • 分析:

本题要根据平面图的欧拉定理“n-m+r=2”来求解区域个数r。

顶点个数的计算:两两线段求交点,每个交点都是图中的顶点。

边数的计算:在求交点时判断每个交点落在几条边上,如果一个交点落在一条边上,这条边就分裂成两条边,边数加1。

求得顶点个数和边数后,根据欧拉定理即可求得区域个数。

代码如下:


平面图的判定

本节介绍判定一个图是否为平面图的一些结论和定理。

定理8 如果G是一个阶n≥3,边数为m的平面图,则m≤3n-6。证明略。

该定理给出了一个图是平面图的必要条件。从另一个角度看,这也是一个图是非平面图的充分条件。因此,可以得到定理8的逆否命题:

推论1 如果G是一个阶n≥3,边数为m>3n-6的图,则图G是非平面图。

根据此推论,可以判定图10(a)和10(b)都是非平面图。其中,在图10(a)中,顶点数n=7,边数m=16>3×7-6;在图10(b)中,顶点数n=6,边数m=13>3×6-6。

从定理8还可以得到以下推论。

  • 推论2 每个平面图含有一个度小于或等于5的顶点。
  • 推论3 5阶完全图K5是非平面图。(实际上,5阶以上的完全图都是非平面图。)

注意定理8中的条件并不是充分条件,例如对K3,3来说,由于有6个顶点、9条边,因此3×6-6≥9,即满足3n-6≥m,但可以证明K3,3是非平面图。

K5和i3,3不是平面图这个结论可以用来判定任何一个图是否是平面图,这就是下面将要介绍的Kuratowski定理和Wagner定理。

在图11中,可以看到,在给定图G的边上,插入一个新的度数为2的顶点,使一条边分成两条边(如图11(a)和图11(c)所示);或者对于关联于一个度数为2的顶点的两条边,去掉这个顶点,使两条边化成一条边(如图11(b)和图11(d)所示),这些都不会影响图的平面性。

2度顶点内同构:给定两个图G1和G2,如果它们是同构的,或者可以通过反复插入和(或)去掉度数为2的顶点后,使得G1和G2同构,则称G1和G2是在2度顶点内同构的。

定理9(Kuratowski定理) 一个图是平面图,当且仅当它不包含与K3,3或K5在2度结点内同构的子图。

K3,3和K5常被称作库拉托夫斯基(Kuratowski)图。

另外,还可以通过收缩边来判定一个图是否是平面图。

收缩:设e是图G的一条边,从G中删去e并将e的两个顶点合并,删去由此得到的环边和平行边,这个过程称为边e的收缩。若图G1可通过一系列边的收得到与G2同构的图,则称G1可以收缩到G2。注意,收缩边e并不要求e的两个顶点的度数为2。

定理10(Wagner定理) 图G是平面图,当且仅当G中既没有可收缩到K5的子图,也没有可收缩到K3,3的子图。

彼得森图(Peterson,如图12所示)可收缩到K5,如在12(a)中,将粗线边收缩,则彼得森图变成了K5。因此,根据Wagner定理,可以判定彼得森图为非平面图。

参考文档