（运筹学与控制论专业论文）关于可平面图的边剖分的若干结果.pdf

山东大学硕士学位论文 关于可平面图的边剖分的若干结果 吴玉文 山东大学教学与系统科学学院 运筹学与控制论 山东济南2 5 0 1 0 0 中文摘要 本文考虑的图若无特殊声明均为简单，无向有限图对于一个图g = a ( v ( a ) e ( g ) ) ，我们用v ( a ) 和e ( g ) 分别表示图的顶点集合和边集合对任意的口 y ( g ) ，我们用如( 口) 表示顶点 在g 中的度数a ( a ) 和6 ( g ) 分别表示图g 的 最大度和最小度对v ( g ) 的子集s ，用g s 表示从g 中删去顶点集合s 及 其关联的边所得到的子图若s = ) ，则令g 一口= g 一 u 对e ( g ) 的子集 x ，用g x 表示从g 中删去边集合x 所得的子图着x = 0 和任一个最大度a ( g ) 足够大的图 g ，有l a ( g ) 曼j ( g ) ；并且，若图g 的最大度( g ) 为偶数( 或为奇数) ，围长 g 5 0 a ( c ) ( 或g21 0 0 a ( g ) ) ，则线性荫度猜想成立 1 3 本文的主要结果 我们通过对可乎面图的边染色和线性荫度问题进行讨论研究，主要得出以下 结论 定理2 1 5 设g 是最大度为6 的可甲面图若g 中不含长度为6 的嘲，则g 是第一类图 定理2 1 1 0 设g 是最大度为5 的可平面图若g 中不含长度为4 的圉，或不 含长度为5 的圈，则g 是第一类图 定理3 2 1 设g 是最大度等于7 的可平面图，则l a ( g ) 4 3 山东大学硕士学位论文 上述定理中，定理2 1 5 已由y b u 和w w a n g 1 4 1 证明出来，但是我们通 过d i s c h a r g i n g 方法又给出了它的一个更为简单的证明，具体的证明过程省略 本文中，我们主要给出了定理2 1 1 0 和定理3 2 1 的证明过程其中，第二章介 绍了有限制条件的可平面图的边染色；而第三章则是通过给出最大度7 的可平 面图的线性荫度，证明出对于可平面图来说，线性荫度猜想成立 此外。关于可甲面图的线性荫度，我们还有如下结果， 定理3 3 2 设g 是最大度( g ) 1 1 的可甲面图，则t a ( a ) = 垒笋 定理3 3 3 设g 是个最大度a ( c ) 27 的可平面图，若g 中任意两个三角形 都没有公共边，则l a ( g ) = f 垒铲1 4 第二章可平面图的边染色 2 1 边染色的分类问题 在第一章里。我们提到关于简单图g 的分类，即当x ，( g ) = z x ( g ) 时称g 为第一类图；当x + ( g ) = ( g ) + 1 时称g 为第二类图而图的分类问题就是 判断一个图g 究竟是第一类图，还是第二类图的问题饲如，对于一个完全图 纸( n 2 ) 来说，若n 是奇数，则( 以) 一n ，即j 厶是第二类的；若n 是偶 数，则x ( j 0 ) = n 一1 ，即j 厶是第一类的另外很容易得知，p e t e r s o n 图是第 二类图，而任意的二部图都是第一类图关于图的分类问题，虽然已有一些相关 的结论。但是未解决的部分还有很多 现在我们来考虑可平面图的分类问题v i z i n g 【2 1 通过对q ，甄，八面体和 二十面体的某条边进行细分而得到了a 2 ，3 ，4 ，5 ) 的第二类的可平面图另 外，他还证明了如下结果。 定理2 1 1 ( v i z i n g 【2 】) 如果g 是一个可平面图，并且6 ( c ) 8 ，那么g 是 第一类图 因此，关于可平面图的边染色的分类问题，只有最大度等于6 和7 这两种情 况未被解决于是v i z i n g 在1 9 6 8 年的时候，提出了著名的- - f v 面图猜想 猜想2 1 2 ( 可平面图猜想【2 】) 任意一个最大度等于6 或7 的可平面图都是第 一类图 l z h a n g 和d ps a n d e r s ，y z h a o 分别在2 0 0 0 年和2 0 0 1 年解决了这个 猜想中最大度等于7 的情况，即 定理2 1 3 ( l z h a n g 【4 9 ，d p s a n d e r s ，y z h a o 【3 0 】) 任意一个最大度 等于7 的可平面图都是第一类图 对于最大度等于6 这种情况下的可甲面图猜想，至今还未完全解决，但已有 一些相关的结论 定理2 1 4 ( g z h o u 5 l 】) 设g 是最大度为6 的可平面图若g 中不合长度 为3 。4 或者5 的圈，则g 是第一类图 最近y b u 和w w a n g 对上面这个结果做了改进，得到了下面这个结果 5 山东大学硕士学位论文 定理2 1 5 ( y b u ，w w a n g 【1 4 】) 设g 是最大度为6 的可平面团若g 中 不含长度为6 的圈，则g 是第一类图 这里要提到的是，最近我们也给出了该结论的一个更为简单的证明，具体证 明过程参见文献 4 3 1 若考虑可甲面图的最大度，圈，围长及其它的相关条件，其 分类问题还有一些其它的结论 定理2 1 6 ( k r o n k ，r a d l o w s k i ，f r a n e n 【2 】) 设g 是一个可平面图，且和 g 分别为g 的最大度和围长如果下列条件之一成立，则g 是第一类图 ( 1 ) a 3 ，g 8 ； ( 2 ) a 芝4 。9 25 ； ( 3 ) a 5 ，g 4 定理2 1 7 ( p l a m ，j l i u ，w s h i u ，j r u 【2 2 1 ) 设g 是一个可平面图如 果下列条件之一成立，则g 是第一类图 ( 1 ) a26 ，且g 中不合长度为4 的圈； ( 2 ) 26 ，且g 中任两个长度为3 的面不关联于同一个顶点； ( 3 ) a 5 ，且g 中不合长度为4 和5 的圈； ( 4 ) 5 ，g 中不合长度为4 的圈，且任两个长度为3 的面不关联于同一 个顶点l ( 5 ) a24 。且g 中不合长度为t 的圈，其中4 l 1 4 ； ( 6 ) 4 ，g 中不舍长度在4 和6 之间的圈，且任两个长度为3 的面不关 联于同一个顶点 定理2 1 8 ( y b u ，w w a n g 【1 4 】) 设g 是最大度为6 的可平面图若g 中 不合有弦的长度为4 的圈，则g 是第一类图 定理2 1 9 ( y b u 。w w a n g 【1 4 】) 设g 是最大度为6 的可平面图若g 中 不合有弦的长度为5 和6 的圈，则g 是第一类图 在下一节中。我们将用图论中广泛使用的d i s c h a r g i n g 方法来证明本章的主 要结论： 定理2 1 1 0 ( j w u ，y w u 【4 2 】) 设g 是最大度为5 的可平面图若g 中不 合长度为4 的圈，或不合长度为5 的圈，则g 是第一类图 6 山东大学硕士学位论文 2 2 最大度为5 的可平面图的边染色 首先，在证明定理2 1 1 0 之前，我们要给出临界图的定义，并对证明过程中 要用到的一些概念，符号做出解释 定义2 2 1 若图g 是连通的第二类图，并且对于任意的边e e ( g ) ，都有x ，【g e ) y ( g ) 。则称g 是一个临界图 如果临界圈g 的最大度为，那么g 就是一个一临界图显然，任个 临界图都足2 一连通的 定义x y z 为图g 的个三角形，若o ，y 和$ 为g 中三个不同的顶点。且两两 相邻接如果，是一个度为k 的面，其边界上各个顶点的度分别为南，玩，缸， 且不妨设t 1 如s s 记则称，是一个0 - ，如，缸) 一面另外，可以用辞 来代替幻，以表示在，的边界上某个顶点的度至少为略 接下来，我们再来介绍几个与证明相关的引理 引理2 2 2 ( 【2 】) 设g 是一个第二类的图。则对于任意的k 满足2 k ( g ) ，g 中都存在一个k 临界子图， 引理2 2 3 ( v i z i n g 邻接引理【2 】) 设g 是一临界冒。且锚， 是g 中任意两 个相邻接的顶点，d ( v ) = k ，那么 ( 1 ) 若k ，则“至少邻接于一k + 1 个度为的顶点； ( 2 ) 若k = ，则i t 至少邻接于两个度为的顶点 根据引理2 2 3 ，可以很容易地得出下面的推论 推论2 2 4 设g 是一临界图，且u ，口是g 中任意两个相邻接的顶点，则有 ( 1 ) d ( i t ) + d ( v ) + 2 ； ( 2 ) 若3 ，则“至多邻接于一个度为2 的顶点，且至少邻接于两个度 为的顶点； ( 3 ) 若d ( u ) + d ( v ) = 十2 ，更l l 对任意的埘n ( i t ， ) i t ，u ，都有 d ( w 1 = a 引理2 2 5 ( l z h a n g 4 0 1 ) 设g 是一临界图，“和口是g 中任意两个相邻 接的顶点，且d ( “) + d p ) = + 2 ，那么 ( 1 ) 对任意的w n ( n ( i t ，口 ) ) i t ，口) ，都有d ( w ) 一1 ； ( 2 ) 若d ( t ) ，d ( ) 0 设，是个度至少为6 的面，则c h ( ) = c h ( f ) 0 设 是一个度为2 的顶点，则砒( 口) 一一2 由推论2 2 4 可知，口的两个邻 接顶点的度均为5 因此，根据r 1 1 有，c ( 口) = - 2 + 1 2 = 0 设 是一个度为3 的顶点，则c ( u ) = c h ( v ) = 0 设 是一个度为4 的顶点，则c h ( v ) = 2 由引理2 2 3 可知，至多存在一个 度为3 的顶点与 相邻接，并且m i n ( d ( u ) l u ( ) 3 因为g 中不含长度 为4 的圈，所以至多存在两个度为3 的面与u 相关联根据r 1 2 和r 1 3 可知。 对于每一个度为3 的关联面，口至多分出值1 ，且口至多分值 给每一个度为5 的关联面 若不存在与口相关联的度为3 的面，则 至多邻接于4 个度为5 的面从 而c h ( 口) 22 一 4 0 若仅存在一个度为3 的面与 相关联。则口至多邻接 于3 个度为5 的面从而c ( 口) 2 1 一 3 0 现在，设存在两个度为3 的面与口相关联如果口根据r 1 2 分值1 给其中一 个面，那么，一定是个( 4 ，4 ，4 ) 一面或( 3 ，4 ，5 ) 一面由推论2 2 4 可以得知。口的 另个度为3 的关联面必定是一个( 4 ，5 ，5 ) 一面因此，c h ( v ) 2 - 1 一。一 x 2 0 否则，由r 1 2 可知，”至多分值；给每一个度为3 的关联面，从而可以推出 c h 7 扣) 芝2 一；2 一- i 2 = 0 9 山东大学硬士学位论文 设 是个度为5 的顶点，则c h ( v ) = 4 由引理2 2 3 可知，至多存在一个 度为2 的顶点与口相邻接，并且m i n d ( u ) l u | 、r ( 口) 2 因为g 中不含长度 为4 的圈，所以至多存在两个度为3 的面与 相关联。 若不存在与 相关联的度为3 的面，则 至多邻接于5 个度为5 的面从 而根据r 1 1 和r 1 3 有，砒7 ( 口) 芝4 1 一 5 0 若仅存在一个度为3 的面 与 相关联。则口至多邻接于4 个度为5 的面这种情况下，无论口是否邻接于 度为2 的顶点。都可以推出c h ( v ) 4 一m a x 1 + ；+ 4 ，2 + 4 0 下面只需讨论恰好存在两个度为3 的面与 相关联这一种情况即可我们 分三种情况进行讨论 情况1 - 1 m i n d ( u ) l u ( ) = 2 令为口的度为2 的邻接点根据r 1 1 可知，口分值1 给“那么由推论 2 2 4 可知，对于任意的i f ) n ( v ) 一“都有d ( w ) = 5 由此还可推出，口的任一 度为3 的关联面均是一个( 2 ，5 ，5 ) 一面或( 5 ，5 ，5 ) 一面 若边 缸关联于一个( 2 ，5 ，5 ) 一面，那么与口“相关联的另一个面的度至少为 6 ，否则g 中必有长度为4 的圈因此，由引理2 25 可知， 至多关联于1 磊i 4 度为 5 的面，且它们必定是( 4 + ，4 + ，5 ，5 ，5 ) 一面从而，c h ( v ) 4 - 1 一；一1 一i 1x 2 0 若不然，即不存在( 2 ，5 ，5 ) 一面与伽相关联，贝0 根据r 1 2 ，f 至多分值1 给每一 个度为3 的关联面因此，c h ( u ) 4 1 1 2 一i 1 3 = 0 情况1 2 m i n d ( u ) l u ( ) = 3 此时，口至多邻接于两个度为3 的顶点，且至少邻接于三个度为5 的顶点。 若口根据r 1 2 分值2 给个( 3 ，4 ，5 ) 一面，则由引理2 2 5 可知，其余的 的 度为3 的关联面均是( 5 ，5 ，5 ) 一面，从而有，c h ( 口) 4 - 2 - 1 - 3 = 0 若不然， 则口至多分值给每一个度为3 的关联面因此，c ( 口) 24 一；2 一3 = 0 情况1 - 3 m i n d ( u ) l u ( ) 4 此时， 至多分值2 给每一个度为3 的关联面因此同样可以推出，c h ( v ) 2 4 一；2 一 3 = 0 综上所述，当g 中不含长度为4 的圈时，对于任意的z v ( e ) u f ( g ) ，都 有c h ( z ) 0 ，从而与( 2 2 3 ) 式矛盾，结论得证 现在，我们来证明第二种情况下结论同样成立，即若g 中不含长度为5 的 圈，则g 是第一类图下面给出新的交换规则 r 2 - 1 对于每一个度为2 的顶点口，每个度为5 的邻接顶点分值1 绘口 山东大学硬士学位论文 r 2 - 2 对于每个度为3 的面，令瓤y 和。是与之相关联的三个不同的 顶点，且d ( x ) d ( y ) s d (