（应用数学专业论文）图的l21标号及其算法.pdf

图的l ( 2 ，1 ) 一标号及其算法 摘要 图的l ( 2 ，1 ) 标号来源于h a l e 所介绍的频率分配问题设z 为非负整数集 合图g 的一个k - l ( 2 ，1 ) - 标号是映射：v ( c ) 一z ，使得对任意。，y y ( g ) ，当 如( z ，y ) = 1 时，有l 妒( z ) 一( ! ，) l 2 ；当d g ( z ，y ) = 2 时，有i ( z ) 一( 秒) l 1 并 称a ( g ) = m i n k l 存在g 的个k - l ( 2 ，1 ) 标号】为图g 的l ( 2 ，1 ) 标号数 对于任何最大度为a ( c ) 的图g ，g r i g g s 和y e h 猜想，入( g ) 2 ( g ) 近 年来，研究者围绕该猜想做了大量的工作，但迸展缓慢，最新的界是入( g ) 2 ( g ) + a ( g ) 一2 目前，关于图的l ( 2 ，1 ) 一标号问题的研究大都集中在证明该猜 想对某些特殊图成立 本文首先总结了近些年图的l ( 2 ，1 ) 一标号的主要结果和进展，然后对一些特 殊图类做了研究： ( 1 ) 研究仙人掌图g 的l ( 2 ，1 ) 一标号，证明了当a ( g ) 5 时，入( g ) ( g ) + 2 给出了a ( g ) = 3 ，4 时，入( g ) a ( g ) + 2 成立的若干条件，并刻画了( g ) = 3 ，4 以及入( g ) = a ( g ) + 3 的仙人掌图 图g 的线图l ( g ) 的l ( 2 ，1 ) 一标号实际上等价于图g 的l ( 2 ，1 ) 边- 标号通 常用a 7 ( g ) 表示图g 的l ( 2 ，1 ) 一边一标号数本文从算法的角度研究了两类图的 l ( 2 ，1 ) 边标号 ( 2 ) 对于( g ) = 3 的图g ，本文给出了一个线性时间算法，能够在线性时间 之内给出图g 的1 6 三( 2 ，1 ) 一边标号，从而得到了a ( q 1 6 的个算法证明，这 也说明了g r i g g s 和y e h 的猜想对于最大度为3 的图g 的线图是成立的 ( 3 ) 对于( g ) = ( l ( g ) ) = 3 的s u b c u b i c 图g ，本文给出了一个线性时问算 法，能够在线性时间之内给出图g 的9 - l ( 2 ，1 ) 一边一标号，从而得到了( g ) 冬9 韵 一个算法证明，这也说明了g r i g g s 和y e h 的猜想对于这类图g 的线图是成立的 i 关键词：l ( 2 ，1 ) 标号；l ( 2 ，1 ) 边标号：仙人掌图；s u b c u b i c ；算法 t h el ( 2 ，1 ) 一l a b e l i n ga n da l g o r i t h m o fg r a p h s a b s t r a c t t h el ( 2 ，1 ) 一l a b e l i n go fg r a p h sa r i s e sf r o mav a r i a t i o nf r e q u e n c ya s s i g n m e n t p r o b l e mb y h a l e l e tz b eas e to f n o n n e g a t i v ei n t e g e r s ，a nk - l ( 2 ，1 ) - l a b e l i n go fg i s a f u n c t i o n 咖：v ( c ) _ z ，s u c h t h a t ，f o ra n yt w ov e r t i c e sz ，y y ( g ) ，i ( z ) 一( 可) i 2i f d g ( z ，y ) = 1 ；a n di ( z ) 一矽( y ) i 1i f d a ( z ，y ) = 2 t h el ( 2 ，1 ) 一l a b e l i n gn u m b e r o fg ，d e n o t e db ya ( g ) ，i st h es m a l l e s tn u m b e rks u c ht h a tgh a sa nk - l ( 2 ，1 ) 一l a b e l i n g f o ra n yg r a p hgw i t hm a x i m u md e g r e e ( g ) ，g f i g g sa n dy e hc o n j e c t u r e dt h a t a ( g ) 2 ( g ) i nr e c e n ty e a r s ，s t u d e n t sd oa l o to fw o r kt op r o v et h a tc o n j e c t u r e ， h o w e v e r , t h en e wb o u n di sa ( g ) sa 2 ( g ) + a ( g ) 一2 n o w , t h em o s ts t u d yi st o c o n f i r mt h ec o n j e c t u r ef o rs o m ec l a s s e so fg r a p h s i nt h i st h e s i s ，w ef i r s t l ys u m m a r i z et h em a i nr e s u l t sa n de v o l u t i o no nt h el ( 2 ，1 ) - l a b e l i n gi nr e c e n ty e a r s ，t h e nw ei n v e s t i g a t es o m eg r a p h s ： ( 1 ) w ee x p l o r et h el ( 2 ，1 ) - l a b e l i n go f c a c t i ，a n dp r o v et h a ta ( g ) ( g ) + 2w h e n a ( g ) 5 w ep r e s e n ts e v e r a lc o n d i t i o n sf o r 入( g ) a ( c ) + 2w h e n ( g ) = 3 ，4 ， a n di l l u s t r a t es o m ec a c t if o ra ( g ) = a ( a ) + 3w h e n ( g ) = 3 ，4 t h el ( 2 ，1 ) 一l a b e l i n go fl ( g ) i sa n a l o g o u st ot h el ( 2 ，1 ) 一e d g e - l a b e l i n go fg w e u s u a l l yd e n o t e db y 入( g ) t h el ( 2 ，1 ) - e d g e - l a b e l i n gn u m b e r a c c o r d i n gt ot h ea l g o - r i t h m ，w ee x p l o r et h el ( 2 ，1 ) 一e d g e - l a b e l i n gp r o b l e mo ft w oc l a s s e so fg r a p h s ( 2 ) f o rag r a p hgw i t ha ( c ) = 3 ，w ep r e s e n tal i n e a rt i m ea l g o r i t h mt o1 6 l ( 2 ，1 ) 一e d g e - l a b e l i n gt h eg r a p hg s ow ep r o v et h a t 义( g ) 1 6a n ds h o wt h a tt h e c o n j e c t u r eo fg r i g g sa n dy e hi sc o n f i r m e df o rt h el i n eg r a p ho fg w i t ha ( g 1 = 3 ( 3 ) f o ras u b c u b i cg r a p hg w i t ha ( a ) = ( l ( g ) ) = 3 ，w ep r e s e n tal i n e a rt i m e a l g o r i t h mt o9 - l ( 2 ，1 ) 一e d g e l a b e l i n gt h eg r a p hg s ow ep r o v et h a ta ( g ) 9a n d s h o wt h a tt h ec o n j e c t u r eo fg r i g g sa n dy e hi sc o n f i r m e df o rt h el i n eg r a p ho fgw i t h t h ( g ) = ( l ( g ) ) = 3 k e y w o r d s ：l ( 2 ，1 ) 一l a b e l i n g ；l ( 2 ，1 ) 一e d g e l a b e l i n g ；c a c t i ；s u b c u b i c ；a l g o r i t h m i v 学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。论文中除了特别加以标注和致谢的地方外，不包含其他人或其他 机构已经发表或撰写过的研究成果。其他同志对本研究的启发和所做的贡献均 已在论文中作了明确的声明并表示了谢意。 研究生签名：计林日期：哆6 争 学位论文使用授权声明 本人完全了解浙江师范大学有关保留、使用学位论文的规定，即：学校有 权保留送交论文的复印件和电子文档，允许论文被查阅和借阅，可以采用影 印、缩印或扫描等手段保存、汇编学位论文。同意浙江师范大学可以用不同方 式在不同媒体上发表、传播论文的全部或部分内容。保密的学位论文在解密后 遵守此协议。 研究生签名：1 冲吞小 翩繇哗剐弘夸 浙江师范大学学位论文诚信承诺书 我承诺自觉遵守浙江师范大学研究生学术道德规范管理 条例。我的学位论文中凡引用他人已经发表或未发表的成 果、数据、观点等，均己明确注明并详细列出有关文献的名 称、作者、年份、刊物名称和出版文献的出版机构、出版地和 版次等内容。论文中未注明的内容为本人的研究成果。 如有违反，本人接受处罚并承担一切责任。 午 林戍 计l， 筠师髋教人导 范 一 承渚 1绪论 本学位论文主要考虑图的l ( 2 ，1 ) 一标号及其算法研究在本章里，我们先给出 与本文有关的一些问题的背景、定义和进展在给出综述之前，我们首先将引进 一些符号和概念，这些符号和概念将贯穿全文对本章没给出的符号和概念，我们 会在后面适当的地方给出对于那些文中末给出的符号和概念，可以在 1 】中找 到 1 1 基本概念 本文讨论的图均为无向、简单图对于图g ，令y ( g ) ，e ( g ) ，i v ( a ) l ，f e ( g ) i ， a ( a ) 和6 ( a ) 分别记为图的顶点集合，边集合，顶点数，边数，最大度和最小度若 边e = u v ，则称顶点u 与u 相邻，让( 或 ) 与e 关联对u v c a ) ，记d g ( u ) 表示g 内顶点u 的度d g ( u ，v ) 表示g 内顶点口之间的距离 定义1 1r 2 1 设g ( k e ) 为简单图称g 内的两条边e ，是相邻的( 距离为1 ) 当且 仅当存在一个点与e 和厂都关联称e ，的距离为2 当且仅当e ，不相邻，且存 在一条边与e 和厂都相邻对e e ( g ) ，记d v ( e ) 表示g 内边e 的度，d a ( e ，) 表 示g 内边e ，之间的距离 定义1 2 3 1 图g 的线图l ( a ) 是以e ( a ) 为顶点集合的图，其中两个顶点相邻当 且仅当它们在g 中是相邻边 定义1 3f l , 3 l 图g 的正常七一顶点染色是映射砂：v ( a ) _ 1 ，2 ，七) 使得任意 相邻顶点乱，v 有咖( 让) 妒( ) 图g 的色数x ( a ) 是最小的整数k 使得g 具有 k 顶点染色 定义1 40 , 3 1 图g 的正常角一边染色是映射：e ( c ) 一 1 ，2 ，七】使得任意相 邻边e ，有( e ) 矽( 厂) 图g 的边色数x ( g ) 是最小的整数k 使得g 具有七一边 染色 1 绪论 定义1 5f 4 1 设z 为非负整数集合图g 的一个l ( 2 ，1 ) - 标号是映射咖：v ( a ) _ z ， 使得对任意z ，y y ( g ) ，当d g ( z ，y ) = 1 时，有i 咖( z ) 一咖( 可) i 2 ；当d a ( x ，y ) = 2 时，有l ( z ) 一砂( 可) i 1 g 的一个k - l ( 2 ，1 ) - 标号是标号西：y ( c ) _ z ，使得对任 意z y ( g ) ，有西( z ) k 并称 a ( g ) = m i n k i 存在g 的一个k - l ( 2 ，1 ) - 标号) 为图g 的l ( 2 ，1 ) 标号数 定义1 6f 2 】设z 为非负整数集合图g 的边集e ( g ) 0 图g 的一个l ( 2 ，1 ) 一 边一标号是映射妒：e ( g ) _ z ，使得对任意e ，e ( g ) ，当d c ( e ，) = 1 时， 有l 妒( e ) 一e f t ) i 2 ；当d c ( e ，) = 2 时，有l ( e ) 一咖( 删1 g 的一个k l ( 2 ，1 ) 一边一标号是标号咖：e ( g ) 一z ，使得对任意e e ( g ) ，有砂( e ) k 并 称 入( g ) = m i n k 存在g 的一个k - l ( 2 ，1 ) 一边一标号 为图g 的l ( 2 ，1 ) 边标号数 1 2 应用背景与研究现状 图论是组合数学的一个分支，在现实世界中存在广泛的应用它的起源很早， 瑞士数学家欧拉( l e u l e r ) 在1 7 3 6 年解决了当时颇为有名的一个数学难题，即 “哥尼斯城堡七桥”问题，从而使欧拉成为图论和拓扑学的创始人欧拉将七桥 问题转化为一个数学模型，用四个顶点表示两岸和两个小岛，连接相应顶点的线 段表示桥此论文的发表标志着图论的诞生 早期图论与“数学游戏 密切联系直到1 8 4 7 年，基尔霍夫( k i r c h h o f f ) 运用 图论解决了电路理论中求解联立方程问题，第一次将图论运用于工程技术领域 18 5 7 年，凯莱( c a y l e y ) 在有机化学领域，计算饱和氢化物g - 2 n + 2 的同分异构体 数目时，发现了一族重要的图，称为树从此图论脱离解决“数学游戏”阶段，进 入解决各种实际问题，开始向其它科学领域渗透 2 0 世纪后，图论应用渗透到诸多其它科学领域，如物理学、化学、信息学、 运筹学、博奕论、计算机网络、社会学、语言学等2 0 世纪5 0 年代，由于计算 2 l 绪论 机的迅速发展，促使了组合学最优化算法研究，有力推动了图论的发展，使图论成 为数学领域中发展最快的分支之一。 图的染色是图论中重要组成部分，它来源于著名的四色猜想即对世界地图 或任何一个国家的行政区域地图，最多用四种颜色就可对其染色，使得凡是相邻 的国家或相邻的区域都着以不同的颜色美国的a p p e l 和h a k e n 于1 9 7 6 年借助 电子计算机证明了四色猜想成立从此四色猜想成了四色定理但是，用常规的数 学方法证明四色定理仍然是一个未获解决的问题 图染色这一迷人的研究领域，与概率论、矩阵论、群论等有着密切的联系， 同时包含着许多有趣的问题，从而吸引了众多学者的极大兴趣本学位论文将介 绍图论中新的研究课题图的标号理论，它来源于无线电领域，是某些图染色问题 的推广，有着十分广泛的应用和研究价值 在1 9 8 0 年，h a l e 5 1 提出了频率分配的理论及其应用频率分配问题来源于 现实世界无线电领域对于一个无线电发射台集合，当给每个发射台分配频率时， 会发现被分配相同或相近频率的发射台，由于地理位置相近或自然现象等原因可 能会产生干扰因此分配频率时就要使得相互干扰的无线电发射台所分配的频率 在允许范围之内 # h a l e1 5 1 将此问题归结成图的t - 染色问题构造图g = ( ve ) ，用顶点 集合v ( g ) 中顶点表示发射台，两个顶点之间存在一条边当且仅当对应的 发射台相互干扰给定图g 和非负整数集合t 图g 的t - 染色就是映射 ：v ( a ) _ o ，1 ，2 ，) ，使得 若z 可e ( g ) ，i ( z ) 一( 夕) ig t 为了达到资源优化配置，主要围绕以下参数进行研究：( 1 ) 3 - 染色的色数 x r ( a ) ，z r ( g ) = i i l i n i ( z ) f z y ( g ) 州为g 的t - 染色) ；( 2 ) t - 染色i 拘s p a n s p r ( c ) ，s p r ( g ) = m i n m a x l 咖( x ) 一( y ) l l x ，y y ( g ) - l 为g 的t - 染色) ；( 3 ) t - 染色的e d g es p a ne s p t ( g ) ，e s p t ( g ) = m i n m a x o ( x ) 一( y ) l l x y e ( g ) ) l 咖为 g 的t 染色 这一理论与图论中正常顶点染色有机联系在一起当t = o ，t - 染色就是 3 i 绪论 图论中图的正常顶点染色问题，另外图染色的许多算法可以得到应用频率分配 问题作为最优化问题引起了许多学者的研究兴趣，在过去的十儿年得到广泛地研 究 6 _ l o 】 r o b e r t st 4 1 ( 和g f i g g s 的个人交流) 提出了另外一种相似的有效的频率分配办 法，他提出在几个不同地点的无线电发射台有效地分配无线电频率，频率用非负 整数表示，使得相近的发射台分配不同的频率，极相近的发射台分配频率至少相 差2 ，从而使得这些发射台不会干扰研究内容在于确定无线电现实网络需要最 少频率，就能使较近的无线电发射台不发生干扰g f i g g s 和y e h 【4 】将这个问题归 结为图的l ( 2 ，1 ) 标号问题用图的顶点表示无线电发射台，如果图的两个顶点相 邻，表示两个无线电发射台非常相近如果图的两个顶点的距离为2 ，表示两 个无线电发射台相近 由于缺少无线电频率资源及光谱的使用密集化，因此优化频率资源配置及极 小化或消除频率的内在干扰，l ( 2 ，1 ) 标号问题就显得十分有研究价值许多学者 致力于该领域，得到许多有价值的结果 4 ，i l _ 2 5 】 g r i g g s 和y e h 【4 】确定了a ( r ) ，入( g ) 和a ( 眠) 的具体数值，其中r 是, 个 顶点的路，g 是礼个顶点的圈，是g 加上一个与g 中所有顶点都相邻的顶 点得到的图，称为佗一轮 对于死一立方体q 扛，j o n a sf i l l 证明了n + 3 入( q 死) g r i g g s 和y e h 【4 1 证明了 入( q n ) 2 n + 1 ，其中n 5 利用译码理论方法，w h i t t l e s e y , g e o r g e s 和m a u r o 1 1 2 1 证明了如下结论： 入( q 他) 2 盘+ 2 k - q + 1 2 ，其中住2 七一舔1sqsk + 1 特别地，a ( q 2 - 一七一1 ) 2 七一1 即有a ( q n ) 2 n ，其中佗3 对于最大度为a ( t ) 1 的树t ，g r i g g s 和y e h 【4 1 证明了a ( t ) + 1 入( t ) a ( t ) + 2 他们还证明了一般图的l ( 2 ，1 ) - 标号问题是n p 一完备的对于最大度为 ( g ) 1 的一般图g ，g f i g g s 和y e h 【4 1 证明了入( g ) 2 ( g ) + 2 a ( c ) 当g 为 3 一连通图时，上界改进为a ( g ) 2 ( g ) + 2 x ( a ) 一3 ，当g 是直径为2 的图时，上 界改进为久( g ) sa 2 ( g ) 此外，他们还提出了如下猜测： 4 1 绪论 猜想1 1 4 1 对任何最大度为a ( c ) 的图g ，总有a ( g ) a 2 ( g ) s a k a i 1 3 1 考虑了一类弦图，并证明对于任何弦图g ，有a ( g ) ( ( g ) + 3 ) 2 4 c h a n g 和k u of 1 4 1 把一般图g 的5 ( 2 ，1 ) 一标号数的上界改进为a ( g ) 2 ( g ) + ( g ) 之后，k r i l 和s k r e k o v s k if 1 5 1 将此上界改进为a ( g ) a 2 ( g ) + z x ( c ) 一1 最近，g o n c a l v e s 1 6 1 又将此上界进一步改进为a ( g ) 2 ( g ) q - a ( c ) 一2 但是这 离证明入( g ) a 2 ( g ) 还有很大的差距要直接证明g r i g g s 和y r e h 【4 】的猜想比较 困难目前，关于图的l ( 2 ，1 ) 标号问题的研究大都集中在证明该猜想对某些特殊 图成立 对于平面图的l ( 2 ，1 ) - 标号问题，研究得比较全面详细关于平面图的最初 结果见 1 7 】，作者证明了对于任何平面图g ，有a ( g ) 2 a ( g ) + 3 5 m o l l y 和 s a l a v a t i p o u r 1 8 1 将该上界改进为 a ( g ) + 9 0 w a n g 和l i bn 9 1 证明了围长至少为 5 的平面图g ，有入( g ) a ( a ) + 2 1 作为平面图的一类子集，树的l ( 2 ，1 ) 一标号 问题在 4 】中被全面地解决 在文献 2 】中，图g ( e ( g ) 0 ) 的线图l ( g ) 的己( 2 ，1 ) - 标号问题称为图g 的l ( 2 ，1 ) - 边一标号问题g e o r g e s 和m a u r o 研究了完全图，树，扎一维立方体，联 图的a 7 ( g ) 的上界和下界另外，作者证明对于a ( g ) 4 的图g ，有入7 ( g ) 2 ( a ( a ) 一1 ) ( ( g ) + 2 ) 文献 2 6 】改进这个上界得到： 引理1 1 2 6 1 对于a ( g ) 4 的图g ，a 7 ( g ) 2 a 2 ( g ) 一2 在文献【2 6 】中，朱海洋在理论上证明了对于( g ) = 3 的图g ，有入( g ) s1 6 对于a ( g ) = 3 的图g ，本文给出了一个线性时间算法，能够在线性时间之内 给出图g 的1 6 l ( 2 ，1 ) 边一标号，从而得到了入7 ( g ) 1 6 的一个算法证明，这也 说明了g r i g g s 和y e h 的猜想对于最大度为3 的图g 的线图是成立的对于 a ( g ) = ( l ( g ) ) = 3 的s u b c u b i c 图g ，本文给出了一个线性时间算法，能够在线 性时间之内给出图g 的9 - l ( 2 ，1 ) 边标号，从而得到了a 7 ( g ) 9 的一个算法证 明，这也说明了g r i g g s 和y e h 的猜想对于这类图g 的线图是成立的 5 2 仙人掌图的l ( 2 ，1 ) 一标号 本章主要研究仙人掌图的l ( 2 ，1 ) 标号问题本章分为三节，第一节介绍仙人 掌图的定义以及相关符号第二节研究满足一定条件的仙人掌图的l ( 2 ，1 ) 一标号 数第三节研究a ( c ) = 3 或4 的两类特殊仙人掌图的l ( 2 ，1 ) 标号数 2 1 定义及符号 定义2 1d i l 若图g 的每个块或者为一条边或者为一个圈，则称g 为仙人掌图 引理2 1 2 6 1 令g 为仙人掌图，a ( a ) 1 ，则十1 入( g ) + 3 为了文章叙述简洁，定义以下概念和符号设g 是个仙人掌图，且j c i = 佗， g 箬g 我们称点 g 是一个最大度点，若d ( v ) = ( g ) ；小度点，若 d ( v ) 1 ) 若砂( 乱) = 0 ，则西( ( 乱) ) 2 ，3 ，4 ，5 - 因此g 能被标为以下六个情况： 2 0 ( 3 5 1 ) 4 ；( 2 0 4 ) ；2 0 ( 5 3 1 ) 4 ；3 ( 0 0 2 ) 5 1 ；( 3 0 5 ) ；4 0 ( 5 3 0 ) 2 若砂( 似) = 1 ，则咖( ( u ) ) 3 ，4 ，5 ) 因此g 能被标为以下三个情况：3 1 ( 4 0 2 ) 5 ；( 3 1 5 ) ；4 ( 1 5 3 ) 0 2 。若痧( u ) = 2 ， 则( ( 让) ) o ，4 ，5 ) 因此g 能被标为以下三个情况：( 0 2 4 ) ；( 0 2 5 ) ；4 2 ( 5 1 3 ) 0 情况2 g i = 3 m + 1 ( m 1 ) 若o ( u ) = 0 ，则咖( ( 札) ) 2 ，3 ，4 ，5 ) 因此g 能被标为以下六个情况： 2 ( 0 3 5 ) ；( 2 0 4 ) 1 5 0 4 ；2 0 ( 5 1 3 ) 0 4 ；3 0 4 1 ( 3 5 1 ) ；( 3 0 5 ) 1 ；4 ( 0 5 2 ) 若( u ) = 1 ，则咖( ( u ) ) 3 ，4 ，5 ) 因此g 能被标为以下三个情况：3 1 4 0 ( 3 1 5 ) ；( 3 1 5 ) 0 ；4 1 5 0 ( 4 2 0 ) 若 ( 心) = 2 ，则西( ( u ) ) _ o ，4 ，5 ) 因此g 能被标为以下三个情况：0 2 4 0 ( 5 1 3 ) ； ( 0 2 5 ) 3 ；4 ( 2 5 0 ) 情况3l g i = 3 m + 2 ( m 1 ) 若妒( 让) = 0 ，则( ( 就) ) 2 ，3 ，4 ，5 因此g 能被标为以下六个情况： 2 0 ( 3 1 5 ) ；( 2 0 4 ) 1 5 ；( 2 0 5 ) 1 4 ；4 0 ( 3 5 1 ) ；3 0 5 ( 2 0 4 ) 1 5 ；4 0 ( 5 3 1 ) 若( 让) = 1 ，贝0 ( ( 钆) ) 3 ，4 ，5 ) 因此g 能被标为以下三个情况：4 ( 1 3 5 ) 0 ；3 1 ( 5 2 0 ) ；4 1 ( 5 0 2 ) 若砂( t ) = 2 ， 则( ( u ) ) o ，4 ，5 】- 因此c 能被标为以下三个情况：( 0 2 4 ) 1 5 ；0 2 ( 5 1 3 ) ； 4 2 ( 5 31 ) 证明完毕 通过类似的分析，我们可得到以下的引理 引理2 5 设x u y 是圈g ，n 4 上的一段路若多是x u y 上的一个k - l ( 2 ，1 ) 一标 号，k 7 ，则能延拓成g 上的一个k - l ( 2 ，1 ) 一标号 7 2 仙人掌图的l ( 2 ，1 ) 一标号 引理2 6 设x u y 是一段路，添加中间点u 的一条关联边，使其另一端连接一个 3 一圈g ，这样组成的图记为g 设妒是x u y 的个5 - l ( 2 ，1 ) 一标号则能延拓成 g 的一个5 - l ( 2 ，1 ) 标号，除下列情况以外：( z u y ) = ( o ，2 ，5 ) ，其中( 钍) 为2 或 5 ，以及咖( x u y ) = o ，3 ，5 ) ，其中矽( u ) 为。或3 引理2 7 设x u y 是一段路，添加一个3 一圈岛，使其与x u y 有一个公共点u 这 样组成的图记为g 设移是x u y 的一个6 - l ( 2 ，1 ) 标号则能延拓成g 的一个 6 - l ( 2 ，1 ) 标号，除下列情况以外：( “) = 1 ， 矽( z ) ，( ) ) = 3 ，4 ) ， 3 ，6 ) 或 5 ，6 ； 矽( 让) = 2 ， ( z ) ，咖( y ) ，= o ，4 ) 或 o ，6 - ；妒( u ) = 3 ， 咖( z ) ，( ) 】- = ( o ，1 ) 或 5 ，6 】； 砂( 乱) = 4 ，1 咖( z ) ，( 可) ) = o ，6 ) 或 2 ，6 ；以及矽( 扎) = 5 ， 妒( z ) ，矽( 可) ) = 2 ，3 ， o ，3 ) 或 o ，1 ) 定理2 1 设g 是一个不含3 一圈的仙人掌图，则( g ) - 4 - l 入( g ) ( g ) - 4 - 2 证明：易见，仅须证明第二个不等式即可我们对g 的阶数进行归纳假设当 l g i = 2 或a ( g ) = 2 时，定理显然成立设g 是一个i g i 3 且a ( g ) 3 的 仙人掌图若g 包含一个叶子点u 记其唯一的邻点为w 根据归纳假设可得 a ( g 一 ) a ( g u ) + 2 a ( g ) + 2 假设是图g u 的一个( ( g ) - 4 - 2 ) 一 l ( 2 ，1 ) 一标号由于d g 一。( 叫) a ( g ) 一1 ，则至多有( g ) 一1 + 3 = ( g ) + 2 个 标号对v 禁用那么至少还剩1 个标号可以标给u 因此西能延拓成g 的一个 ( a ( g ) 4 - 2 ) n ( 2 ，1 ) 标号假设g 不含叶子点，则设c 是g 的一个终端圈，并设u 是g 内c 的锚点设z 和y 是乱在c 内的两个邻点，令p = c 一乱一z y 根据 归纳假设可得a ( g p ) ( g p ) + 2 ( g ) 4 - 2 假设是图g p 的一个 ( ( g ) + 2 ) - n ( 2 ，1 ) 一标号若f c i 6 或( g ) 5 ，则根据引理2 4 和引n 2 5 ，痧能 延拓成g 的一个( a ( g ) + 2 ) - n ( 2 ，1 ) - 标号 因此，我们假设4 i c i 5 且3 a ( g ) 4 当( g ) = 3 时，记v 是u 的 不同于z 和y 的另一个邻点若l c l = 4 ，记a 是c 上不同于u ，z 以及耖的另一个 点在引理2 4 的证明中可以发现，矽不能延拓成c 的一个( ( g ) + 2 ) n ( 2 ，1 ) 标号 当且仅当西( u ) = 0 ， 矽( z ) ，妒( 可) - = 2 ，4 ) 或 ( z ) ，咖( 秒) ) = ( 2 ，5 ) ，或者，( u ) = 2 ， _ ( 。) ，咖( ) ) = o ，4 ) r 2 仙人掌图的l ( 2 ，1 ) 一标号 若( 让) = 0 ，不失一般性，假设( z ) = 2 ，咖( 可) = 4 则矽( 口) = 3 或5 若 多( 口) = 3 ，则将z 的标号改为5 ，将a 标为1 即将c 标为5 0 4 1 根据归纳假设， 我们可以得到g 的一个( a ( g ) + 2 ) 一l ( 2 ，1 ) 一标号若( u ) = 5 ，则将z 的标号改 为3 ，将。标为1 即将c 标为3 0 4 1 ，根据归纳假设，我们亦可得到g 的一个 ( a ( g ) + 2 ) 一l ( 2 ，1 ) - 标号 若( 乱) = 0 ，妒( z ) = 2 ，咖( y ) = 5 贝u 西( u ) = 3 或4 若毋( u ) = 3 ，贝0 将z 的 标号改为4 ，将a 标为1 即将c 标为4 0 5 1 根据归纳假设，我们可得g 的一个 ( a ( g ) + 2 ) 一l ( 2 ，1 ) 一标号若咖( ) = 4 ，则将z 的标号改为3 ，将a 标为1 即将c 标为3 0 5 1 根据归纳假设，我们可得g 的一个( a ( g ) + 2 ) - l ( 2 ，1 ) 一标号 若( u ) = 2 ，咖( z ) = 0 ，( 可) = 4 则( 口) = 5 由于d ( v ) 3 ，则至少有一 个标号i o ，1 ，3 ) 满足i 隹( ( 口) ) 如果i = 0 ，则将u 的标号改为0 ，将z 的 标号改为3 ，将a 标为1 即将c 标为3 0 4 1 根据归纳假设，我们可得g 的二_ 个 ( ( g ) + 2 ) - l ( 2 ，1 ) 一标号如果i = 1 ，则将u 的标号改为1 ，将x 的标号改为3 ，将a 标为0 即将c 标为31 4 0 根据归纳假设，我们可得g 的一个( ( g ) + 2 ) 一l ( 2 ，1 ) 一 标号如果i = 3 ，则将乱的标号改为3 ，将y 的标号改为l ，将a 标为4 即将c 标 为0 3 1 4 根据归纳假设，我们亦可得g 的一个( ( g ) + 2 ) 一l ( 2 ，1 ) 一标号 若i c i = 5 ，记b 为a 和z 的公共邻点在引理2 4 的证明中可以发现，不能延 拓成c 的一个( a ( g ) + 2 ) 一l ( 2 ，1 ) 一标号当且仅当( “) = 0 ， 矽( z ) ，痧( y ) 】= 3 ，5 不失一般性，我们假设p ) = 3 ，痧( 可) = 5 ，那么痧扣) = 2 或4 若( ) = 2 ，则将 z 的标号改为4 ，将a 标为3 ，将b 标为1 即将c 标为4 0 5 3 1 根据归纳假设，我们 能得到g 的一个( ( g ) + 2 ) 一n ( 2 ，1 ) 一标号若( u ) = 4 ，则将z 的标号改为2 ，将 a 标为1 ，将b 标为4 即将c 标为2 0 5 1 4 根据归纳假设，我们能得到g 的一个 ( ( g ) + 2 ) - l ( 2 ，1 ) 标号 类似于上述的分析，当( g ) = 4 ，我们仍能得到g 的一个( ( g ) + 2 ) - z ( 2 ，1 ) 标号，由于较为简单，我们省略其证明证明完毕 定理2 2 设g 是个( g ) 5 的仙人掌图，则a ( a ) 十1 a ( e ) ( g ) + 2 9 2 仙人掌图的l ( 2 ，1 ) 一标号 证明：易见，仅需证明第二个不等式即可我们对g 的阶数进行归纳假设当 i g l = 2 或( g ) = 2 时，定理显然成立设g 是一个i g i 3 且a ( g ) 3 的仙 人掌图若g 包含一个叶子点，类似于定理2 1 的证明，结论成立因此我们假设g 不含有叶子点设c 是g 的一个终端圈且设u 是g 内c 的锚点设z 和y 是u 在c 内的两个邻点若c 喾g ，类似于定理2 1 的证明，结论成立 假设c 竺岛且d ( 乱) ( g ) 根据归纳假设，可得入( g z y ) a ( g z y ) + 2 a ( g ) + 2 假设是图g z y 的一个( ( g ) + 2 ) 一l ( 2 ，1 ) 一标号 由于d g 一茁一掣( “) ( g ) 一3 ，则至多有a ( g ) 一3 + 3 = ( g ) 个标号对z 和y 禁 用那么至少还剩3 个不同的标号可以标给z 和g 易见矽能延拓成g 的一个 ( a ( g ) + 2 ) 一l ( 2 ，1 ) 标号 因此，我们假设c 竺c 3 且d ( u ) = ( g ) 由于a ( g ) 5 ，根据对终端圈 的定义，我们可以得知至少存在另一个终端圈c 7 ，其锚点也为“不失一般 性，我们假设c 7 笔c 3 ，记c = u a b 设a = z ，y ，a ，6 ) 根据归纳假设，可得 入( g a ) ( g a ) + 2 a ( g ) + 2 假设是图g a 的一个( a ( g ) 十2 ) l ( 2 ，1 ) 一标号由于d a a ( 乱) a ( g ) 一4 ，则至多有( g ) 一4 + 3 = a ( g ) 一1 个标 号对x ，y 。a 以及b 禁用那么至少还剩4 个不同的标号可以标给x ，y ，a 和b 易 见咖能延拓成g 的一个( a ( g ) + 2 ) 一l ( 2 ，1 ) 标号证明完毕 定理2 3 设g 是一个a ( g ) = 3 的仙人掌图若对任何两个3 圈g ，有 d ( 岛，c 3 ) 3 ，且对任何一个3 圈伤和一个圈g ，4 i 6 ，有d ( g ，q ) 2 则 4 a ( g ) 5 证明：易见，仅需证明第二个不等式即可我们对g 的阶数进行归纳假设当 i g l = 4 时，定理显然成立设g 是一个j gj 5 的仙人掌图若g 包含一个叶 子点，类似于定理2 1 的证明，结论成立因此我们假设g 不含有叶子点设c 是 g 的一个终端圈且设缸是g 内c 的铺点设z 和可是缸在e 内的两个邻点若 c 喾c 3 或d ( u ) ( g ) ，则类似于定n 2 1 的证明，结论成立 因此我们假设c 竺c 3 且d ( 乱) = a ( a ) = 3 根据归纳假设，我们有 入( g c ) ( g c ) + 2 5 设西是图g c 的一个5 - l ( 2 ，1 ) 一标号设移是让 1 0 2 仙人掌图的l ( 2 ，1 ) 一标号 的不同于z 和y 的另一个邻点 假设d ( u ) = 2 根据引理2 3 ，我们仅需考虑情况( 耖) o ，1 ，2 ) 若( 口) = 0 ， 那么c 可以由标号1 ，3 和5 正常标出，则能延拓成g 的一个5 - l ( 2 ，1 ) 一标号 若咖( u ) ( 1 ，2 ) ，那么c 可以由标号o ，3 和5 正常标出，则妒能延拓成g 的一个 5 - l ( 2 ，1 ) - 标号 因此我们假设d ( v ) = 3 更进一步的，我们假设g 的任何一个终端圈，其 锚点都包含一个度数为3 的邻点由于对于g 内的任何两个3 圈岛，都有 d ( 仍，c 3 ) 3 ，因此v 的任何一个异于钆的邻点都不会属于一个3 一圈则u 属 于一个圈q ，其中i q l 7 再者，我们可以选择终端圈c ，使得存在一个点 加y ( q ) ，其中d ( w ) = 3 ，且在q 上的非v j 点，其度数或者为2 ，或者有一个邻点 属于终端圈记w o 是叫的一个不在q 上的邻点，记叫1 ，w 2 是叫在q 上的两个 邻点 设日是g w o 且满足w v ( h ) 的一个分支根据归纳假设，我们有 a ( c h ) ( g h ) + 2 5 设咖是g 一日的一个5 - l ( 2 ，1 ) 标号我们根据 顺时针方向，以( 叫。) ，( 叫) ，矽( 叫2 ) 为开始顺序，罗列q 上的标号根据引理2 3 ， 只需考虑妒( 叫o ) = 0 ，1 或2 的情况我们能使延拓成g 的一个5 - l ( 2 ，1 ) 一标号 如下： 情况1i q i = 3 m ( m 3 ) 假设妒( 姚) = 0 由于d g 一日( t u o ) 2 ，则2 ，3 和5 中至少有1 个标号不出 现在集合( g 一日( 伽o ) ) 中若2 譬( g 一日( 姚) ) ，则可将q 标为4 2 ( 5 1 3 ) 0 若 3 圣咖( g 一日( 伽o ) ) ，则可将q 标为( 5 3 1 ) 若5 簪咖( g h ( 叫o ) ) ，则可将q 标为 ( 3 5 1 ) 根据引理2 6 ，能延拓成g 的一个5 - l ( 2 ，1 ) - 标号 假设妒( 叫o ) = 1 由于d g 一日( 叫o ) s2 ，则3 ，4 和5 中至少有1 个标号不出 现在集合移( g 一日( 仰o ) ) 中若3 簪西( g 日( 蛐) ) ，则可将q 标为5 3 ( 0 2 4 ) 1 若 4 圣西( g 一日( 咖) ) ，则可将q 标为( 2 4 0 ) 若5 簪( g 一日( 叫o ) ) ，则可将q 标为 3 5 ( 0 2 4 ) t 根据引理2 6 ，能延拓成g 的一个5 - l ( 2 ，1 ) 标号 假设西( 咖) = 2 由于d g h ( w 0 ) 2 ，则o ，4 和5 中至少有1 个标号不出 l l ! 些茎堕塑墨( ! ：1 2 ：堡呈 现在集合妒( g 一日( o ) ) 中若0 隹妒( g 一日( 妣) ) ，则可将q 标为3 ( 0 4 2 ) 5 1 若 4 岳砂( g 一日( 叫o ) ) ，则可将q 标为0 4 ( 1 3 5 ) 0