本次课主要内容 平面性算法 (一)、涉及算法的相关概念 (二)、平面性算法
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 2 本次课主要内容 (一)、涉及算法的相关概念 (二)、平面性算法 平面性算法
(一)、涉及算法的相关概念 关于图的平面性问题,我们已经建立了一些平面性 判定方法: (1)对于简单图G=(n,m),如果m>3n-6,则G是非可 平面的; (2)对于简单连通图G=(m,),如果每个面次数至少 为23,且m>(m-2)11-2),则G是非可平面的; ③)库拉托斯基定理:G是可平面的当且仅当G不含有 与K和K3.3同胚的子图 (4)瓦格纳定理:G是可平面的当且仅当G不含有能够 收缩成K和K33的子图;
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 3 关于图的平面性问题,我们已经建立了一些平面性 判定方法: (一)、涉及算法的相关概念 (1) 对于简单图G=(n, m),如果m>3n-6,则G是非可 平面的; (2) 对于简单连通图G=(n, m),如果每个面次数至少 为l≥3,且m>(n-2)l /(l-2),则G是非可平面的; (3) 库拉托斯基定理:G是可平面的当且仅当G不含有 与K5和K3,3同胚的子图; (4) 瓦格纳定理:G是可平面的当且仅当G不含有能够 收缩成K5和K3,3的子图;
上面的判定方法,局限性很大。这次课我们将给出 一个算法,其作用是:如果G非可平面,通过算法可以 得到判定;如果G是可平面图,通过算法,可以给出一 种平面嵌入形式。 定义1设H是G的一个子图,在E(G)-E山中定义一 个二元关系“、”: e,e,∈E(G)-E(H,ee,当且仅当存在一条途径W,使得: (I)e,与e2分别是W的始边和终边,且 (2)W的内点与H不能相交。 e e
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 4 上面的判定方法,局限性很大。这次课我们将给出 一个算法,其作用是:如果G非可平面,通过算法可以 得到判定;如果G是可平面图,通过算法,可以给出一 种平面嵌入形式。 定义1 设H是G的一个子图,在E(G)-E(H)中定义一 个二元关系“ ~”: 12 1 2 e e EG EH e e , ( ) ( ), 当且仅当存在一条途径W,使得: (1) e1与e2分别是W的始边和终边,且 (2) W的内点与H不能相交。 G e4 e3 e2 e1 e7 e6 e5
定义2设B是E(G)-E山D关于二元关系“”的等价类 在G中的边导出子图,则称B是G关于子图的一座桥。 桥与H的公共顶点称为桥B在H中的附着顶点。 例1在下图中,红色边在G中导出子图为H。求出G 关于H的所有桥。 e e 4
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 5 定义2 设B是E(G)-E(H)关于二元关系“ ~” 的等价类 在G中的边导出子图,则称B是G关于子图H的一座桥。 桥与H的公共顶点称为桥B在H中的附着顶点。 例1 在下图中,红色边在G中导出子图为H。求出G 关于H的所有桥。 G B1 B2 B3 B4 G e4 e3 e2 e1 e7 e6 e5
定义3设H是图G的可平面子图,序是H的一种平面嵌入。 若G也是可平面图,且存在G的一个平面嵌入,使得: 称序 是G容许的。 例2在G中,我们取红色边导出的子图为H,并取序=H 容易知道:序是G容许的
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 6 定义3 设H是图G的可平面子图, 是H的一种平面嵌入。 若G也是可平面图,且存在G的一个平面嵌入 ,使得: 称 是G容许的。 H% G% H G % % H% 例2 在G中,我们取红色边导出的子图为H, 并取 H% H 容易知道: 是G容许的。 G G% H%
例3在G中,我们取红色边导出的子图为H,并取 序=H G 容易知道:序不是G容许的。 定义4设B是G中子图H的任意一座桥,若B对H的所有附 着顶点都位于序的某个面f的边界上,则称在面f内可 画入,否则,称B在面f内不可画入
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 7 例3 在G中,我们取红色边导出的子图为H, 并取 H% H 容易知道: 不 是G容许的。 G H% 定义4 设B是G中子图H的任意一座桥,若B对H的所有附 着顶点都位于 的某个面 f 的边界上,则称B在面 f 内可 画入,否则,称B在面 f 内不可画入。 H%
对于G的桥B,令: F(B,)={//是的面,且B在内可画入》 例4红色边的导出子图是H,如果取序=H 确定H的桥在序 中可以画入的面集合。 G 解: F(B,序={,} F(B2,净)={f} F(B,={f} 8
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 8 对于G的桥B,令: 例4 红色边的导出子图是H,如果取 确定H的桥在 中可以画入的面集合。 FBH f f H B f (, ) % % 是 的面,且 在 内可画入 H%=H H% B3 B1 B2 f3 f2 f1 G F(,) , BH f f 1 23 % 解: F(,) BH f 2 3 % F(,) BH f 3 3 %
定理1设序 是G容许的,则对于H的每座桥B: F(B,序)≠Φ 证明:因序是G容许的,由定义,存在G的一个平面嵌 入ě,使得: 序 于是,H的桥B所对应的帝 的子图,必然限制在序的 某个面内。所以: F(B,序)≠Φ 注:定理1实际上给出了一个图是可平面图的一个必要条 件。这个必要条件表明:如果存在G的一个可平面子图H
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 9 定理1 设 是 H% G容许的,则对于H的每座桥B: FBH (, ) % 证明:因 是G容许的,由定义,存在G的一个平面嵌 入 ,使得: H% G% H% G% 于是,H的桥B所对应的 的子图,必然限制在 的 某个面内。所以: G% H% FBH (, ) % 注:定理1实际上给出了一个图是可平面图的一个必要条 件。这个必要条件表明:如果存在G的一个可平面子图H
使得对于某桥B,有F(B,)=D,那么,G是非 可平面的。 根据上面的结论:我们可以按如下方式来考虑G 的平面性问题: 先取G的一个可平面子图H,其平面嵌入是序 对于H的每座桥B,如果:F(B,序)=Φ,则G非可 平面。 否则,取H的桥B1,作:H2=B,UH1,再取一个面 f∈F(B,房) 将B画入序的面f中。 10
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 10 使得对于某桥B,有 ,那么,G是非 可平面的。 FBH ( , )= % 根据上面的结论:我们可以按如下方式来考虑G 的平面性问题: 先取G的一个可平面子图H1, 其平面嵌入是 H1 % 对于H1的每座桥B,如果: ,则G非可 平面。 1 FBH ( , )= % 否则,取H1的桥B1,作:H2=B1∪H1,再取一个面 1 1 f FB H (, ) % 将B1画入 的面 H%1 f 中
如果B可平面,则只要把B平面嵌入后,得到H的 平面嵌入序, 然后再进行上面相同的操作,可以得到G的边数 递增的子图平面嵌入序列: 序,序6 最终,得到可平面图G的一种平面嵌入形式。 (二)、平面性算法 1964年,德穆克龙Demoucron),莫尔根思Mlgrance和 珀特维斯(Pertuiset)提出了下面的平面性算法,简称DMP 算法
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 11 如果B1可平面,则只要把B1平面嵌入后,得到H2的 平面嵌入 然后再进行上面相同的操作,可以得到G的边数 递增的子图平面嵌入序列: 1 2 H H % %, L 最终,得到可平面图G的一种平面嵌入形式。 H2 % (二)、平面性算法 1964年,德穆克龙(Demoucron), 莫尔根思(Mlgrance)和 珀特维斯(Pertuiset)提出了下面的平面性算法,简称DMP 算法