当前位置 : 主页 > 手机开发 > 无线 >

平面图的基本概念及性质

来源:互联网 收集:自由互联 发布时间:2021-06-10
基本概念 平面图: 设无向图G,若能将G画在一个平面上,使得任何两条边仅在顶点处相交,则称G是具有平面性质的图,简称平面图,否则称G是非平面图。 在平面图G中,G的边将其所在

基本概念

平面图:设无向图G,若能将G画在一个平面上,使得任何两条边仅在顶点处相交,则称G是具有平面性质的图,简称平面图,否则称G是非平面图。

 

在平面图G中,G的边将其所在的平面划分成的区域称为,有限的区域称为有限面内部面,无线的区域称为无限面外部面,包围面的边称为该面的边界,包围每个面的所有边组成的回路长度称为该面的次数(桥计算两次)。

由定义易知,

1、如果一条边不是桥,那它必是两个面的公共边界

2、桥只能是一个面的边界

3、两个以一条边为公共边界的面称为相邻的

就有如下的定理:平面图G所有面的次数之和等于边数的两倍(类似于握手定理)。

欧拉公式

定理:设G是一个面数为 f 的(n,m)平面图,则 n-m+f = 2.

:用归纳法证明,对图的边数做归纳

(1) m=0时,由于G是一个连通图,因此G只包含一个孤立顶点,具有一个外部面,1-0+1=2

(2)假设m=k时欧拉公式成立,对m=k+1做归纳。若存在悬挂边,则删去与之相连的悬挂边之后,边数和定点数都减少1而面数不变,因此n-m+f不变

若不存在悬挂边,每个顶点的度数都大于1,图中必定存在回路C,C上任一边都一定是两个面的公共边界,删去此边,这两个面合并为一个面。顶点数不变,边数减1,面数减1,因此n-m+f不变。

 

推论1:设G是一个面数为 f 的(n,m)平面图,且有p个连通分支,则n-m+f = p+1

证:对每个连通分支使用n-m+f即可,p=1时就是欧拉公式

 

推论2:假设G是一个面数为 f 的(n,m)连通简单平面图,n≥3,每个面的次数至少是p(p≥3),则m ≤ (n-2) * p / (p-2)。

证:由之前的定理知,f*p≤2m,带入欧拉公式整理即可

应用:利用该定理可以证明K3,3是非平面图

假设K3,3是平面图,其中最短的回路长度为4,应有9≤(6-2) * 4 / (4-2) = 6,产生矛盾 

 

推论3:设G是一个面数为 f 的(n,m)连通简单图且n≥3,则m≤3n-6.

证:联通简单图不存在重边和自环,所以每个面的次数最少为3,带入定理2中的公式 m≤(n-2) * 3 / 1 = 3n-6

应用:利用该定理可以证明K5是非平面图

假设K5是平面图,由于K5中n=5,m=10,定理有m≤3n-6,即应有10≤3*5-6,产生矛盾。

 

推论4:任何简单连通图平面图中,至少存在一个度数不超过5的顶点。

证:若所有顶点的度数都大于5,由握手定理有6n≤2m,即m≥3n,与推论3 m≤3n-6矛盾

 

这些定理和推论只是图可平面性的必要条件,满足这些条件的图不一定是平面图。

库拉托夫斯基定理

库拉托夫斯基定理给出了判断一个图是否是平面图的充分必要条件

先学习一个概念——同胚

同胚:若图G1和G2是同构的,或者通过反复的插入或删除2度顶点,它们能变成同构,则称G1和G2是同胚的(或称在2度顶点内同构

分享图片

定理:一个无向图是平面图当且仅当它不包含与K3,3或K5同胚的子图。 (证明比较复杂,略)

例如,证明下面的不是平面图

分享图片

(1)删除一些2度顶点及相连的边(如图中虚线所示)

分享图片

(2)发现这是一个K3,3

分享图片

(3)有由理知,不是平面图。

参考链接:

中国大学mooc 刘铎 离散数学 

原文链接:https://www.cnblogs.com/lfri/p/9939463.html

网友评论