离散数学 课件6.4平面图_第1页
离散数学 课件6.4平面图_第2页
离散数学 课件6.4平面图_第3页
离散数学 课件6.4平面图_第4页
离散数学 课件6.4平面图_第5页
已阅读5页，还剩3页未读， 继续免费阅读

下载本文档

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

文档简介

6.4平面图定义

如果把一个无向图G画在平面上，使得除结点处外没有边交叉出现,则称G为平面图。画出的这种不出现边交叉的图称为图G的一个平面表示(平面嵌入)。例

假设有3幢房子，利用地下管道连接3种服务—供水、供电和供气，连接这些服务的条件是管子不能相互交叉，该问题称为3个公共事业问题。问三个公共事业问题的管子连接可以实现吗？解

分别用3个结点表示3幢房子,3个结点表示水源、电源和气源连接点，在表示3幢房子结点和表示水源、电源和气源连接点的结点之间加上表示管子的边，得到图G。这样问题就转化为判断G是否是平面图的问题。显然G为K3,3,由平面图的知识知，G不是平面图，即三个公共事业问题的管子连接是不可能实现的。定义

设G是一个平面表示,G的边将整个平面划分成若干区域,每个区域称为G的一个面,其中面积无限的区域称为无限面或外部面,常记成R0,面积有限的区域称为有限面或内部面。包围面R的所有边构成的回路称为该面的边界,边界的长度称为面R的次数,记为deg(R)。定理

平面图中所有面的次数之和等于边数的2倍。显然，同一个平面图可以有不同形状的平面表示,但它们都是同构的。1750年，欧拉发现任何含有n个结点、m条棱和r个面的凸多面体，都有n−m+r=2成立，这个公式可以推广到平面图。

定理(欧拉公式)设G为任意的连通平面图,若它有n个结点,m条边，r个面。则有n−m+r=2证明

对G的边数m作归纳法。m=0时,G为孤立点,此时n=1,r=1,结论成立。m=1时,如果该边是环，则有n=1，r=2，这时n−m+r=1−1+2=2，结论成立。如果该边不是环，则n=2，r=1，这时n−m+r=2−1+1=2，结论成立。设m=k−1(k>1)时,欧拉公式成立,现证明m=k时结论成立。（1）若G中至少有1个1度结点，删除这个1度结点得到图G1,则G1是连通的，G1中结点的个数n1=n−1,边的条数m1=m−1,面的个数r1=r,由归纳假设n1−m1+r1=2，即

(n−1)−(m−1)+r=2，整理后得n−m+r=2（2）若G中所有顶点的度数大于或等于2,则必有初级回路。设C为一初级回路,在C上任取一条边e,令G2=G-e,由于e在C上,所以G2仍连通。在G2中,结点个数n2=n,m2=m−1,r2=r−1。由归纳假设得到

n−(m−1)+(r−1)=2，整理后得n−m+r=2推论

一个简单连通平面图，它有n个结点，m条边，若m>1，则有m≤3n−6证明

设G有k个面，分别为r1,r2,⋯,rk

，因为G是简单图，所以G的每个面至少由3条边围成，所以G所有面的次数之和deg(r1)+deg(r2)+…+deg(rk)≥3k由于平面图的所有面的次数之和是边数的两倍，2m≥3k，即k≤3m/2，代人欧拉公式有2=n−m+k≤n−m+3m/2整理得m≤3n−

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

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

最新文档

评论

0/150

提交评论