图论及其应用(22)

1、1本次课主要内容本次课主要内容(一一)、涉及算法的相关概念、涉及算法的相关概念(二二)、平面性算法、平面性算法平面性算法平面性算法2 关于图的平面性问题，我们建立了一些可平面性判关于图的平面性问题，我们建立了一些可平面性判定方法：定方法：(一一)、涉及算法的相关概念、涉及算法的相关概念 (1) 对于简单图对于简单图G=(n, m)，如果，如果m3n-6，则，则G是非可是非可平面的；平面的； (2) 对于连通图对于连通图G=(n, m)，如果每个面次数至少为，如果每个面次数至少为l3,且且m(n-2)l /(l-2)，则，则G是非可平面的；是非可平面的； (3) 库拉托斯基定理：库拉托斯基定理：

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

3、-E(H)中定义一个中定义一个二元关系二元关系“ ”:”:1212,( )(),e eE GE H ee 当且仅当存在一条途径W,使得： (1) e1与与e2分别是分别是W的始边和终边，且的始边和终边，且 (2) W与与H的内点不能相交。的内点不能相交。 容易验证：上面的关系是容易验证：上面的关系是E(G)-E(H)元间的等价关系。元间的等价关系。4 定义定义2 设设B是是E(G)-E(H)关于二元关系关于二元关系“ ” 的等价类的等价类在在G中的边导出子图，则称中的边导出子图，则称B是是G关于子图关于子图H的一座桥。的一座桥。桥与桥与H的公共顶点称为桥的公共顶点称为桥B在在H中的附着顶点。中

4、的附着顶点。 例例1 在下图中，红色边在在下图中，红色边在G中导出子图为中导出子图为H。求出。求出G关于关于H的所有桥。的所有桥。GGB1B2B3B45 定义定义3 设设H是图是图G的可平面子图，的可平面子图， 是是H的一种平面嵌入。的一种平面嵌入。若若G也是可平面图，且存在也是可平面图，且存在G的一个平面嵌入的一个平面嵌入 ，且：，且： 称称 是是G容许的。容许的。HGHGH 例例2 在在G中，我们取红色边导出的子图为中，我们取红色边导出的子图为H, 并取并取HH 容易知道：容易知道： 是是G容许的。容许的。GGH6 例例3 在在G中，我们取红色边导出的子图为中，我们取红色边导出的子图为H,

5、 并取并取HH 容易知道：容易知道： 不不 是是G容许的。容许的。GH 定义定义4 设设B是是G中子图中子图H的任意一座桥，若的任意一座桥，若B对对H的所有附的所有附着顶点都位于着顶点都位于 的某个面的某个面f的边界上，则称的边界上，则称B在面在面 f 内可画内可画入，否则，称入，否则，称B在面在面 f 内不可画入。内不可画入。H7 对于对于G的桥的桥B,令：令： 例例4 红色边的导出子图是红色边的导出子图是H,如果取如果取 确定确定H的桥在的桥在 中可以画入的面集合。中可以画入的面集合。 ( ,)F B Hf fHBf是 的面，且 在 内可画入=H HHB3B2B1f3f2f1G123(,)

6、,F B Hff 解：解：2(,)F B H 33(,)F B Hf8 定理定理1 设设 是是G容许的，则对于容许的，则对于H的每座桥的每座桥B:H( ,)F B H 证明：因证明：因 是是G容许的，由定义，存在容许的，由定义，存在G的一个平面嵌的一个平面嵌入入 ，使得：，使得：HGHG 于是，于是，H的桥的桥B所对应的所对应的 的子图，必然限制在的子图，必然限制在 的的某个面内。所以：某个面内。所以：GH( ,)F B H 注：定理注：定理1实际上给出了一个图是可平面图的一个必要条实际上给出了一个图是可平面图的一个必要条件。这个必要条件表明：如果存在件。这个必要条件表明：如果存在G的一个可平

7、面子图的一个可平面子图H,9使得对于某桥使得对于某桥B，有，有 ，那么，那么，G是非是非可平面的。可平面的。( ,)=F B H 根据上面的结论：我们可以按如下方式来考虑根据上面的结论：我们可以按如下方式来考虑G的平面性问题：的平面性问题： 先取先取G的一个可平面子图的一个可平面子图H1, 其平面嵌入是其平面嵌入是 1H对于对于H1的每座桥的每座桥B,如果：如果： ，则，则G非可非可平面。平面。1( ,)=F B H 否则，取否则，取H1的桥的桥B1,作：作：H2=B1HH1 1, ,再取一个面再取一个面11(,)fF B H 将将B1画入画入 的面的面 f 中。中。1H10 如果如果B1可平

8、面，则只要把可平面，则只要把B1平面嵌入后，得到平面嵌入后，得到H2的的平面嵌入平面嵌入 然后再进行上面相同的操作，可以得到然后再进行上面相同的操作，可以得到G的边数的边数递增的子图平面嵌入序列：递增的子图平面嵌入序列：12,H H 最终，得到可平面图最终，得到可平面图G的一种平面嵌入形式。的一种平面嵌入形式。2H(二二)、平面性算法、平面性算法 1964年，年，Demoucron, Mlgrance和和Pertuiset提出了下面提出了下面的平面性算法，简称的平面性算法，简称DMP算法。算法。11 设设G是至少三个顶点的简单块。是至少三个顶点的简单块。 (1) 取取G的一个圈的一个圈H1,求

9、出求出H1的一个平面嵌入的一个平面嵌入 。置。置i=1;1H (2) 若若E(G)-E(Hi)=, ,则停止；否则，确定则停止；否则，确定G G中中H Hi i的所有桥，的所有桥，并对每座桥并对每座桥B B，求出，求出 ；i(,)FB H (3) 若存在桥若存在桥B,使得：使得： ，则停止，则停止 (G不可平不可平面面) ；否则，在；否则，在Hi的所有桥中确定一个使得的所有桥中确定一个使得 最小最小的的B，并取，并取 。i(,)F B H i(,)FBH( ,)ifF B H (4) 在桥在桥B中取一条连接中取一条连接Hi中两个附着顶点的路中两个附着顶点的路Pi, iiPB 置置Hi+1=Hi

10、PPi i, ,把把P Pi i画在画在 的面的面 f f 内内, ,得到得到iHi+1H12 (5) 置置i=i+1转转(2)。 例例5 用平面性算法考察下图用平面性算法考察下图G的平面性。的平面性。v6v5v4v3v2v1v8v7图图G 解：解：(1) 取取G的一个圈的一个圈H1,并作平面嵌入：并作平面嵌入：13v6v5v4v3v2v1v8v7图图G (2)v6v5v4v3v2v1v8v7H1113BGv vv6v5v4v3v2v1v8v71Hf1f21112(,),FBHff214BGv v2112(,),FBHff327BGv v3112(,),FBHff426BGv v537BGv

11、v4112(,),FBHff5112(,),FBHff14v6v5v4v3v2v1v8v7图图G645BGv v6112(,),FBHff758BGv v7112(,),FBHff868BGv v8112(,),FBHff (3) 取取B1和和f1. (4) 取取P1=v1v3f3v6v5v4v3v2v1v8v71Hf1f215v6v5v4v3v2v1v8v7图图G (3) 取取B2和和f3. (4) 取取P2=v2v7114BGv v1213(,),FBHff227BGv v223(,)FBHf326BGv v437BGv v323(,)FBHf4213(,),FBHff545BGv v52

12、13(,),FBHff658BGv v7113(,),FBHff768BGv v7213(,),FBHffv6v5v4v3v2v1v8v72Hf1f2f316v6v5v4v3v2v1v8v7图图G226BGv v337BGv v233(,)FBHf3314(,),FBHff445BGv v4314(,),FBHff558BGv v531(,)FBHf668BGv v631(,)FBHf114BGv v131(,)FBHfv6v5v4v3v2v1v8v73Hf1f2f3f417 (3) 取取B1和和f1. (4) 取取P3=v1v4v6v5v4v3v2v1v8v7图图Gv6v5v4v3v2v1v

13、8v74Hf1f2f3f5f4126BGv v237BGv v143(,)FBHf245(,)FBHf345BGv v3415(,),FBHff458BGv v441(,)FBHf568BGv v541(,)FBHf18v6v5v4v3v2v1v8v7图图G (3) 取取B1和和f5. (4) 取取P4=v2v6v6v5v4v3v2v1v8v74Hf1f2f3f6f4f519v6v5v4v3v2v1v8v7图图G 继续下去，得到：继续下去，得到：v6v5v4v3v2v1v8v7G 算法分析：主要运算包括：算法分析：主要运算包括：20（i）找出块）找出块G中的一个圈中的一个圈Hi；（ii）确定）

14、确定G中中Hi的桥以及它们对于的桥以及它们对于Hi的附着点；的附着点；（iii）对于）对于 的每个面的每个面 f 确定其周界；确定其周界； iH（iv）对于）对于 的每座桥的每座桥B，确定，确定 iH),(iHBF（v）在）在Hi 的某座桥的某座桥B中求一条起点与终点均为附着点中求一条起点与终点均为附着点的一条路的一条路Pi。 可证上述每一个算法均存在好算法，因此平面性算法可证上述每一个算法均存在好算法，因此平面性算法也是好算法。也是好算法。本章部分习题解答本章部分习题解答21 例例1 求证，每个求证，每个5连通简单可平面图至少有连通简单可平面图至少有12个顶点。个顶点。 证明：设证明：设G是

15、是5连通图，则：连通图，则：()5k G 由惠特尼定理得：由惠特尼定理得：()()5Gk G 所以：所以：()2deg( )5vVGmvn 另一方面：另一方面：G是是5连通简单可平面图，所以有：连通简单可平面图，所以有：36mn 于是得：于是得：2.536nmn 即：即：02.50.56mnn 所以：所以：n12。22 例例2 求证，没有求证，没有6连通简单可平面图。连通简单可平面图。 证明：若不然，设证明：若不然，设G是是6连通图，则：连通图，则：()6k G 由惠特尼定理得：由惠特尼定理得：()()6Gk G 所以：所以：()2d( )6vVGmvn 于是得：于是得：36mn 这与这与G是

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

17、3n-4)/224 证明：由条件易知：证明：由条件易知：2n 由欧拉公式得：由欧拉公式得：22nnm 于是得：于是得：342nm 例例5 设设G是一个是一个(n, m)单图，图单图，图G分解为可平面的最少分解为可平面的最少个数称为个数称为G的厚度的厚度(G).(G).求证：求证： (1) ()36mGn25 (2) 证明证明: (1) 当当n=1时，结论成立。时，结论成立。(1)(),3;386(2)nn nKnnn并 证 明 ：时 等 式 成 立 。 设当设当n3时，时，G分解为分解为(G)(G)个可平面子图个可平面子图G Gi i(1i (1i (G) 因为每个因为每个Gi是平面单图，于是：是平面单图，于是：()36iim Gn 所以：所以：()136iim Gn12()()()()()Gm Gm Gm Gm G 所以：所以：()36mGn26 (2) 因为因为K3, K4是平面图，所