欢迎来到三一办公! | 帮助中心 三一办公31ppt.com(应用文档模板下载平台)
三一办公
全部分类
  • 办公文档>
  • PPT模板>
  • 建筑/施工/环境>
  • 毕业设计>
  • 工程图纸>
  • 教育教学>
  • 素材源码>
  • 生活休闲>
  • 临时分类>
  • ImageVerifierCode 换一换
    首页 三一办公 > 资源分类 > PPT文档下载  

    《离散完整》PPT课件.ppt

    • 资源ID:5563720       资源大小:319KB        全文页数:19页
    • 资源格式: PPT        下载积分:15金币
    快捷下载 游客一键下载
    会员登录下载
    三方登录下载: 微信开放平台登录 QQ登录  
    下载资源需要15金币
    邮箱/手机:
    温馨提示:
    用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)
    支付方式: 支付宝    微信支付   
    验证码:   换一换

    加入VIP免费专享
     
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,就可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰。
    5、试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。

    《离散完整》PPT课件.ppt

    1,8.4 平面图,平面图与平面嵌入平面图的面、有限面、无限面面的次数极大平面图极小非平面图欧拉公式平面图的对偶图,2,平面图和平面嵌入,定义 如果能将图G除顶点外边不相交地画在平面上,则称G是平面图.这个画出的无边相交的图称作G的平面嵌入.没有平面嵌入的图称作非平面图.例如 下图中(1)(4)是平面图,(2)是(1)的平面嵌入,(4)是(3)的平面嵌入.(5)是非平面图.,3,平面图和平面嵌入(续),今后称一个图是平面图,可以是指定义中的平面图,又可以是指平面嵌入,视当时的情况而定.当讨论的问题与图的画法有关时,是指平面嵌入.K5和K3,3是非平面图设G G,若G为平面图,则G 也是 平面图;若G 为非平面图,则G也 是非平面图.Kn(n5),K3,n(n3)都是非平面图.平行边与环不影响图的平面性.,4,平面图的面与次数,设G是一个平面嵌入G的面:由G的边将平面划分成的每一个区域无限面(外部面):面积无限的面,用R0表示有限面(内部面):面积有限的面,用R1,R2,Rk表示 面Ri的边界:包围Ri的所有边构成的回路组面Ri的次数:Ri边界的长度,用deg(Ri)表示 说明:构成一个面的边界的回路组可能是初级回路,简单回路,也可能是复杂回路,还可能是非连通的回路之并.定理 平面图各面的次数之和等于边数的2倍.,5,平面图的面与次数(续),例1 右图有4个面,deg(R1)=1,deg(R2)=3,deg(R3)=2,deg(R0)=8.请写各面的边界.,例2 左边2个图是同一个平面图的平面嵌入.R1在(1)中是外部面,在(2)中是内部面;R2在(1)中是内部面,在(2)中是外部面.其实,在平面嵌入中可把任何面作为外部面.,6,极大平面图,定义 若G是简单平面图,并且在任意两个不相邻的顶点之间加一条新边所得图为非平面图,则称G为极大平面图.性质若简单平面图中已无不相邻顶点,则是极大平面图.如 K1,K2,K3,K4都是极大平面图.极大平面图必连通.阶数大于等于3的极大平面图中不可能有割点和桥.设G为n(n3)阶极大平面图,则G每个面的次数均为3.任何n(n4)阶极大平面图G均有(G)3.,7,实例,3个图都是平面图,但只有右边的图为极大平面图.,8,极小非平面图,定义 若G是非平面图,并且任意删除一条边所得图都是平面图,则称G为极小非平面图.说明:K5,K3,3都是极小非平面图 极小非平面图必为简单图下面4个图都是极小非平面图,9,欧拉公式,定理8.11(欧拉公式)设G为n阶m条边r个面的连通平面图,则 nm+r=2.证 对边数m做归纳证明.m=0,G为平凡图,结论为真.设m=k(k0)结论为真,m=k+1时分情况讨论如下:(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时结论成立.(2)否则,删除一个圈上的一条边,记作G.G 连通,有n个顶点,k条边和r-1个面.由归纳假设,n-k+(r-1)=2,即n-(k+1)+r=2,得证m=k+1时结论也成立.证毕.,10,欧拉公式(续),欧拉公式的推广 设G是有 p(p2)个连通分支的平面图,则 n m+r=p+1证 设第 i 个连通分支有 ni个顶点,mi 条边和 ri 个面.对各连通分支用欧拉公式,ni mi+ri=2,i=1,2,p求和并注意 r=r1+rp+p1,即得 n m+r=p+1,11,与欧拉公式有关的定理,12,与欧拉公式有关的定理(续),定理:设G为有 p(p2)个连通分支的平面图,且每个面的次数不小于l(l 3),则定理 设G为简单平面图,则(G)5.,13,同胚与收缩,消去2度顶点v 如上图从(1)到(2)插入2度顶点v 如上图从(2)到(1)G1与G2同胚:G1与G2同构,或经过反复插入、或消去2度顶点后同构收缩边e 如下图从(1)到(2),14,库拉图斯基定理,定理 G是平面图G中不含与K5同胚的子图,也不含与K3,3同胚的子图.定理 G是平面图G中无可收缩为K5的子图,也无可收缩为K3,3的子图.,15,非平面图证明,例 证明下述2个图均为非平面图.证,图中红色部分分别与K3,3和 K5 同胚,16,平面图的对偶图,定义 设平面图G,有n个顶点,m条边和r个面,构造G的对偶图G*=如下:在G的每一个面Ri中任取一个点vi*作为G*的顶点,V*=vi*|i=1,2,r.对G每一条边ek,若ek在G的面Ri与Rj的公共边界上,则作边ek*=(vi*,vj*),且与ek相交;若ek为G中的桥且在面Ri的边界上,则作环ek*=(vi*,vi*).E*=ek*|k=1,2,m.,17,平面图的对偶图(续),例 黑色实线为原平面图,红色虚线为其对偶图,18,平面图的对偶图(续),性质:G*是平面图,而且是平面嵌入.G*是连通图若边e为G中的环,则G*与e对应的边e*为桥;若e为桥,则G*中与e对应的边e*为环.在多数情况下,G*含有平行边.同构的平面图的对偶图不一定同构.上面两个平面图是同构的,但它们的对偶图不同构.,19,平面图与对偶图的阶数、边数与面数之间的关系:设G*是平面图G的对偶图,n*,m*,r*和n,m,r分别为G*和G的顶点数、边数和面数,则(1)n*=r(2)m*=m(3)r*=n-p+1,其中p是G的连通分支数(4)设G*的顶点vi*位于G的面Ri中,则d(vi*)=deg(Ri),平面图的对偶图(续),

    注意事项

    本文(《离散完整》PPT课件.ppt)为本站会员(小飞机)主动上传,三一办公仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知三一办公(点击联系客服),我们立即给予删除!

    温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




    备案号:宁ICP备20000045号-2

    经营许可证:宁B2-20210002

    宁公网安备 64010402000987号

    三一办公
    收起
    展开