《第61讲 平面图课件》由会员分享，可在线阅读，更多相关《第61讲 平面图课件（26页珍藏版）》请在金锄头文库上搜索。
1、离散数学,第61讲 平面图,第7章 几类特殊的图,7.5 平面图,本讲内容,7.5 平面图,本节仅讨论无向图. 单层印刷电路版、集成电路的布线等涉及平面图. 平面图与地图着色问题也密切相关.,1. 平面图的有关概念 Def 设G是无向图, 若可将G画在一个平面上, 使得任意两条边仅仅在节点处才相交, 则称G是可平面图或简称G为平面图(planar graph). 不能画在曲面上? 平面表示? 由于一个平面图与其平面表示是同构的, 因此平面图通常是指其平面表示.,两个重要的非平面图的例子: (1) K5. (2) K3,3.,Def 设G是平面图,由G的若干条边所围成的连通区域称为图G的面(fa
2、ce), 围成面的(回路所在的)边称为面的边界(boundary). 一个区域是连通的, 是指其内部不包含该图的任何边.,理解平面图的面: 在一张较大的纸上将平面图画上, 然后用剪刀将图的所有边剪破, 这张纸被分成的每一部分就是一个面. 围墙?,特别注意, 任何平面图都有一个由若干条边往外围成的一个面,它是唯一的一个无限面. 平面图的两个面相邻是指这两个面有公共的边界.,2. Euler公式 Theorem (Euler公式)任意(n, m)连通平面图的面数r = m n +2. Proof 对面数r归纳. r = 1. r 2 圈C. 去掉C上的一条边e. G e. Remark 在Eule
3、r公式中, “连通”的条件是必不可少的.,Corollary 1 任意(n, m)简单平面图, 若n 3, 则m 3n - 6. n3? 不妨设G连通, 否则考虑其连通分支. 由于对于n2(n7)的简单图有m3n, 若存在连通分支的节点个数n3, 就有边数m 3n 6, 结论成立. 假设每个连通分支的节点个数均2.,若存在两个连通分支的节点个数为2, 则这两个连通分支的边数2 34 6, 结论成立. 若节点个数为2的连通分支仅一个或没有,结论也成立.,例7-16 证明: K5不是平面图. Hint 反证. 10 35 6?,Corollary 2 任意(n, m)简单平面图, 若G不含K3子图
4、且n 3, 则m 2n - 4. 例7-17 证明: K3,3不是平面图. Hint 反证. 9 26 4? 更一般的结论: 习题7.5 7.,下面的定理是证明“五色定理”的关键. Theorem 任何简单平面图必存在一个度数5 的节点. Proof 不妨设n 3. 假设vV, deg(v) 6.,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*不同构.,小结与作业,Any Questions,?,Thank You !,
