（运筹学与控制论专业论文）平面图的3可选择性.pdf

摘要 平面图的3 可选择性 摘要 1 9 7 9 年，p e r d s s 等人刻画了2 可选择图并提出猜想：每一个平面 图都是5 可选择的，且存在着不是4 可选择的平面图1 9 9 3 年，v o i g t 成 功地构造出了不是4 可选择的平面图，随后，t h o m a s s e n 证明了每一个 平面图都是5 可选择的由此，自然产生这样一个问题：哪些平面图 是4 可选择的，哪些平面图是3 可选择的? 1 9 9 6 年，g u t n e 赶明了这个问 题是n p 困难的最近，m i c k a g lm o n t a s s i e r 提出：哪些条件能保证每个 平面图都是3 可选择的? 因此，寻找平面图是3 或4 可选择的充分条件 成为图的染色理论中的一个重要研究课题本文关注平面图的3 可选 择性， 本文在前人的工作基础上继续研究平面图的3 可选择性问题，证 明了： ( 1 ) 每一个不含4 ，5 ，9 圈且任意两个三角形距离至少为3 的平面 图是3 可选择的 ( 2 ) 每一个不合4 ，6 ，8 ，9 圈的平面图是3 可选择的 ( 3 ) 每一个不舍4 ，7 ，8 ，9 圈的平面图是3 可选择的 关键词：平面图，3 可选择性，圈，距离 a b s t r a c t 3 - c h o o s a b l l i t yo fp l a n h f igr a p h s a b s t r a c t i n1 9 7 9 ，re r d t ，se ta lc o n j e c t u r e d t h a te v e r yp l a n a rg r a p hi s5 - c h o o s a b l e a n dt h e r ea r ep l a n a rg r a p h sw h i c ha r en o t4 一c h o o s a b l e m o r et h a no n e d e c a d el a t e r , t h ec o n j e c t u r ew a ss e t t l e db yv _ o i g ta n dt h o m a s s e n m o r e p r e c i s e l y , 、b i g tc o n s t r u c t e dap l a n a rg r a p hw h i c hi sn o t4 - c h o o s a b l e a n d t h o m a s s e np r o v e dt h a te v e r yp l a n a rg r a p hi s5 一c h o o s a b l e an a t u r a lp r o b l e mo nc h o o s a b i l i t yo f p l a n a rg r a p h si st od e t e r m i n ew h e t h e ra g i v e np l a n a r g r a p hi s3 - c h o o s a b l e ，o r4 - c h o o s a b l e s o o nl a t e r , g u t n e rp r o v e dt h a tt h e p r o b l e mi sn p h a r d r e c e n t l nm i c k a 占lm o n t a s s i e ra s k e d ：w h a ta r et h e s u f f i c i e n tc o n d i t i o n sf o rap l a n a rg r a p ht ob e3 - c h o o s a b l e ? t h i sd i s s e r t a - l i o n sc o n c e r n s3 - c h o o s a b i l i t yo f p l a n a l g r a p h s f o l l o w i n gp r e c e d e n tw o r k s ，t h i sd i s s e r t a t i o n ss t u d i e s3 - c h o o s a b i l i t y p r o b l e mo fp l a n a rg r a p h s t h em a i nr e s u l t so b t m n e dm t h i sd i s s e r t a t i o n s m a yb es u m m a r i z e da sf o l l o w s ： ( 1 ) e v e r yp l a n a rg r a p hw i t h o u t4 - ，5 - a n d9 - c y c l e s ，a n dw r h o u tt r i - a n g l e sa td i s t a n c el e s st h a n3i s3 - c h o o s a b l e ( 2 ) e v e r yp l a n a rg r a p hw i t h o u tc y c l e so fl e n g t h4 ，6 ，8 ，o r9i s3 - c h o o s a b l e ( 3 ) e v e r yp l a n a rg r a p hw i t h o u tc y c l e so fl e n g t h4 ，7 ，8 ，o r9i s3 一 c h o o s a b l e k e yw o r d s ：p l a n a rg r a p h ，3 一c h o o s a b i l i t y , c y c l e ，d i s t a n c e l i 学位论文独创性声明 本人声明所里交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。论文中除了特别加以标注和致谢的地方外，不包含其他人或其他 机构已经发表或撰写过的研究成果。其他同志对本研究的启发和所做的贡献均 已在论文中作了明确的声明并表示了谢意。 研究生签名：讹亮日期：弘呵1 z 12 - 学位论文使用授权声明 本人完全了解浙江师范大学有关保留、使用学位论文的规定，即：学校有 权保留送交论文的复印件和电子文档，允许论文被查阅和借阅，可以采用影 印、缩印或扫描等手段保存、汇编学位论文。同意浙江师范大学可以用不同方 式在不同媒体上发表、传播论文的全部或部分内容。保密的学位论文在解密后 遵守此协议。 研究生签名：沈高 导师签名：歪左前日期：弘币，2 f 浙江师范大学学位论文诚信承诺书 我承诺自觉遵守浙江师范大学研究生学术道德规范管理 条例。我的学位论文中凡引用他人已经发表或未发表的成 果、数据、观点等，均已明确注明并详细列出有关文献的名 称、作者、年份、刊物名称和出版文献的出版机构、出版地和 版次等内容。论文中未注明的内容为本人的研究成果。 如有违反，本人接受处罚并承担一切责任。 承诺人( 研究生) ：沈克 指导教师：奶前 一、绪论 ( 一) 、基本概念 一、绪论 在本节中，我们定义一些本学位论文中耍用到的图论的基本术语与符号一 个有序对g = ( v e ) 称为一个无向图，其中y 是一个有限集合，局黾y 中元素的 某些无序对的集合矿中的元素叫做图g 的顶点，e 中的元素玎叶做图g 的边通常 用y ( g ) 、e ( g ) 分别表示图g 的顶点集合、边集合，没有重边和环的图叫做简单 图除非特别指出，本文研究的图均指有限简单无向图 常用u ， 表示g 中的点，用e 表示g 中的边若边e = m ，e ( g ) ，则说“和 在g 中 相邻，或u 和口互为邻点；这时也说“和v 是e 的端点若点v 是边e 的端点，则说 与e 在g 中 相关联把g 中与顶点。相关联的边的条数叫做。在图g 中的度数，记作d c ( 。) ，在不 引起混淆情况下也可简记为d ( 口) 若d ( ) = 。则称w 是k 点若d ( t ，) k ，则称v 为 一个+ 点类似地可定义k 一点图g 中的点的最小和最大的度数分别记作6 ( g ) ( 或6 ) 和a ( c ) ( 或) 设s 是，( g ) 的一个非空真子集，则g s 表示从g 中删去s 内 的所有顶点以及这些顶点相关联的边所得到的子图通常m e s 表示为g 的 由s 导出的子图 。个可平面图是一个可以画在e u c l i d 平面上且能使得边仅在端点处相交的 圈一个平面图是一个可平面图在e u c l i d 平面上实现边仅在端点处相交的一个 特殊画法设图g 是平面图，常用f ( g ) 表示面集合，对于每个面，f ( g ) ，g 中围 绕，的闭途径的长度叫做，在g 中的度，记为d ( ，) 若d ( ，) = k ( 酬，) k ，d ( f ) ) ， 则称，为一个k 面( + 面，r 一面) 常把3 面叫做三角形若面，的边界是圈，则称，是 简单面若顶点 ( 边e ) 在面，的边界上，则说”( e ) 与，在g 中相关联用y ( ，) 表示 与，相关联的点所形成的集合若两个面至少有一条公共边，则称这两个面是相邻 的又若这两个面只有两个公共点，则称它们是正规相邻的 图g 的一个正常k 一顶点染色是一个映射咖：v 一 1 ，2 ，k ) 使得相邻的 顶点接受不同的色如果g 有一个正常k 一顶点染色，则称g 是顶点可染的，简 称g 是k 可染的g 的染色数是使得g 是正常k 顶点可染的最小的非负整数k 图g 的一个顶点色列表是一个颜色集合簇厶它指定g 的每个顶点口一个颜 色集合三p ) 若g 有一个正常的顶点染色妒使得对每一个顶点秽e 有妒( 掣) l ( 口) ，则称g 为l 顶点可染的若对每一个满足i l ( v ) l = k ，t ，v 的l ，g 都是l 一顶 一、绪论 点可染的，则称g 是顶点可选择的，简称g 是可选择的g 的顶点列表色数是使 得g 是一顶点可选择的最小的非负整数女 本文所用术语和符号基本上与文献【l 】中一致。本节中未介绍的其他圈论术 语将在必要时予以阐述 ( 二) 、平面图3 可选择问题的研究概况与本文的研究工作 图的染色理论是图论中晟重要的分支之一，在无线通讯频道分配、舰队维 护、任务分派、交通定向等诸多领域都有着广泛的应用，见文献【2 】，本学位论文 主要研究了平面图的顶点列表染色 1 9 7 9 年，e r d o s 等人刻画了2 可选择图并提出猜想：每一个平面图都是5 可选择 的，且存在着不是4 可选择的平面图【3 j 时隔十多年，这一猜想最终被v o i g t 和t h o m a s s e n 所证实： 1 9 9 3 年，v o i g t 成功地构造出了不是4 可选择的平面图 4 】。 1 9 9 4 年。t h o m a s s e n i l t 明了如下著名定理： 定理1 1 博l 每个平面图都是5 可选择的 由此，自然产生这样一个问题：哪些平面图足4 可选择的，哪些平面图是3 可选 择的? i 9 9 6 匀z ，g a r n e r 【6 i 证明了这个阏题是n p 困难的因此，寻找平匿图是3 或4 可 选择的充分条件成为图的染色理论中个重要研究课题本文关注平面图的3 可 选择性 1 9 7 6 年，s t e i n b e r g 猜想：每一个无4 ，5 圈的平面图是3 可染的后e r d d s 建议将此 猜想的条件适当放宽：满足每一个无j 圈“，i ) 的平面图是3 可染的最小正整 数i 是多少? 到目前为止，最好的结果t 扫b o r o d m 等人在文献【7 】中给出：i = 7 平面图3 可选类似的问题i 扫m o n t a s s i e r 在文献 8 】中提出： 问题1 1 【8 】满足每一个无j 圈( 4 j ) 的平面图是3 可选的最小正整数i 是多 少? 对于问题1 1 ，到目前为止最好的结果渤= 9 这由m o n t a s s i e r 在文献【8 】和l i z h a n g 等在文献 9 i q a 给出了证明当然，这一结果的证明，首先要归功于b o r o d i n 在 文献【1 0 】中给出的几个结构i 盈v o i g t 在2 0 0 3 年成功地构造出了无4 ，5 圈的平面图 一2 一 一、绪论 不是3 可选择的例子【“1 ，故而此问题中的i 6 鉴于此，m o n t a s s i e r 给出了平面 图3 可选择的以下一个猜想： 猜想1 1 【8 1 每一个无4 ，5 ，6 圈的平面图是3 可选的 除了问题1 1 外，m o n t a s s i e r 在文献【8 】中还提出了以下一个问题 向题1 2 s l 平面图是3 可选择的充分条件有哪些? 对于问题1 2 。就我们所知，到目前为止，主要有以下一些结果 a l o n 和t a r i e s 早在1 9 9 2 年证明了以下结果 定理1 2i t 2 ) 每一个平面二部图都是3 可选择的 t h o m a s s e n 毛e 1 9 9 5 年给出了以下结论 定理1 31 1 3 】每一个无3 ，4 圈的平面图都足3 可选择的 l a m 等人相当于证明了以下结果 定理1 4 ( 1 4 1 每一个无3 ，5 ，6 圈的平面图都是3 可选择的 l iz h a n g _ 币, 1 b a o y i n d u r e n gw u 在文献【9 】和文献【1 5 仲给出了以下结论： 定理1 5设g 是平面图，如果它满足以下条件之一 ( 1 ) 州g 不含有4 ，5 ，6 ，9 圈； ( 2 ) t ”1g 不含有4 ，5 ，7 ，9 图 则g 是3 可选择的 m o n t a s s i e r 等人在文献d 6 给出了以下结论 一3 一 一、绪论 定理1 , 61 1 6 1 设g 是平面图，如果它满足以下条件之一： ( 1 ) g 不含有4 ，5 圈且任意两个三角形距离至少为4 ； ( 2 ) g 不含有4 ，5 ，6 圈且任意两个三角形距离至少为3 则g 是3 可选择的 本文在第二章、第三章和第四章分别证明了以下结果 ( 1 ) 每一个不含4 ，5 ，9 圈且任意两个三角形距离至少为3 的平面图是3 可选 择的 ( 2 ) 【7 j 每一个不含4 ，6 ，8 ，9 圈的平面图是3 可选择的 ( 3 ) 每一个不含4 ，7 ，g ，9 罔的平面图是3 可选择的 这些结论是对问题1 2 的一些已有结论的有力补充 一4 _ 二、不含4 5 ，9 嘲平而陶的3 可选择性 二、不含4 ，5 ，9 圈平面图的3 可选择性 本节将给出平面图是3 可选择的一个新的充分条件，即 定理2 1每一个不含4 ，5 ，9 圈并且任意两个三角形距离至少为3 的平面图是3 可 选择的 ( 一) 、极小非3 可选择图的结构 设g 是非3 可选择图若g 的任何真予图h 都是3 可选择的，则称g 是极小 非3 可选择的下述引理2 1 是显然的 引理2 1 若g 是极小非3 可选择图，则d ( g ) 3 把仅带有一条弦的惫( 4 ) 圈叫做带弦圈设日是g 的一个点导出子图， 若日同构于一个带弦女圈，则称日为g 的一个e 子图作为g 的e 子图，若还满足 除弦上的一个端点在g 中可能为4 点外，其余的点在g 中都是3 点，则称日为g 的一 个特殊e 子图简称日为g 的一个s e 子图 引理2 2若g 是极小非3 可选择图，则g 不含s o 子图 证盼假设g 含有s o 子图设置是g 的一个s e 予图根据g 不是3 可选择的可 知，存在g 的一个色列表l = l ( v ) l i l ( v ) i = 3 ， y ( g ) ) ，使得g 不是l 可染 的设z ，a l ，a 2 ，a 。，y ，口1 ，b 2 ，目。r l , 1 ，m 1 ，依次排列在口的外圈上， o 是仃的唯一弦令g ，= g 一矿( 日) ，上是l 在g 上的限制由g 的极小性，是l 可 染的设c 是g 的一个l 7 染色不失一般性，设z 为4 点根据日的定义，除了耖之外， v ( 日) 中的每一个其它点z ，恰有一个邻点口7 g 令三( 钞) = 工( ”) c 0 ，) ，移可； 三7 ( 鲈) = l ( 可) ，则得到日的一个色列表l 7 下面将证明日是l 7 可染的，因此g 是l 可 染的，从而得到矛盾 若存在某种色a 上，( a ) ( a + - ) 对某个 1 ，2 ，犯一1 ) 成立，则先 把a 染给a ，然后可依次将a 一1 ，a 一2 ，a 1 ，z ，b 丌 ，b i ，y ，如，爿。一1 ，a + l 染 好，从而得到日的一个l 7 染色因此，不妨设l 7 ( a 1 ) = l 7 ( a 2 ) 一= l 7 ( a ) 若存 在某种色b l 7 ( z ) 二7 1 ) ，则可先把6 染给。，然后按顺序最。，b 1 ，y ， ，a 1 即 可把日染好故可设l 7 ( $ ) = l 7 ( a 1 ) = l 7 ( a ：) = l 7 ( 4 。) 由对称性可 设三7 ( 。) = l 7 ( b 1 ) = l ( b 2 ) 一= 上，( b 。) 因而可设上( z ) = u ( a 1 ) = 一5 一 - 二、不含4 ，5 9 嘲平而翻的3 可选择性 l 7 2 ) = l ( a ；) = l ( b l ) = l 7 ( b 2 ) 一= l 7 ( 且。) ： c ，此时先按顺 序b l ，b 。，z ，a 1 ，如给各顶点染色，由于y 在日上的三个邻点z ，b 1 ，a n 染 的色不是c 就是d 而己( y ) i 3 ，故此时y 也可染好这就证明了日是l 可染的，从 而完成了引理2 2 的证明口 ( 二) 、定理2 1 的证明 将所有没有4 ，5 ，9 圈，且任意两个三角形的距离都不小于3 的平面图所形成 的图类记为g 假如定理2 1 不成立，即g 中存在着非3 可选择平面图从9 中选取 一个顶点数尽可能少的非3 可选择平面图，记为g ，则g 满足引理2 1 和引理2 2 显 然g 是连通的 由于g 中任意两个三角形距离至少为3 且无4 ，5 圈，下面的断言2 1 是显然的 断言2 1g 无4 面和5 面，且g 中的6 面，7 面和8 面都是简单面 断言2 2 在g 中，3 面和8 面不能相邻；3 面和6 ，7 面只能正规相邻 证明：只证明3 面和6 面只能正规相邻其余结论可以更加容易或相类似地得 到证明设t = x y z 是一个3 面，f = x y o p q r 是一个与t 相邻的6 面若z = 0 ， 贝u d ( y ) = 2 ，这与引理2 1 相矛盾若。= p ，则。茹r 卯形成4 圈，矛盾由对称性知， z r ，。g 即证明了，和丁只能正规相邻 口 断言2 3g 中不存在以下构形：三个面两两相邻，其中一个为3 面，另两个为6 面 证明：首先证明：若6 面与6 面相邻，则它们只能正规相邻设，= x y o p q r ，7 = x y 0 7 p “qr 若0 = 0 ，贝o d ( v ) = 2 ，这与引理1 矛盾若0 = p ，则o y x r q p 形成5 圈， 矛盾若0 = q ，则o y o p q 形成4 圈，矛盾若0 p = r ，月j j o y o p q r 形成5 圈，矛盾故 而o ，萑y ( ，) 同理可证萑y ( ，) 再由对称性得到r 7 隹y ( ，) ，一隹y ( ，) 因 此，和，7 只能正规相邻 又由断言2 2 ，3 面与6 面只能正规相邻，故若一个3 面，两个6 面两两相邻，则它 们只能两两正规相邻，而这又会形成9 圈。矛盾口 由欧拉公式i v ( c ) 一i e ( g ) i + i f ( g ) i = 2 和等式d ( v ) = 2 i e ( g ) i = v v ( g ) d ( ，) ，可得以下等式： ，f ( g ) - 一6 一 = 、不含4 ，5 ，9 嘲平而陶的3 可选择性 ( d ( 口) - 6 ) + ( 2 d ( ，) 一6 ) = 一1 2 v ( g )，( g ) 从上式出发，定义v ( c ) uf ( g ) 上的一个权函数 ：对口y ( g ) ，卸( ) = d ( u ) 一6 。对f f ( g ) ， ( ，) = 2 d ( f ) 一6 于是，g 的所有顶点和面的权和为一1 2 下 面将定义一个重新分配v ( g ) uf ( g ) 中各元素的权的规则用伽0 ) 表示按所定义 的规则重新分配v ( c ) u 尸( g ) 中各元素的权后元素z 的权一方面，重新分配权后， 总权和不变：另一方面，将证明对每一个z v ( c ) uf ( g ) 有 7 ( z ) 0 这样就得 到下面的矛盾不等式，从而完成定理2 i 的证明 0 ( 茁) 一”( z ) = - 1 2 # y ( g ) u f ( g ) 4 y ( g ) u f ( g ) 用r 0 一可) 表示元素礴专移到元素! ，的权量用r 和一) 和r ( 一z ) 分别表面元 素转出的权量汞i 接收到的权量定义权转移规则如下： r 1 转移至3 点口的权 设r 是与 相关联的6 + 面 r i 1 若口与3 面相关联，则r ( ，一钉) = r 1 2 若口不与3 面利关联，则t ( ，一口) = 1 r 2 转移至4 点的杈 若口与3 面相关联，设，和g 郁是与秽相关联的6 + 面，其中，与3 面相邻，g 不与3 面 相邻 r 2 1 若g 为7 面，则r ( g 一”) = ，- , - ( f 一”) = i r 2 2 若g 不为7 面则f 0 一t j ) = 1 7 - ( ，一移) = ； 若v 不与3 面相关联 r 2 3 设，是与口相关联的6 + 面，则下( ，一郇) = ； r 3 转移至5 点u 的权 设，是与相关联的6 + 面 r 3 1 若u 与3 面树关联，则7 u 一) = i r 3 2 若口不与3 面相关联，则r ( ，一 1 3 ) = 一1 一 二、不含4 5 9 幽平而罔的3 可选择性 r 4 转移至6 面，的权 设，与3 面t 相邻v ( t ) nv ( f ) = p ，暑，) ，v ( t ) y ( ，) = z ，g 是与，和丁都相邻 的7 + 面 r 4 1 若d ( 。) = d ( y ) = 3 ，则r 0 一f ) = r 4 2 若z 和y 中有一个为3 点另一个为4 + 点，并且d ( z ) 4 ，则7 - ( 夕一，) = ； 口关于点的权的验证 注意到权规则r 1 ，r 2 ，r 3 分别是为了确保当 是3 点，4 a ，或5 点时，都有t 1 7 ( 秽) o 而设计的，而对于6 + 点来说，不涉及到权的转移，所以，帕y ( g ) 都有 ( 口) 0 口关于面的权的验证 设，为6 面若，不与任何3 面相邻根据规则易知f ( ，一) 1x6 = 6 ， 故w ( ，) 2 6 6 6 = 0 若，与3 面丁相邻由断言2 ，2 知，6 而与3 面只能正规相邻故可设v ( t ) nv ( f ) = 矗，可 ，v ( t ) v ( f ) = z 当z 和可都是3 点时，设与面，丁都相邻的两个面分别为g l 和9 2 根据断言2 3 ， m 和伪都是7 + 面由r 4 1 ，r ( g l f ) = ；，r 渤一f ) = 困r ( ，一) 2x ；+ 4 1 = 7 ，故 7 ( ，) 2 6 6 + 2x 一7 = 0 当z 和可中有一个为3 点另一个为4 + 点时，不妨设d ) = 3 ，a ( y ) 4 若d ( z ) = 3 ，根据引理2 2 ，上除了! ，外，至少还存在另一个4 十点”因三角形距离至少为3 ， 故“不与3 面相关联，从而r ( ，一u ) i 1 由规则得到7 一( ，一z ) = ；，r ( ，一y ) i 因下( ，一) s ；+ i + + l 3 0 当x l r r l ：l y 都为4 + 点时，由规则易得到r ( ，一z ) = ；，7 - ( ，一咖= ；因7 r ( ，一) s 2x ；+ 1 4 0 若，与3 面t 相邻由断言2 2 知，7 面与3 面只能正规相邻故可设y ( t ) n y ( ，) = p ，订，v ( t ) v ( f ) = 如) 一8 二、不含4 ，5 ，9 圈平面陶的3 可选择性 当z 为3 点时，根据引理2 2 ，y ( ，) 中必存在一个4 + 点，设u 是y ( ，) 中的一个4 + 点 若z ，可都是3 点，i t r 4 1 ，至多要转移；给一个相邻的6 面再因r ( 一。) ：；， r ( ，一y ) = ；，r ( j ：一“) 故r ( ，一) 2 ；+ ；+ + 1 4 = 8 ，从 而 ( ，) 0 若z ，3 ，中至少有一个4 + 点，同样f l ：l r 4 1 ，至多要转；给一个相邻 的6 面再因7 - ( ，一z ) + r ( ，一曲；+ ；，故r ( ，一) i + i + + l 5 8 ，从 而 7 ( ，) 0 当z 为4 + 点时，若z 和y 都是3 点，则由规则知此时，不用转移权给相邻的6 面 因此，t ( f 一) 2 ；+ 1 5 = 8 ，从而 7 ( ，) 0 若。和y 中个为3 点另一个 为4 + 点，由r 4 2 ，厂至多要转移 给一个相邻的6 面因r ( ，一) i 3 + i 3 1 - i 1 + 1 5 0 口关于面的权的验证 设，为3 面由权规则r 3 ，葫7 ( ，) = 一1 + 3xj 1 = 0 设，为5 面因为5 面不能与3 面相邻，由r 1 2 和r 2 2 ，丁( ，一) 5x = 1 故而 c 7 ( ，) 1 1 = 0 设，为7 面因为7 面不能与3 面相邻，由r l 和r 2 ，r ( s 一) 7x ； 3 3 = 0 设，为1 2 + 面易得c h ( ，) ( d ( ，) 一4 ) 一i 4 ) = 亟售坐芝0 设，为1 1 面若，至少与一个4 + 点相关联，则由r l 和r 2 ，7 - ( ，一) 1 0x ；+ j 1 = 7 ，从而i c h ( f ) 7 7 = 0 故以下设与，相关联的点都是3 点由于g 中不含有 相邻3 面，n f 至多和五个3 面相邻若，与五个3 面相邻，因g 中不含构形g 2 ，故此 时，不再与任何5 面相邻。从而根据r l ，c h 7 ( ，) = 7 1 0 ；一 = 0 若，至多与 1 4 三、无4 6 ，8 9 豳平面图的3 可选择性 四个3 面相邻，也就是说，最多关联八个每个从，中得到；权的点从而由r l 得到 c ( ，) 7 8 ；一3 0 最后设，为l o 面由本部分对图g 的假设，最多关联九个3 点 情形1 ，至多关联八个3 点 根据权规则，c h ( i ) 6 一( 8x ；+ 2x ) = 0 情形2 ，恰关联九个3 点令口是y ( ，) 上唯一的4 + 点 情形2 1 口是5 + 点 根据权规则，易得7 ( ，一秒) = 0 ，从而，c h ( f ) 6 9 ；= 0 情形2 2 秒是4 点 着九个3 点中每个均从面，得到；权，则，必与五个3 面相邻并且口必与这五 个3 面中的一个相关联，把这个3 面记做t 设，7 t 是与点训相关联且与，相邻的 蔚，见图3 4 ，那么易知，7 不是5 面由权规贝j j r 2 3 下( ，一t ，) = 0 从而c h f f ) = 6 9 ；= 0 故以下设九个3 点中有一个3 点，记为从面，得到的权少于；由规 贝i j r i ，或者r ( ，一“) = ，或者，r ( 一= ；若7 - ( ，一u ) = ，则根据规贝f j r 2 ， 因r ( ，一口) 曼，从而得至t j c h ( ，) 6 一( 8x ；+ 2x ) = 0 若r ( ，一“) = ， 由规贝s j r l 2 ，钳不会与3 面相关联，实际上，u 与一个5 面和一个异于，的7 + 面相关 联令，7 是与u 相关联的那个5 面，令是u 在y ( ，) nv ( 1 7 ) 中唯一的邻点，见图3 5 当乜，t j 时，则u ，是一个与5 面相关联的3 点由权规则r 1 2 ，f ( ，一) = ，从 而得至r j c h ( ) 6 一( 7x ；+ 2 ；+ ) 0 以下假设= 钉若口不与3 面相 关联则由r 2 ，7 _ ( ，一秽) = 0 从而得蛰j c h ( f ) 6 一( 8 ；+ ；) 0 若目与 一个3 面相关联由引理3 1 的g 2 知，这个3 面不与面，相邻，也就是说，这个3 面 与面，相邻通过对面，点的简单分析，可以知道此时在矿( ，) 上的从，接收；权 的3 点的个数最多为七个( 其中一种可能的情形已经在图3 6 上表示出来) 从 而c h ( ，) 6 一( 7 ；+ ；+ i 1 + 击) 0 1 5 一 兰、无4 ，6 8 9 醐平面罔的3 可选择性 图3 4图3 5图3 6 ( - - ) 、非2 一连通条件下定理3 2 的i i e n f l 本部分将证明对于非2 - 连通的平面图，定理3 2 也是成立的，从而完成定 理3 2 的证明显然此时我们只需要考虑g 是连通且至少有一个割点的情形即可 设g 是一个满足以下条件的连通平面图： 。 ( 1 ) 至少有一个割点； ( 2 ) 6 ( g ) 3 ； ( 3 ) 不含有4 ，6 ，8 ，9 圈 以下我们将要证明图g 也必定含有一个其面上均为3 点的l o 面 反证法设g 不含有其面上均为3 点的j o 面下面我们将通过g 构造一个2 连 通的新图g 4 满足( 2 ) 、( 3 ) 两条并且不含有其面上均为3 点的l o 面这个结果显然将 与我们上一节刚证明的结论矛盾 设口足g 的一个终端块，, i j 为b 在g 中的割点，是含有终端块8 的面，口是 在b 上且异于钍的点显然，u 和口都在y ( ，) 中做b 的l o 个拷贝，记为b l ，b 2 ，b 1 0 在每个块b ( i = 1 ，2 ，1 0 ) 中，与点“和秒相对应的点分别记为u i 和q 把鼠， i = l ，2 ，1 0 按以下方法嵌入，中首先，令b = t 3 1 然后，对i = 2 ，3 ，1 0 ， 依次通过粘合点q l 和啦把且嵌k n y 中最后任取z y ( ，) 矿) ，粘合点口1 0 和 点z 把按上述过程得到的图记作g ，显然，在嵌入的过程中，可以保证g 7 仍为平 面图此外，g ，还有如下性质： ( 1 ) g 含有的割点数要比g 严格少； ( 2 ) 6 ( g 7 ) 3 ； ( 3 ) g ，不含有4 ，6 ，8 ，9 圈； 三、无4 。6 。8 9 n 平而图的3 可选择性 ( 4 ) g 中不含有面其上均为3 点的l o 面 性质( 2 ) 和( 3 ) 是显然的性质( 1 ) 是由于在g ，中“不为割点，故g 中的割点数至 少要比g 少一个以下说明性质“) 假设g 含有其面上均为3 点的l o 面f 。由g 的假 定知f 垡g 显然，f 譬b i i = 1 ，2 ，1 0 这得v d v ( f ) n 如l ，* 1 0 ) 口又 因f 本身是2 - 连通的，故妣，i = 1 ，2 ，l o ，均在y ( f ) 中从而，i v ( f ) l 1 1 ，矛盾 重复上述的构造过程，最终将得到2 _ 连通的图g ，它满足性质( 2 ) 、性质( 3 ) 和 性质( 4 ) 这与在本节中第二部分得到的结论相矛盾定理3 2 证毕 口 j 7 一 四、无4 7 8 9 嘲平面图的3 可选择性 四、无4 ，7 ，8 ，9 圈平面图的3 可选择性 本节将给出平面图是3 可选择的另一个充分条件即证明以下定理 定理4 1 每一个不含4 ，7 ，8 ，9 圈平面图是3 可选择的 ( 一) 、一些特殊的定义