《图论》第5章平面图ppt课件.ppt
《《图论》第5章平面图ppt课件.ppt》由会员分享,可在线阅读,更多相关《《图论》第5章平面图ppt课件.ppt(21页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、1 可平面性可平面性 一个图一个图 G=(V,E) ,若能将其画在平面上,若能将其画在平面上,且任意两条边的交点只能是且任意两条边的交点只能是G的顶点,则称的顶点,则称G可嵌可嵌入平面,或称入平面,或称G是可平面的。可平面图在平面上是可平面的。可平面图在平面上的一个嵌入称为一个平面图。的一个嵌入称为一个平面图。树是一类重要的平面图。树是一类重要的平面图。应用举例:印刷电路版、集成电路设计。应用举例:印刷电路版、集成电路设计。5.1 5.1 平面图及其性质平面图及其性质2 区域区域 由平面图的边包围而成,其中不含图的顶点。由平面图的边包围而成,其中不含图的顶点。也称为面。包围域也称为面。包围域R
2、的所有边组成的回路称为该的所有边组成的回路称为该域的边界,回路长度称为该域的度,记为域的边界,回路长度称为该域的度,记为deg(R)。5.1 5.1 平面图及其性质平面图及其性质v2R1R2R0v1v3v4v5v6v7各域的边界:各域的边界:R0: v1 v2 v4 v5 v7 v7 v4 v3 v1R1: v1 v2 v4 v3 v1R2: v4 v5 v7 v4 v6 v4R3: v7 v7 例例deg(R0)=8, deg(R1)=4, deg(R2)=5, deg(R3)=1R33 内部面和外部面内部面和外部面 由平面图的边包围且无穷大的域称由平面图的边包围且无穷大的域称为外部面。(如
3、上例的域为外部面。(如上例的域R0为外部面)为外部面)一个平面图有且只有一个外部面。一个平面图有且只有一个外部面。 曲面嵌入曲面嵌入 一个图可嵌入平面当且仅当它可嵌入曲面一个图可嵌入平面当且仅当它可嵌入曲面.5.1 5.1 平面图及其性质平面图及其性质1deg()2riiRm 定理定理5-1-15-1-1 平面图平面图G的所有域的度之和等于其边数的所有域的度之和等于其边数m的的2倍,即:倍,即:4 定理定理5-1-2 5-1-2 欧拉公式欧拉公式 设平面连通图设平面连通图G有有n个顶点,个顶点,m条边,条边,d个域,则有个域,则有 n- -m+d = 2。证明证明1 对对m作归纳。作归纳。证明
4、证明2 对对d作归纳。作归纳。欧拉公式对非简单图仍然成立。欧拉公式对非简单图仍然成立。 推论推论 设平面图设平面图G的连通分支数为的连通分支数为k,并有,并有n个顶点,个顶点,m条边,条边,d个域,则有个域,则有 n- -m+d = k+1。5.1 5.1 平面图及其性质平面图及其性质5 极大平面图极大平面图 设设G=(V,E)为简单平面图,为简单平面图,|V| 3,若对,若对任意任意vi ,vj V,且,且 (vi ,vj) E,有,有G =(V, E (vi ,vj)为非平面图,则称为非平面图,则称G为一个极大平面图。为一个极大平面图。“极大性极大性”乃针对固定顶点数的图的边的数目而乃针对
5、固定顶点数的图的边的数目而言。言。5.1 5.1 平面图及其性质平面图及其性质6 极大平面图的性质极大平面图的性质 1.极大平面图是连通图。极大平面图是连通图。2.极大平面图的每个面都由极大平面图的每个面都由3条边组成。条边组成。3.极大平面图有极大平面图有3d=2m(d为面数目,为面数目,m 为边数目)。为边数目)。4.极大平面图极大平面图G=(V, E),若,若|V| 4,则,则 vi V,有,有 deg(vi ) 3。证明证明5.1 5.1 平面图及其性质平面图及其性质7 定理定理5-1-35-1-3 设极大平面图设极大平面图G有有n个顶点,个顶点,m条边,条边,d个域,则有个域,则有m
6、=3n- -6,d=2n- -4。证明证明 将将3d=2m代入欧拉公式。代入欧拉公式。 推论推论 简单平面图简单平面图G有有 m 3n- -6,d 2n- -4。 定理定理5-1-45-1-4 简单平面图至少有一个顶点的度小于简单平面图至少有一个顶点的度小于6。 证明证明 设任一点的度设任一点的度 6,得,得 m 3n,矛盾。,矛盾。5.1 5.1 平面图及其性质平面图及其性质8 二部图二部图 图图G=(V, E),若,若V可划分成可划分成V1和和V2 两部分,两部分,使得:使得: v1 V1,若,若( v1, v2 ) E ,则必,则必v2 V2 ; v2 V2,若,若( v1, v2 )
7、E ,则必,则必v1 V1 。 则称则称G为一个二部图。为一个二部图。5.1 5.1 平面图及其性质平面图及其性质例例9 完全二部图完全二部图 设设G=(V, E)为一个二部图,为一个二部图, V1和和V2 如如上所述,若上所述,若 ( v1 ) ( v2 )(v1 V1 , v2 V2 ( v1, v2 ) E), 则称则称G为一个完全二部图,记为为一个完全二部图,记为 Kn1, n2。 ( n1 =|V1| ,n2 =| V2 |)5.1 5.1 平面图及其性质平面图及其性质例例 K3,310 定理定理5-1-55-1-5 K5 和和K3,3 是不可平面的。是不可平面的。 证明证明 反证法
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 图论 平面图 ppt 课件
限制150内