复试2离散结构_第1页
复试2离散结构_第2页
复试2离散结构_第3页
复试2离散结构_第4页
复试2离散结构_第5页
已阅读5页,还剩16页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

8.4

平面图–平面图与平面嵌入–平面图的面及其次数–极大平面图–极小非平面图–欧拉公式–库拉图斯基定理–平面图的对偶图1平面图与非平面图定义8.6如果能将图G除顶点外边不相交地画在平面上,则称G是平面图.这个画出的无边相交的图称作G的平面嵌入.没有平面嵌入的图称作非平面图.例如下图中(1)~(4)是平面图,(2)是(1)的平面嵌入,(4)是(3)的平面嵌入.(5)是非平面图.23平面图的面与次数设G是一个平面嵌入G的面:由G的边将平面划分成的每一个区域无限面(外部面):面积无限的面,用R0表示有限面(内部面):面积有限的面,用R1,R2,…,Rk表示面Ri的边界:包围Ri的所有边构成的回路组面Ri的次数:Ri边界的长度,用deg(Ri)表示说明:构成一个面的边界的回路组可能是初级回路,简单回路,也可能是复杂回路,甚至还可能是非连通的回路之并.实例例1

右图有4

个面R1的边界:R2的边界:R3的边界:R0的边界:abcefgabcdde,

fgdeg(R1)=1deg(R2)=3deg(R3)=2deg(R0)=84实例例2右边2个图是同一平面图的平面嵌入.R1在(1)中是外部面,在(2)中是内部面;R2在(1)中是内部面,

在(2)中是外部面.说明:(1)一个平面图可以有多个不同形式的平面嵌入,它们都同构.(2)可以通过变换(测地投影法)把平面图的任何一面作为外部面R2(1)R1R3(2)5R2

R1R36平面图的面与次数(续)定理8.9

平面图各面的次数之和等于边数的2倍证一条边或者是2个面的公共边界,或者在一个面的边界中出现2次.在计算各面的次数之和时,每条边恰好被计算

2次.极大平面图定义8.8若G是简单平面图,且在任意两个不相邻的顶点之间加一条新边所得图为非平面图,则称G为极大平面图例如K1,K2,K3,K4都是极大平面图(1)是K5删去一条边,

是极大平面图.

(2)、(3)不是.(1)7(2)(3)极大平面图的性质极大平面图是连通的

设G为n(n‡3)阶简单图,G为极大平面图的充分必要条件是,G每个面的次数均为3.例如极大平面图8外部面的次数为4非极大平面图极小非平面图定义8.8若G是非平面图,并且任意删除一条边所得图都是平面图,则称G为极小非平面图例如K5,K3,3都是极小非平面图下述4个图也都是极小非平面图910欧拉公式定理8.10

设G为n阶m条边r个面的连通平面图,则n-m+r=2证

对边数m做归纳证明.

m=0,

G为平凡图,结论成立.设m=k(k‡0)时结论成立,

对m=k+1,若G中无圈,则G必有一个度数为1的顶点v,删除v及关联的边,记作G¢.

G¢连通,有n-1个顶点,k条边和r个面.由归纳假设,

(n-1)-k+r=2,

即n-(k+1)+r=2,

得证m=k+1时结论成立.否则,删除一个圈上的一条边,记作G¢.

G¢连通,有n个顶点,k条边和r-1个面.由归纳假设,n-k+(r-1)=2,即n-(k+1)+r=2.得证m=k+1时结论也成立.

证毕.11欧拉公式(续)推论设平面图G有p

(p‡2)个连通分支,则n

-

m

+

r

=

p

+

1其中n,m,r

分别是G的阶数,边数和面数.证设第i

个连通分支有ni个顶点,mi条边和ri个面.对各连通分支用欧拉公式,ni

-

mi

+

ri

=2,

i

=

1,

2,

,

p求和并注意r

=r1+…+rp

-p+1,即得n

-

m

+

r

=

p

+

1欧拉公式(续)定理8.11设G为n阶连通平面图,有m条边,且每个面的次数不小于l

(l

‡3),

则证由各面次数之和等于边数的2倍及欧拉公式得2m

lr

=

l

(2+m-

n)可解得所需结论.(n

-

2)12l

-

2m

£l实例例3证明K5和K3,3不是平面图证K5

:n=5,

m=10,

l=3K3,3

:

n=6,

m=9,

l=4不满足定理8.11的条件例4

设简单连通平面图有n(n‡3)个顶点、m条边,则m£3n-6证不难证明3阶以上的简单连通平面图每个面的次数至少为3,

由定理8.11立即得到要证的结论.13同胚与收缩消去2度顶点v如图从(1)到(2)插入2度顶点v

如图从(2)到(1)G1与G2同胚:G1与G2同构,或经过反复插入、或消去2度顶点后同构收缩边e

如图从(3)到(4)(3)14(4)15库拉图斯基(Kuratowski)定理定理8.13

一个图是平面图当且仅当它既不含与K5同胚的子图,

也不含与K3,3同胚的子图.定理8.14

一个图是平面图当且仅当它既无可收缩为K5的子图,

也无可收缩为K3,3的子图.实例也与K3,3同胚可收缩到K3,3例5

证明下面2个图均为非平面图.与K5同胚也可收缩到K51617对偶图定义8.11设平面图G有n个顶点,m条边和r个面,G的对偶图G*=<V*,E*>构造如下:在G的每一个面Ri中任取一个点vi*作为G*的顶点,V*=

{

vi*|

i=1,2,…,r

}.对G每一条边ek,若ek在G的面Ri与Rj的公共边界上,则作边

ek*=(vi*,vj*),

且与ek相交;若ek只在面Ri的边界上,则作环

ek*=(vi*,vi*).

E*={

ek*|

k=1,2,…,m

}.实例性质G*是平面图,而且是平面嵌入.G*是连通的.若e为G中的环,则G*中e*为桥;若e为桥,则G*中e*为环.同构的平面图的对偶图不一定同构.如(1)和(3)(1)(2)(3)1819对偶图(续)定理8.15

设G*是连通平面图G的对偶图,n*,

m*,

r*和n,m,r分别为G*和G的顶点数、边数和面数,则n*=

rm*=mr*=n设G*

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论