（运筹学与控制论专业论文）平面图的诱导圈符号控制数问题.pdf

i 。 d i s s e r t a t i o no fm a s t e r2 010s c h o o lc o d e ：1 0 2 6 9 s t u d e n tn u m b e r ：510 7 0 6 010 8 2 e a s tc h i n an o r m a lu n i v e r s i t y o nt h es i g n e dc y c l ed o m i n a t i o np r o b l e m o tp l a n a ra r a p h s -v i d e p a r t m e n t ：d e p a r t m e n t o fm a t h e m a t i c s m a j o r ： s u b j e c t ： o p e r a t i o n a lr e s e a r c ha n dc y b e r n e t i c s g r a p ht h e o r ya n d i t sa p p l i c a t i o n s s u p e r v i s o r ：c h a n g h o n gl u m a s t e rc a n d i d a t e ：x i a o y a nl i u 2 0 1 0 5 华东师范大学学位论文原创性声明 郑重声明：本人呈交的学位论文干面团白铙辱圈翳雩磋辱9 规司趁 ， 是在华东师范大学攻读砸斯博士( 请勾选) 学位期间，在导师的指导下进行的研究工作 及取得的研究成果。除文中已经注明引用的内容外，本论文不包含其他个人已经发表或 撰写过的研究成果。对本文的研究做出重要贡献的个人和集体，均已在文中作了明确说 明并表示谢意。 作者签名： 日期：加f o 年争月幻e l 华东师范大学学位论文著作权使用声明 平面团筋质导圈荷号凌制叛问题系本人在华东师范大学攻读 学位期间在导师指导下完成的劝博士( 请勾选) 学位论文，本论文的研究成果归华东 师范大学所有。本人同意华东师范大学根据相关规定保留和使用此学位论文，并向主管 部门和相关机构如国家图书馆、中信所和“知网”送交学位论文的印刷版和电子版；允 许学位论文进入华东师范大学图书馆及数据库被查阅、借阅；同意学校将学位论文加入 全国博士、硕士学位论文共建单位数据库进行检索，将学位论文的标题和摘要汇编出版， 采用影印、缩印或者其它方式合理复制学位论文。 本学位论文属于( 请勾选) () 1 经华东师范大学相关部门审查核定的“内部 或“涉密”学位论文掌， 于年月日解密，解密后适用上述授权。 ) 2 不保密，适用上述授权。 吲雠坦丝 本人签名童4 晚拖 】加年p 月衫日 “涉密”学位论文应是已经华东师范大学学位评定委员会办公室或保密委员会审定过的学位 论文( 需附获批的华东师范大学研究生申请学位论文“涉密”审批表方为有效) ，未经上 述部门审定的学位论文均为公开学位论文。此声明栏不填写的，默认为公开学位论文，均适用 上述授权) 。 ， ：色 。b 硕士学位论文答辩委员会成员名单 姓名职称 单位备注 、矢漭1 基摇隼尔卿嬲 主席 券酸惫叔褪 上淘妞媾 郛写佛萝l 放般耷禾j 千恕培 华东师范大学平面图的诱导圈符号控制数问题 摘要 设g = ( k 助是一个简单图，定义函数f ：e 一 - 1 ，+ l 如果g 的任意一个诱导 圈c 都满足，( c ) = 。目c ) 厂( p ) 1 ，则称厂为图g 的诱导圈符号控制函数( s i g n e dc y c l e d o m i n a t i o nf u n c t i o n ) ，简记为s c d e 同时定义y 乏( g ) = r a i n f ( g ) l f 是g 的一个s c d f 为 图g 的诱导圈符号控制数( s i g n e dc y c l ed o m i n a t i o nn u m b e r ) 本文主要研究了极大平面图，2 连通平面图和最小度为3 的图的诱导圈符号控制 数主要结果如下： ( 1 ) 设g ( i v ( g ) i = ，1 ) 是一个极大平面图，矗( g ) = 聘一2 当且仅当它的所有诱导圈都 是g ( 2 ) 设g ( i v ( g ) i = ，1 ) 是一个极大平面图，y 二( g ) n 当且仅当g 有一个诱导圈q ，其 中k 4 ( 3 ) 若g 是一个2 。连通平面图，则心( g ) 1 ( 4 ) 任意6 ( g ) = 3 的图g ，若7 二( g ) 有常数下界，则y s c ( g ) 2 上述关于极大平面图的结果，否定了徐宝根在【o ns i g n e dc y c l ed o m i n a t i o ni n g r a p h s ，d i s c r e t em a t h 3 0 9 ( 2 0 0 9 ) 1 0 0 7 1 0 1 2 】中的一个猜想 关键词：控制集；符号控制数；诱导圈符号控制数；平面图；极大平面图 c y c l eo fg i sg ( 2 ) l e tg ( i v i = 以) b eam a x i m u mp l a n a rg r a p h ，r l ( g ) ni fa n do n l yi fg h a sa l li n d u c e d c y c l eg ( 七4 ) ( 3 ) i fg i sa2 - c o n n e c t e dp l a n a rg r a p h ，t h e n 记。( g ) 1 ( 4 ) l e tg b eag r a p hw i t h5 ( g ) = 3 ，i fy ：。( g ) h a sac o n s t a n tb o u n d ，t h e n7 乏( g ) 2 t h ea b o v er e s u l t so nm a x i m u mp l a n a rg r a p h sn e g a t i v ea c o n j e c t u r ei nb x u 【o ns i g n e d c y c l ed o m i n a t i o ni ng r a p h s d i s c r e t em a t h 3 0 9 ( 2 0 0 9 ) 1 0 0 7 1 0 1 2 】 k e yw o r d s ：d o m i n a t i o ns e t ；s i g n e dd o m i n a t i o nn u m b e r ；s i g n e dc y c l e d o m i n a t i o nn u m o b e r ；p l a n a rg r a p h ；m a x i m u mp l a n a rg r a p h i i 华东师范大学平面图的诱导圈符号控制数问题 目录 第一章引言l 1 1 背景和基本概念1 1 2 研究现状3 第二章极大平面图的诱导圈符号控制数5 2 1 任意极大平面图的诱导圈符号控制数的界5 2 2 构造出t 。= ，l 一2 的极大平面图8 2 3 所有诱导圈是c 3 的极大平面图的诱导圈符号控制数1 0 2 4 含有c k ( k 4 ) 诱导罔的极大平面图的矗( g ) 1 3 第三章诱导圈符号控制数在一些图上的界1 8 3 12 一连通平面图的诱导圈符号控制数1 8 3 26 ( g ) = 3 的图的诱导圈符号控制数2 0 第四章总结2 2 参考文献2 4 致谢2 7 i i i 第一章引言 1 1 背景和基本概念 控制集问题是组合优化理论中一个重要的研究领域，其主要应用在设计和通 讯网络、社会科学、优化、生物信息学、计算复杂度分析和算法设计等多各方面 由于应用广泛，控制集问题的研究也就逐渐得到了深入和扩大，各种新的控制参数 也不断涌现图的控制集问题的研究已经有很长的历史，可回溯到1 9 世纪中期的 一种象棋游戏在h a y n e s ，h e d e t n i e m i ，s l a t e r 的书【1 6 】和【1 7 】中给出了图的控制集 的详细介绍以及早期的一些结果，最近的一些结果可在 1 5 1 ， 1 9 1 ，【1 8 】，【2 3 】， 2 2 1 ，【2 4 】等 文献中找到起初图的控制集问题只涉及点的控制集，由于边的控制集问题与实 际联系紧密所以也逐渐被大家关注，例如电话转换网络根据来电查找线路问题 等就可以转化为边的控制集问题这方面的研究如：【2 6 ，【l l 】，【2 l 】，【1 2 】符号控制集 最先在d u n b a r , h e d e t n i e m i ，h e n n i n g ，s l a t e r 的 7 】中提出，对于它的研究已经有很多 的结果，如：【7 】， 2 0 】， 9 】，【l o 】， 1 l 】，【1 3 】，【6 】等最早的符号控制集偏重于点的符号控制 集的研究，而对边的符号控制集问题首先在徐宝根的【2 9 】中出现，最近的结果可参 考 3 1 ，【7 】， 3 2 1 ，【1 ，【3 0 等本文所研究的图的诱导圈符号控制数问题是一个新的问 题，它也是由徐宝根提出的，在他的 2 8 】中首次给出定义，同时也做出了一些研究下面 介绍一些本文涉及到的基本定义 设g = ( ve ) 是一个简单图，y 表示图g 的顶点集；e 表示图g 的边集对于 任意的一点v vn ( v ) 表示点1 ，的开邻域集，而n v 】= n ( v ) u y 表示1 ，的闭邻 域集d ( v ) 表示点1 ，的度，即与点1 ，相连的点的个数，其中最小的d ( v ) 记做6 ( g ) 如 果点集s v ，那么g s 】表示由s 在图g 中诱导出的子图；如果g 是日的一个子 图，那我们就记做g h 如果g h ，那么日一g = 日【y ( y ( g ) 】两个不相交的 图g l ，g 2 的并我们记做g lug 2 ，而用g l + g 2 表示两者的联合，即在原图的基础上添 加边 u v l u v ( g i ) ，v v ( g 2 ) 另外，我们用d ( u ，1 ，) 表示图中两点u ， ，之间的最小距 离，g 表示图g 的补图如果一个圈c 满足g 【y ( c ) 】= c ，那么就叫做图g 的诱导圈如 华东师范大学平面图的诱导圈符号控制数问题 果圈的长度为偶数( 奇数) ，就叫做偶圈( 奇圈) 接下来给出诱导圈符号控制数的定义： 定义1 1 设g = ( v , e ) 是一个非空的简单图，函数f ：e ( g ) 一l - 1 ，1 ，若。嘣c ) f ( e ) 1 对g 的任意诱导圈c 都成立，则称厂是g 的一个诱导圈符号控制函数( s i g n e d c y c l ed o m i n a t i o nf u n c t i o n ) ，简记为s c d f ；同时称矗( g ) = m i n 眭e 厂( p ) l ，是g 的 一个s c d f l 为g 的诱导圈符号控制数( s i g n e dc y c l ed o m i n a t i o nn u m b e r ) 简单地，厂是g 的一个s c d e 若记f ( g ) = 。尉g ) 弛) ，则心( g ) = m i nf f ( g ) l f 是g 的 一个s c d f 若y 二( g ) = ，( g ) ，就称，是g 的一个最小诱导圈符号控制函数 图1 ：例图 例如图 1 】：在局中有两条边标+ 1 ，一条边标1 ，y 二( 局) = 1 再如在砀中有四条 边标+ 1 ，两条边标1 ，矗( 甄) = 2 同时，偶圈的诱导圈符号控制数都为2 ，而奇圈的诱 导圈符号控制数都为1 根据定义我们不难得出如下事实 2 8 】： g 是一个简单图，则有 ( 1 ) 如果g 没有圈，则矗( g ) = 一i e ( g ) i ； ( 2 ) 如果g 是的补图，那么y 二( g ) = i ( g ) j = 0 ； ( 3 ) 对于两个不相交的图g l ，g 2 ，有t s c ( g lu g 2 ) = t 。( g 1 ) + 矗g 2 ，而9 = ( ( g iu g 2 + k i ) ) = 7 2 ( g l + k i ) + 以。( 6 2 + k 1 ) ； ( 4 ) 矗( g ) 兰i e ( g ) i m o d ( 2 ) 文中我们还会用到下面两个概念： 定义1 2 每一个面( 含外平面) 都是三角形面的平面图称为极大平面图 2 华东师范大学平面图的诱导圈符号控制数问题 定义1 3 一个点与一个圈的所有顶点都相连而构成的图称为轮图，圈长为k 的轮 图记做肌 1 2 研究现状 对符号控制数的研究已经很丰富了，但本文研究的诱导罔符号控制数问题是一个 新生的问题，徐宝根在【2 8 】中首次介绍了该问题就诱导圈符号控制函数的问题，徐宝 根得到了一些图的诱导圈符号控制数的界，另外也得到了轮图的诱导圈符号控制数的 准确值而本文主要针对其文章最后所提的猜想，做出了一些平面图的结果 【2 8 】中的主要结果如下： 定理1 1 在一个连通图g 中，心( g ) = l e ( g ) i 一2 当且仅当g k 2 ，( 3 ，k m l ，此 时m 万2 定理1 2 对于一个简单图g ，若矗( g ) = i e ( g ) l 一2 当且仅当g = hu 瓦，此 处h 五，2 ，k 3 ，k m m j ，同时m ，l 2 ，b 是自然数 定理1 3 对于任意一个连通图g ，若g k l ，k 2 ，k 3 ，k m ，1 ) ，沏，l 2 ) ，则矗( g ) i e ( g ) i - 4 定理1 4 若一个图g 的点数为，l ，边数为m ，则心( g ) m 一2 n + 2 ，当且仅当g 是一个 树的时候等号成立 所以，如果g 不是一个树，则矗( g ) m 一2 ，l + 4 定理1 5 对于任意点数大于2 的图g ，如果g p 4 ，则有 识c ( g ) + t 。渤半 3 华东师范大学平面图的诱导圈符号控制数问题 根据极大平面图和极大外平面图3 ) 的点边关系得到如下结论 定理1 6 对于任意一个顶点数为万的极大外平面图g ，矗( g ) 1 ；对于任意一个极大 平面图g ，y 2 ( g ) n 一2 然后根据图的运算进而得出如下结论 定理1 7 对于任意图g ，矗( g + k 1 ) n + 矗( g ) 定理1 8 对于任意一个点数大于2 的树t ，7 二( r + k 1 ) = l ；对任意一个森林只以d = 以，如果6 ( f ) 0 ，贝4y 二( ，+ 足1 ) = 以一i e ( f ) i 定理1 9 心( + 1 ) = 2 【：j + 2 在 2 8 】的最后，徐宝根提出了一下三个猜想： 猜想1 任意6 ( g ) = 3 的图g ，y 二( g ) 1 猜想2 如果g 是一个顶点数，l 3 的极大平面图，则y 乏( g ) = 万一2 猜想3 任意2 连通图g ，都有谚。( g ) i 本文就这几个猜想做了一些研究，文中出现的其它记号和概念可参见【8 】，【3 】， 2 7 】， 【3 3 或其它相关文献 4 第二章极大平面图的诱导圈符号控制数 2 1 任意极大平面图的诱导圈符号控制数的界 本章中所涉及到的图g 都是指顶点数为，l 的极大平面图 首先给出一个平面图的一个定义 定义2 1 在一个平面图中，如果一个诱导圈所围的区域内部( 也可指外平面区域) 不再 包含由其它的诱导圈所围的区域，那么我们就称这个诱导圈为该图的基本诱导圈，简称 为基本圈 换一种角度理解基本圈，对于任意一个平面图，不论它是由那种画法呈现出来的， 我们总是可以通过把它画在一个球面上，然后沿着某一个面( 此处的面指的是内部不含 任何点的一个区域) 的边界剪开而得到并且当一个平面图被画在球面上时，它的面不 再有内外之分，每一个面都是内平面因此我们所定义的基本圈指的是当平面图被表示 在球面上时它的每个面的边界所对应的圈，所以简单多面体上的欧拉公式在这里也 是成立的 欧拉公式： y + f e = 2 其中，v 表示顶点数，表示面数( 包括外平面) ，e 表示边数 在【2 8 】中已经得出了下面引理的结论，在此，我们给出另外一种证明方式 引理2 1 【2 8 】任意一个极大平面图g ，以。( g ) ，l 一2 证明：由于任意极大平面图g 的基本圈都是三角形，所以g 的任意一个s c d f 都使 基本圈的三边中最多只能出现一个一1 ，即。c 厂( p ) 1 ，其中c 为基本圈，厂是一 5 华东师范大学平面图的诱导圈符号控制数问题 个s c d e 所以 厂( e ) = 主八已) 圭i 够i e e e ( g )。c 够e c 。 其中够表示图g 的所有基本圈的集合 易知够是图g 的分割面的个数( 包括外平面) 若记y ( g ) - - n ，e ( g ) = m ，则m = 3 n 一6 由欧拉公式可得， f = 2 n 一4 = i 汐1 故， y 八已) 万一2 ； 赢1 矗( g ) = n i l n 厂( p ) i f 是g 的一s c d f 刀一2 e e e ( g ) 在【2 8 】中列出几个例子之后，作者给出了如下猜想 猜想如果g 是一个顶点数n 3 的极大平面图，则心( g ) = n 一2 瓜瓜 g 图2 ：反例 h 口 对于这一猜想，我们找出了反例，如图 2 】所示，当n = 6 时，矗( g ) = 6 4 ( 原因参 照第2 4 节) ；而同时又有矗( = 4 因此，这个猜想是不成立的 那么对于任意一个极大平面图，其诱导圈符号控制数与n 一2 之间会有什么联系 呢? 接下来我们就对这一问题进行分析，同时给出一些结论及证明 首先我们考虑以。( g ) n 一2 时g 所对应的s c d f 的特征及这种特征又会在什么 情况下出现 6 题 八g ) = 三八c ) = 半= 以一l ， 。c e - 管 。 应 含 个 由 数 个 多 出 这两个结果是矛盾的，因此假设只有一个基本圈满足f ( c ) = 3 是不成立的故至 少存在两个基本圈满足f ( c ) = 3 ，同时我们很容易得出当存在两个时， 胴= 鸦izf n 一2 ，则任意s c d f 都会使g 中存在至少两个全都标+ l 的 基本圈，且以。( g ) ，1 反之，显然成立 e l 上面的结论给出了顶点数为n 的极大平面图y ：。( g ) n 一2 的情况，接下来我们考 虑心( g ) = 疗一2 的情况 引理2 3g 是一个顶点数为n 的极大平面图，如果y 乏( g ) - - 疗一2 ，则g 中所有的 诱导圈g 都满足标记和为1 证明：由引理2 2 可知g 的基本圈都是满足标记和为l ，所以我们只用考虑c 3 不是基 本圈的情况 7 华东师范大学平面图的诱导圈符号控制数问题 反证，假设g ( i v i - n ) 是满足条件的点数最少的极大平面图，且c 3 是g 中全标记 为+ l 的诱导圈g 根据极大平面图的性质，该c 3 的内部和外部( 含边界) 都还是极大 平面图不妨记内部图为g l 外部图为g 2 ，并且顶点数分别为拧l ，疗2 ，则，l l + i 1 2 = n + 3 由于g 是满足条件最小图，由引理2 1 可得心( g 1 ) 厅l ，矗( g 2 ) 以2 那么可得 y 二( g ) = 矗( g 1 ) + y 2 ( g 2 ) 一3 i l l + n 2 3 = 咒+ 3 3 这与假设t 。( g ) = 万一2 相矛盾所以g 中所有的诱导圈c 3 都满足标记和为1 得 证 口 由以上的结论我们不仅知道了极大平面图的诱导圈符号控制数的下界，同时也知 道了矗( g ) 与g 的诱导圈g 的取值之间的关系接下来分三个部分研究 2 2 构造出兵r = n 一2 的极大平面图 本节我们主要研究矗= n 一2 的极大平面图的存在性，采用的方法是构造法首 先。我们构造这类极大平面图 对于任意自然数n ，忍3 ，现在我们要构造一个极大平面图g ，满足i y ( g ) i = n ，且y z ( g ) = 万一2 构造的步骤如图【3 】所示 ( 1 ) 先构造一个三角形； 图3 ：构造过程 8 华东师范大学平面图的诱导圈符号控制数问题 ( 2 ) 在这个三角形里添加一个点，把这个点与这个三角形的三个顶点相连： ( 3 ) 再任选一个基本三角形面，在其里面添加一个点，把该点与所在的三角形面的三个 顶点相连： ( 4 ) 如果所形成的图还没有达到n 个顶点，继续重复操作( 3 ) ； ( 5 ) 形成一个以点的极大平面图 显然，图g 是一个极大平面图，同时满足下面的引理 引理2 4 按照上述构造的操作，所得到的极大平面图中的所有诱导圈都是三角 形 证明：反证，假设存在一个诱导圈g ( 七4 ) ，不妨记顶点为l ，l ，屹，v 4 根据构造过 程可知，这k 个点是按照一定次序添加的，不失一般性，收是最后一个添加的点，那 么y k 一定是添加在一个三角形面内部的，而由于 ，l ，h l 都和v k 相连，故1 ，l v k l 是三角 形面的一条边，而这又与，l ，v 2 ，魄构成g ( 足4 ) 诱导圈相矛盾所以这样构成的极 大平面图的所有诱导圈都是c 3 得证 净口 接下来构造对应的一个s c d f 我们就依照g ( i v ( g ) i = ，1 ) 的构造步骤来定义一个s c d e 使得心( g ) = ，l 一2 步骤 如图 4 所示，h 0 ： ( 1 ) 给第一个三角形的三边分别标记+ 1 ，+ l ，1 ； 一 ( 2 ) 增加一个点之后，产生了三个小三角形，首先给含有1 边的小三角形的另外两条边 标记为+ 1 ，剩余的那条边标记为+ 1 ： ( 3 ) 每增加一个点，就重复( 2 ) 的操作； ( 4 ) 加点完毕，得到一个s c d f 图4 ：构造标记 9 华东师范大学平面图的诱导圈符号控制数问题 显然在标记的过程中，我们保证了每次新增加的三角形满足了符号标号和为l ，达 到了最小值，但是这种标记操作会不会产生一个全部标记为1 或+ 1 的三角形呢? 这 个答案是否定的因为我们构造时的操作保证了每一个三角形都是在某一确定的步骤 构造而得到的，并且每次所添加的边不会与所在的三角形之外的边构成诱导圈，同时我 们在给出标记的时候保证了每一步产生的新的三角形满足标记和为1 因此，不会出现 全标记为1 或+ 1 的三角形 按照上述的构造，我们可以得出如下引理 引理2 5 按照上述的构造得出的极大大平面图所对应的诱导圈符号控制数达到 界值 证明：不妨设极大平面图g ( i y ( g ) i _ n ) 是按照上述的构造得出来的，同时厂是按照上 述的构造标记得到的s c d e 由引理2 4 得出图g 的所有诱导圈都是三角形由于，使 得每一个三角形满足八c 3 ) = 1 ，所以得出 八g ) = f ( e ) = 主zf ( c ) = 扣 e e e ( g ) c 懿 其中够表示图g 的基本圈的集合，也可以说是g 的面的边界的集合根据欧拉公式可 得出 l 够i = i e ( g ) i i y ( g ) i + 2 = 2 n 一4 所以 以。( g ) f ( g ) = n 一2 由引理2 1 可知 综上可得，心( g ) = 甩一2 即证 矗( g ) n 一2 综上可知，我们得出对于极大平面图g ( i v ( g ) i = ，1 ) ，以。( g ) n 一2 的界是紧的 口 2 3 所有诱导圈是c 3 的极大平面图的诱导圈符号控制数 首先，我们给出一个事实 1 0 华东师范大学平面图的诱导圈符号控制数问题 对于点数为4 的极大平面图g ，显然心( g ) = 2 ；同时我们不难发现，g 是一个 中心对称图形，对于任意一个使得心( g ) = 2 的s c d f 在无序意义下都是相同的换 句话说，只要保证了其边界满足f ( c 3 ) = l ，它的内部总是可以得到对应的标号使 得矗( g ) = 2 鉴于上述事实，我们就可以对一个诱导圈全是g 的极大平面图g 进行一些操 作不妨记点数为4 的极大平面图为a 若g 中含有a 作为其诱导子图，那么我们就 把a 的内部点去掉，这样就构成了一个新图g l ；若g l 中含有a 作为其诱导子图，那么 我们把a 的内部点去掉，这样就又构成了一个新图g 2 ；对得到的新图继续进行上述的 操作，直到得到的瓯中不再含有a 作为其诱导子图由于这个操作与a 有关，因此我 们简称该操作为a 操作 在上述的a 操作中，每一步所得到的g f ( f k ) 都是一个极大平面图，并且其所 有的诱导圈都是三角形因为在a 中的所有边都不可能成为a 外面其它诱导圈的边， 所以不会对a 外面的结构产生影响同时，g 的任意一个s c d f 对产生的新图g f 也 都是成立的，因为a 的内部的标记不影响a 外边的标记；反过来，满足g f 的任意一 个s c d f 都可以应用与g f - l ，只需在去掉的a 中添加上对应的标号即可所以，只要 我们找到g t 的诱导圈符号控制函数，我们就可以得到g 的诱导圈符号控制函数，同 时，若y 2 ( g t ) = s ，则心( g ) = j + k 我们定义两个集合， 集合形在2 2 节中加点的方法构造出来的极大平面图的集合 集合所有的诱导圈都是c 3 的极大平面图的集合 接下来我们证明一个引理 引理2 6 集合澎与集合是等价的 证明：由引理2 4 可知，澎中的任意一个极大平面图的诱导圈都是g ，故澎显 然成立 接下来我们要证明出彤即可 取g ，且i y ( g ) = 咒1 若n = 4 ，则g = a ，即g 虎，；显然成立 若n = 5 ，则边数m = 9 ，除去边界的3 条边，内部还有6 条边；那么一定存在一个 点与边界三点相连，把原三角面分成三个三角面。而另外一点恰好分布在其中的一个 华东师范大学平面图的诱导圈符号控制数问题 三角面内，则其必与所在三角面的三顶点相连，而此时恰好构成了a 诱导子图反过来 说，相当于在一个c 3 中添加一个点后，然后又在其中一个三角面内添加一个点，这正 符合澎的构造过程故g 形成立 利用归纳法，假设r l = k 时引理是成立的，下面考虑当玎= k + l 时的情况 当n = k + l 时，若在g 内存在一点v 恰好与g 的边界三角形的三个顶点相连，那 么此时就把g 这一三角面分成了三个三角面；并且每一个三角面都是诱导圈全是三角 形的极大平面图，即都属于但是，所得的每一个极大平面图的点数都不大于足；由 假设可知所分得的极大平面图也都属于形所以，我们可以认为是在c 3 中先加了 点 ，然后陆续再加各个面内的点，因此g 澎成立 现在假设不存在上述的点那么我们可以记g 的边界点为：，l ，屹，v 3 ；那么对于任 一个边界点，都至少与g 的内部一个点相连不失一般性，假设i , t l 与内部点相连的最 少，不妨记做：u l u 2 ，；那么由极大平面性可知，在比l ，h 2 ，中一定存在一条 由圪到玢的最短路p 故在p 上一定存在一点( g 内部的) 与屹相连若不然，p 与 边l ：2 1 p 3 恰好构成了一个围长大于3 的诱导圈，这与g 的性质相矛盾同时，我们敢断 言，p 上的任意一点都与屹相连假设存在一点u f 不与屹相连，而在p 上与其相连的 且与屹相连的点为“，u s ( 1 f s ) ，那么我们就可以得到经过u l ，u f ，u ， ，2 的这样一个 诱导圈，显然其围长大于3 这与g 的性质相矛盾，则p 上的每一个点都与也相连，因 此p 上与，3 相连的点也恰好与圪相连，而该点也是1 ，l 的邻居，所以该点与y l ，屹，均都 相连，即与g 的边界三角形的三个顶点相连，这与假设不存在这样的点相矛盾 所以，当n = k + l 时，一定存在g 澎故澎 综上所述， 。学= 。祝 得证 根据上述的引理，现在我们给出本节的重要定理 口 定理2 7一个极大平面图g 满足i v ( g ) l = r l ，如果它的所有诱导圈都是c 3 ，那 么y 羔( g ) = n 一2 证明：由引理2 6 可知，g 形，是可以由构造得到，同样我们也可以构造出它 的s c d e 有引理2 5 可得 矗( g ) = n 一2 1 2 华东师范大学平面图的诱导圈符号控制数问题 得证口 2 4 含有c k ( k 4 ) 诱导圈的极大平面图的y 乏( g ) 极大平面图中除了所有的诱导圈都是g 的极大平面图之外，还有很多极大平面图 是含有g ( 七4 ) 诱导圈的例如图【2 】中的图g 就含有c 4 诱导圈在上节中，我们已 经考虑了所有诱导圈都是g 的极大平面图，接下来我们就考虑含有q ( 七4 ) 诱导圈 的极大平面图 由欧拉公式可以知道，极大平面图g ( i v ( g ) i = 胛) ，边数l ( g ) l = m = 3 n 一6 ，g 的顶 点平均度为 一2 m ：型 6 一= = 一 l f ( e i ) “ 其中e f 为公共边 g 一釜彩l 二 图8 ：变换举例 由于两个极大平面最多有一边公用，同时日是一个树，公共边最多只能是k 一 1 条从而不难得出 f ( g ) k 一( k 一1 ) = l ； 1 9 华东师范大学平面图的诱导圈符号控制数问题 由，的任意性，即得出 y 2 ( g ) = m i n f ( g ) l f 是g 的一个s c d f 1 得证口 这一个界是准确的，如图 8 】，g 是由奇圈构成的图，日是对应的新图，易知矗( g ) = l ，对应的一个s c d f 已经标记在上面 3 2 6 ( g ) - - 3 的图的诱导圈符号控制数 徐宝根在 2 8 】中给出了如下猜想， 猜想任意6 ( g ) = 3 的图g ，y 2 ( g ) 1 该猜想的前提首先是对于6 ( g ) = 3 的这类图其诱导圈符号控制数是有常数下 界的假定这一前提是成立的，本节针对这一常数下界的取值，指出这个常数下界不 是1 接下来我们就用构造的方法给出证明 h 图9 ：构造最小度为3 的图 曝 1 层 2 层 3 层 k l 屡 爆 假设存在一个最小度为3 的图g ，满足v 2 ( o ) = 1 现在构造一个新的图日，步骤如 下： ( 1 ) ，选取一个点，作为第o 层； 2 0 。全毋 a公 久0 、叁 华东师范大学平面图的诱导圈符号控制数问题 ( 2 ) ，给这个点做出三个儿子，作为第1 层； ( 3 ) ，给第l 层的每个点作出两个儿子，作为第2 层； ( 4 ) ，给第f 层的每个点作出两个儿子，作为第f + 1 层( 1 i 2 同时，矗( 甄) = 2 ，且6 ( k 4 ) = 3 ，这说明这一 常数下界也不会大于2 因此我们得出如下结论， 结论3 2 对于任意图g ，满足6 ( g ) = 3 ，若矗( g ) 有常数下界，则矗( g ) 2 虽然我们给出了更确切的结论，但是最小度是3 的图的诱导圈符号控制数的下 界还是没有证明出来；同时对于任意的2 连通图，其诱导圈符号控制数的下界是不 是l 这一问题也没有给出证明 2 1 第四章总结 本文主要研究了极大平面图、2 连通平面图和最小度是3 的图的诱导圈符号控 制数问题；解决了徐宝根在 2 8 】中其中的一个猜想，同时也对另外两个猜想做了一些研 究下面总结一下本文的主要结果： 一、极大平面图的s c d f ( 1 ) ( 定理2 7 木) 设g ( i v ( g ) i = n ) 是一个极大平面图，7 2 ( g ) = 以一2 当且仅当它的所有 诱导圈都是g ( 2 ) ( 定理2 1 0 ) 设g ( i v ( g ) i = n ) 是一个极大平面图，矗( g ) 力当且仅当g 有一 个诱导圈g ( 七4 ) 上述关于极大平面图的结果解决了徐宝根在 2 8 】中的猜想： 如果g 是一个顶点数n 3 的极大平面图，则矗( g ) = ，l 一2 指出这一猜想是错误的，同时完善了极大平面图的诱导圈符号控制数理论 二、2 连通平面图和6 ( g ) = 3 图的s c d f ( 1 ) ( 定理3 1 ) 任意2 - 连通的平面图g ，其r 2