《图论及其应用》PPT课件.ppt

《《图论及其应用》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《图论及其应用》PPT课件.ppt（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Email:图论及其应用图论及其应用任课教师：杨春任课教师：杨春数学科学学院数学科学学院1本次课主要内容本次课主要内容(一一)、涉及算法的相关概念、涉及算法的相关概念(二二)、平面性算法、平面性算法平面性算法平面性算法2 关于图的平面性问题，我们已经建立了一些平面性关于图的平面性问题，我们已经建立了一些平面性判定方法：判定方法：(一一)、涉及算法的相关概念、涉及算法的相关概念 (1)对于简单图对于简单图G=(n,m)，如果，如果m3n-6，则，则G是非可是非可平面的；平面的；(2)对于连通图对于连通图G=(n,m)，如果每个面次数至少为，如果每个面次数至少为l3,且且m(n-2)l/(l-2)

2、，则，则G是非可平面的；是非可平面的；(3)库拉托斯基定理：库拉托斯基定理：G是可平面的当且仅当是可平面的当且仅当G不含有不含有与与K5或或K3,3同胚的子图；同胚的子图；(4)瓦格纳定理：瓦格纳定理：G是可平面的当且仅当是可平面的当且仅当G不含有能够不含有能够收缩成收缩成K5或或K3,3的子图；的子图；3 上面的判定方法，局限性很大。这次课我们将给出上面的判定方法，局限性很大。这次课我们将给出一个算法，其作用是：如果一个算法，其作用是：如果G非可平面，通过算法可以非可平面，通过算法可以得到判定；如果得到判定；如果G是可平面图，通过算法，可以给出一是可平面图，通过算法，可以给出一种平面嵌入形式

3、。种平面嵌入形式。定义定义1 设设H是是G的一个子图，在的一个子图，在E(G)-E(H)中定义一中定义一个二元关系个二元关系“”:”:(1)e1与与e2分别是分别是W的始边和终边，且的始边和终边，且 (2)W的内点与的内点与H不能相交。不能相交。Ge4e3e2e1e7e6e54 定义定义2 设设B是是E(G)-E(H)关于二元关系关于二元关系“”的等价类的等价类在在G中的边导出子图，则称中的边导出子图，则称B是是G关于子图关于子图H的一座桥。的一座桥。桥与桥与H的公共顶点称为桥的公共顶点称为桥B在在H中的附着顶点。中的附着顶点。例例1 在下图中，红色边在在下图中，红色边在G中导出子图为中导出子

4、图为H。求出。求出G关于关于H的所有桥。的所有桥。GB1B2B3B4Ge4e3e2e1e7e6e55 定义定义3 设设H是图是图G的可平面子图，的可平面子图，是是H的一种平面嵌入。的一种平面嵌入。若若G也是可平面图，且存在也是可平面图，且存在G的一个平面嵌入的一个平面嵌入 ，使得：，使得：称称 是是G容许的。容许的。例例2 在在G中，我们取红色边导出的子图为中，我们取红色边导出的子图为H,并取并取 容易知道：容易知道：是是G容许的。容许的。G6 例例3 在在G中，我们取红色边导出的子图为中，我们取红色边导出的子图为H,并取并取 容易知道：容易知道：不不 是是G容许的。容许的。定义定义4 设设B

5、是是G中子图中子图H的任意一座桥，若的任意一座桥，若B对对H的所有附的所有附着顶点都位于着顶点都位于 的某个面的某个面 f 的边界上，则称的边界上，则称B在面在面 f 内可内可画入，否则，称画入，否则，称B在面在面 f 内不可画入。内不可画入。7 对于对于G的桥的桥B,令：令：例例4 红色边的导出子图是红色边的导出子图是H,如果取如果取 确定确定H的桥在的桥在 中可以画入的面集合。中可以画入的面集合。B3B2B1f3f2f1G 解：解：8 定理定理1 设设 是是G容许的，则对于容许的，则对于H的每座桥的每座桥B:证明：因证明：因 是是G容许的，由定义，存在容许的，由定义，存在G的一个平面嵌的一

6、个平面嵌入入 ，使得：，使得：于是，于是，H的桥的桥B所对应的所对应的 的子图，必然限制在的子图，必然限制在 的的某个面内。所以：某个面内。所以：注：定理注：定理1实际上给出了一个图是可平面图的一个必要条实际上给出了一个图是可平面图的一个必要条件。这个必要条件表明：如果存在件。这个必要条件表明：如果存在G的一个可平面子图的一个可平面子图H,9使得对于某桥使得对于某桥B，有，有 ，那么，那么，G是非是非可平面的。可平面的。根据上面的结论：我们可以按如下方式来考虑根据上面的结论：我们可以按如下方式来考虑G的平面性问题：的平面性问题：先取先取G的一个可平面子图的一个可平面子图H1,其平面嵌入是其平面

7、嵌入是 对于对于H1的每座桥的每座桥B,如果：如果：，则，则G非可非可平面。平面。否则，取否则，取H1的桥的桥B1,作：作：H2=B1HH1 1,再取一个面再取一个面 将将B1画入画入 的面的面 f 中。中。10 如果如果B1可平面，则只要把可平面，则只要把B1平面嵌入后，得到平面嵌入后，得到H2的的平面嵌入平面嵌入 然后再进行上面相同的操作，可以得到然后再进行上面相同的操作，可以得到G的边数的边数递增的子图平面嵌入序列：递增的子图平面嵌入序列：最终，得到可平面图最终，得到可平面图G的一种平面嵌入形式。的一种平面嵌入形式。(二二)、平面性算法、平面性算法 1964年，年，Demoucron,M

8、lgrance和和Pertuiset提出了下面提出了下面的平面性算法，简称的平面性算法，简称DMP算法。算法。11 设设G是至少三个顶点的简单块。是至少三个顶点的简单块。(1)取取G的一个圈的一个圈H1,求出求出H1的一个平面嵌入的一个平面嵌入 。置。置i=1;(2)若若E(G)-E(Hi)=,则停止；否则，确定则停止；否则，确定G G中中H Hi i的所有桥，的所有桥，并对每座桥并对每座桥B B，求出，求出 ；(3)若存在桥若存在桥B,使得：使得：，则停止，则停止(G不可平面不可平面)；否则，在；否则，在Hi的所有桥中确定一个使得的所有桥中确定一个使得 最小的最小的B，并取，并取 。(4)在

9、桥在桥B中取一条连接中取一条连接Hi中两个附着顶点的路中两个附着顶点的路Pi,置置Hi+1=HiPPi i,把把P Pi i画在画在 的面的面 f f 内内,得到得到12 (5)置置i=i+1转转(2)。例例5 用平面性算法考察下图用平面性算法考察下图G的平面性。的平面性。v6v5v4v3v2v1v8v7图图G 解：解：(1)取取G的一个圈的一个圈H1,并作平面嵌入：并作平面嵌入：13v6v5v4v3v2v1v8v7图图G (2)v6v5v4v3v2v1v8v7H1v6v5v4v3v2v1v8v7f1f214v6v5v4v3v2v1v8v7图图G (3)取取B1和和f1.(4)取取P1=v1v

10、3f3v6v5v4v3v2v1v8v7f1f215v6v5v4v3v2v1v8v7图图G (3)取取B2和和f3.(4)取取P2=v2v7v6v5v4v3v2v1v8v7f1f2f316v6v5v4v3v2v1v8v7图图Gv6v5v4v3v2v1v8v7f1f2f3f417 (3)取取B1和和f1.(4)取取P3=v1v4v6v5v4v3v2v1v8v7图图Gv6v5v4v3v2v1v8v7f1f2f3f5f418v6v5v4v3v2v1v8v7图图G (3)取取B1和和f5.(4)取取P4=v2v6v6v5v4v3v2v1v8v7f1f2f3f6f4f519v6v5v4v3v2v1v8v7

11、图图G 继续下去，得到：继续下去，得到：v6v5v4v3v2v1v8v7 算法分析：主要运算包括：算法分析：主要运算包括：20（i）找出块）找出块G中的一个圈中的一个圈Hi；（ii）确定）确定G中中Hi的桥以及它们对于的桥以及它们对于Hi的附着点；的附着点；（iii）对于 的每个面的每个面 f 确定其周界；确定其周界；（iv）对于 的每座桥的每座桥B，确定，确定（v）在）在Hi 的某座桥的某座桥B中求一条起点与终点均为附着点中求一条起点与终点均为附着点的一条路的一条路Pi。可证上述每一个算法均存在好算法，因此平面性算法可证上述每一个算法均存在好算法，因此平面性算法也是好算法。也是好算法。本章部

12、分习题解答本章部分习题解答21 例例1 求证，每个求证，每个5连通简单可平面图至少有连通简单可平面图至少有12个顶点。个顶点。证明：设证明：设G是是5连通图，则：连通图，则：由惠特尼定理得：由惠特尼定理得：所以：所以：另一方面：另一方面：G是是5连通简单可平面图，所以有：连通简单可平面图，所以有：于是得：于是得：即：即：所以：所以：n12。22 例例2 求证，没有求证，没有6连通简单可平面图。连通简单可平面图。证明：若不然，设证明：若不然，设G是是6连通图，则：连通图，则：由惠特尼定理得：由惠特尼定理得：所以：所以：于是得：于是得：这与这与G是简单平面图矛盾。是简单平面图矛盾。例例3 求证：若

13、求证：若G是连通平面图，且所有顶点度数不小于是连通平面图，且所有顶点度数不小于3，则，则G至少有一个面至少有一个面 f，使得：，使得：deg(f)5 5。23 证明：若不然，则：证明：若不然，则：由欧拉公式得：由欧拉公式得：于是得：于是得：另一方面：由另一方面：由(G)3(G)3得：得：2m3n 3n-62m3n 3n-6 这样导出矛盾。这样导出矛盾。例例4 设设G是一个是一个(n,m)图。图。求证：若求证：若G是外可平面图，是外可平面图，且没有三角形，则：且没有三角形，则：m(3n-4)/2(3n-4)/224 证明：由条件易知：证明：由条件易知：由欧拉公式得：由欧拉公式得：于是得：于是得：

14、例例5 设设G是一个是一个(n,m)单图，图单图，图G分解为可平面子图的分解为可平面子图的最少个数称为最少个数称为G的厚度的厚度(G).(G).求证：求证：(1)25 (2)证明证明:(1)当当n=1时，结论成立。时，结论成立。设当设当n3时时，G分解分解为为(G)(G)个可平面子个可平面子图图G Gi i(1i(1i(G)因为每个因为每个Gi是平面单图，于是：是平面单图，于是：所以：所以：26 (2)根据完全图的边数和结论根据完全图的边数和结论(1)，可得到，可得到(2)中不等式。中不等式。又因为又因为K3,K4是平面图，所以是平面图，所以(K(K3 3)=)=(K4)=1，而直接，而直接计

15、算：计算：所以，等式对所以，等式对n=3与与4时也成立！当时也成立！当5n8n8时，时，K Kn n是非是非可平面图。因为存在可平面图。因为存在8 8阶简单可平面图阶简单可平面图G G，其补图也是可，其补图也是可平面图，所以对平面图，所以对5n8，Kn可以分解为两个可平面图，可以分解为两个可平面图，即：即：(Kn)=2(5n8).另一方面：当另一方面：当5n8n8时，直接计算知：时，直接计算知：这就证明了这就证明了(2)。27 说明：习题说明：习题6的的1-9题比较简单，要求自己独立完成。题比较简单，要求自己独立完成。没有讲到的习题，作为参考。没有讲到的习题，作为参考。28 作业作业 P143-146 习题习题6：1-929Thank You!30