第61讲平面图ppt课件

离散数学离散数学第第61讲讲 平面图平面图第第7章章 几类特殊的图几类特殊的图7.5 平面图平面图本讲内容本讲内容平面图的有关概念平面图的有关概念1Euler公式公式2Kuratowski定理定理3平面图的对偶图平面图的对偶图47.5 平面图平面图 本节仅讨论无向图本节仅讨论无向图.单层印刷电路版、集成电路的布线等涉及单层印刷电路版、集成电路的布线等涉及平面图平面图.平面图与地图着色问题也亲密相关平面图与地图着色问题也亲密相关.1.平面图的有关概念平面图的有关概念 Def 设设G是无向图是无向图,假设可将假设可将G画在一个平面画在一个平面上上,使得恣意两条边仅仅在节点处才相交使得恣意两条边仅仅在节点处才相交,那么称那么称G是可平面图或简称是可平面图或简称G为平面图为平面图(planar graph).不能画在曲面上不能画在曲面上?平面表示平面表示?由于一个平面图与其平面表示是同构的由于一个平面图与其平面表示是同构的,因因此平面图通常是指其平面表示此平面图通常是指其平面表示.两个重要的非平面图的例子:(1)K5.(2)K3,3.Def 设设G是平面图是平面图,由由G的假设干条边所围成的假设干条边所围成的连通区域称为图的连通区域称为图G的面的面(face),围成面的围成面的(回路所在的回路所在的)边称为面的边境边称为面的边境(boundary).一个区域是连通的一个区域是连通的,是指其内部不包含该图是指其内部不包含该图的任何边的任何边.了解平面图的面了解平面图的面:在一张较大的纸上将平面在一张较大的纸上将平面图画上图画上,然后用剪刀将图的一切边剪破然后用剪刀将图的一切边剪破,这这张纸被分成的每一部分就是一个面张纸被分成的每一部分就是一个面.围墙围墙?特别留意特别留意,任何平面图都有一个由假设干条任何平面图都有一个由假设干条边往外围成的一个面边往外围成的一个面,它是独一的一个无限它是独一的一个无限面面.平面图的两个面相邻是指这两个面有公共平面图的两个面相邻是指这两个面有公共的边境的边境.2.Euler公式公式 Theorem(Euler公式公式)恣意恣意(n,m)连通平面图连通平面图的面数的面数r=m n+2.Proof 对面数对面数r归纳归纳.r=1.r 2 圈圈C.去掉去掉C上的一条边上的一条边e.G e.Remark 在在Euler公式中公式中,“连通的条件是连通的条件是必不可少的必不可少的.2)1(1nmr Corollary 1 恣意恣意(n,m)简单平面图简单平面图,假设假设n 3,那么那么m 3n-6.n3?无妨设无妨设G连通连通,否那么思索其连通分支否那么思索其连通分支.由于对于由于对于n2(n7)的简单图有的简单图有m3n,假设假设存在连通分支的节点个数存在连通分支的节点个数n3,就有边数就有边数m 3n 6,结论成立结论成立.假设每个连通分支的节假设每个连通分支的节点个数均点个数均2.假设存在两个连通分支的节点个数为假设存在两个连通分支的节点个数为2,那那么这两个连通分支的边数么这两个连通分支的边数2 34 6,结论结论成立成立.假设节点个数为假设节点个数为2的连通分支仅一个或没有的连通分支仅一个或没有,结论也成立结论也成立.2)2(3mnm 例例7-16 证明证明:K5不是平面图不是平面图.Hint 反证反证.10 35 6?Corollary 2 恣意恣意(n,m)简单平面图简单平面图,假设假设G不含不含K3子图且子图且n 3,那么那么m 2n-4.例例7-17 证明证明:K3,3不是平面图不是平面图.Hint 反证反证.9 26 4?更普通的结论更普通的结论:习题习题7.5 7.2)2(4mnm 下面的定理是证明下面的定理是证明“五色定理的关键五色定理的关键.Theorem 任何简单平面图必存在一个度数任何简单平面图必存在一个度数5 的节点的节点.Proof 无妨设无妨设n 3.假设假设vV,deg(v)6.).63(22)deg(6nmvnVv 3.Kuratowski定理定理 Def 假设两个图是同构的假设两个图是同构的,或者经过反复进或者经过反复进展以下操作使得它们同构展以下操作使得它们同构,那么称这两个图那么称这两个图同胚同胚(homeomorphism):Theorem(Kuratowski,1930)无向图无向图G是平是平面图的充要条件是面图的充要条件是G无同胚于无同胚于K5和和K3,3的的子图子图.例例8-18 证明证明:Petersen图不是平面图图不是平面图.习题7.5 5:利用Euler公式证明.4.平面图的对偶图平面图的对偶图 对平面图对平面图G的面的研讨可以转换为对其对偶的面的研讨可以转换为对其对偶图图G*的节点的研讨的节点的研讨.根据定义知根据定义知,恣意平面图的对偶图是平面图恣意平面图的对偶图是平面图且是连通的且是连通的.设设G是是(n,m)平面图平面图,有有r个面个面,那么那么G*是是(r,m)平面图平面图,G*有有n个面个面.对于连通平面图对于连通平面图G,其对偶图为其对偶图为G*,这时这时G*的对偶图的对偶图G*为本身为本身.对于非连通平面图对于非连通平面图G,能够能够G与与G*不同构不同构.小结与作业小结与作业了解平面图的有关概念了解平面图的有关概念掌握掌握Euler公式及其推论公式及其推论了解了解Kuratowski定理定理了解平面图的对偶图了解平面图的对偶图习题习题7.5 3,4,5作业作业Any Questions?