（运筹学与控制论专业论文）一些乘积图的l21圆标号.pdf

一、学位论文独创性声明 东南大学学位论文 独创性声明及使用授权的说明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果 尽我所知，除了文中特别加以标明和致谢的地方外，论文中不包含其他人已经发表或撰写 过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材料与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意 二、关于学位论文使用授权的说明 签名：堑啦日期：冱i 亿= i ：匍 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复 印件和电子文档，可以采用影印、缩印或其他复制手段保存论文本人电子文档的内容和纸 质论文的内容相一致除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包 括刊登) 论文的全部或部分内容论文的公布( 包括刊登) 授权东南大学研究生院办理 签名 导师签名：三蚴期：l 立：2 ：7 d 摘要 l ( 2 ，1 ) 标号问题是经典着色问题的一个推广，而l ( 2 ，1 ) 圆标号问题是对l ( 2 ，1 ) 标号问 题的一个变形设k 是一个正整数，：v ( g ) 一 o ，1 ，2 ，k 一1 ) 是一个映射，如果 ，c u ，一，c ，i 七 给定两个图g 和日，g 和日的直积图，记为g h ，其顶点集合定义为v ( c h ) = v ( a ) x v ( h ) ，边集合定义为e ( g x h ) = ( ( z ，耖) ，( z 7 ，矿) ) i z e ( g ) 且y y t e ( 日) ) 给定两个 图g 和日，g 和日的笛卡尔乘积图，记为g o h ，其顶点集合定义为v ( g d h ) = v ( g ) y ( 日) ， 边集合定义为e ( g d h ) = ( ( z ，3 ) ，( z - ，f f ) ) l z = z 且y y e ( h ) 或者y = y 7 且z z 7 e ( g ) 】 本文完全确定了路和完全图的直积图的l ( 2 ，1 ) 圆标号数，以及路和圈的笛卡尔乘积图 的l ( 2 ，1 ) 一圆标号数 关键词：l ( 2 ，1 ) 圆标号数；直积；笛卡尔积；路；圈；完全图 a b s t r a c t t h el ( 2 ，1 ) l a b e l i n gp r o b l e mi sag e n e r a l i z a t i o no fc l a s s i cg r a p hc o l o r i n g ，a n dt h el ( 2 ，1 ) c i r c u l a rl a b e l i n gi sat r a n s f o r m a t i o no fl ( 2 ，1 ) l a b e l i n g g i v e nag r a p hga n da l li n t e g e rk ，a k - l ( 2 ，1 ) 一l a b e l i n go fg i saf u n c t i o nf ：v ( g ) 叫 o ，1 ，k 一1 s u c ht h a t t ( “) 一f ( v ) l 七 2 ，征d g ( 们_ 1 ， 【1 ， i fd v ( u ，口) = 2 w h e r e 知：= m i n i x l ，k l x l t h el ( 2 ，1 ) 一c i r c u l a rl a b e l i n gn u m b e ro fg ，d e n o t e db ya 2 ，1 ( g ) ，i s d e f i n e db y o r 2 ，i ( g ) = m i n k ：t h e r ei s ak - l ( 2 ，1 ) 一c i r c u l a rl a b e l i n go fg g i v e nt w og r a p l l sga n dh ，t h ed i r e c tp r o d u c to fga n dh i st h eg r a p hgxhw i t hv e r t e xs e t v ( g x h ) = v ( g ) x v ( h ) a n d t h e e d g es e te ( g x h ) = ( ( z ，y ) ，( z ，可) ) l z z 7 e ( g ) a n dy y t e ( 日) ) g i v e nt w og r a p h sga n dh t h ec a r t e s i a np r o d u c to fga n dhi st h eg r a p hg o hw i t hv e r t e xs e t v ( e h ) = v ( g ) v ( h ) a n d t h ee d g es e te ( g d h ) = f i x ，可) ，( ，! ，) ) l z = a n d 可矿e ( h ) o ry = 矿a n dz z e ( g ) t h i st h e s i sc o m p l e t e l yd e t e r m i n e st h el ( 2 ，1 ) - c i r c u l a rl a b e l i n gn u m b e r so ft h ed i r e c tp r o d u c t o fap a t ha n dac o m p l e t eg r a p ha n dt h ec a r t e s i a np r o d u c to fap a t ha n dac y c l e k e yw o r d s ：l ( 2 ，1 ) 一c k c u l a rl a b e l i n gn u m b e r ；d i r e c tp r o d u c t ；c a r t e s i a np r o d u c t ；p a t h ；c y c l e ； c o m p l e t eg r a p h i i 第二章p m 的l ( 2 ，1 ) 一圆标号 3 2 1 前言 3 2 2p m 的l ( 2 ，1 ) 一圆标号数 4 第三章p m 口g 的l ( 2 ，1 ) - 圆标号 9 3 1 前言 9 3 2 尸m 口g 的厶( 2 ，1 ) 一圆标号数 致谢 参考文献 i i i 第一章引言 1 1 背景 考虑到我们要给一个地区内几处不同的无线电发射站分配频道，为了避免相互干扰，距 离较近的发射站分配到的频道应彼此间隔又由于频道资源本身的稀缺性，我们要求使用尽 可能少的频道段那么至少要给它们分配多少波段合适呢? 这个实际中的问题在1 9 8 0 年首 次被h a l e 1 】用图论的知识来阐述，也因此引入了d 着色这个概念接下来，r o b e r t s 2 】提出 了频道分配问题模型的一个变形，即用非负整数代表频道，距离较近的发射站使用不同的频 道，距离特别近的发射站使用的频道至少差2 受此启发，g r i g g s 和y e h 3 】用图论中的术语 将距离量化，如果两个发射站距离特别近，在图上反映为代表这两个发射站的顶点相邻；如 果两个发射站比较近，相应顶点在图上的距离为2 这就是近十几年来激起大家无限兴趣的 l ( 2 ，1 ) 标号问题 图g 的一个l ( 2 ，1 ) 一标号是指一个映射f ：v ( g ) _ o ，1 ，2 ，且满足条件：如果 伽e ( g ) ，那么i f ( u ) 一，( u ) l 2 ；如果d g ( t i ，v ) = 2 ，那么i f ( u ) 一，( t ，) 1 l ( 2 ，1 ) 标号，的 跨度定义为m a x u ，。y ( g ) l ，( u ) 一，( 口) i ，记作s p a 佗( 1 ) 图g 的所有l ( 2 ，1 ) 一标号中跨度最小的 数定义为图g 的l ( 2 ，1 ) 一标号数，记作a 2 ，1 ( g ) 如果8 p a n ( f ) = a 2 ，l ( g ) ，则称，是图g 的一 个a 2 ，1 标号图g 的l ( 2 ，1 ) 圆标号是对l ( 2 ，1 ) 标号的一个变形，即将l ( 2 ，1 ) 一标号中直线 上的距离变形成圆上的距离设k 是一个正整数，图g 的一个k - l ( 2 ，1 ) 一圆标号是指一个映 射f ：v ( v ) _ o ，1 ，2 ，k 一1 ，且满足条件：如果钆口e ( g ) ，那么i f ( u ) 一f ( v ) l k 2 ；如果 d g ( t i ， ) = 2 ，那么l f ( u ) 一f ( v ) l k 1 ，其中i x l k ：- - - - m i n i x i ，k 一】图g 的所有k - l ( 2 ，1 ) 一圆标 号中最小的k 定义为图g 的l ( 2 ，1 ) 一圆标号数，记作c r 2 ，l ( g ) 如果图g 的某个k - l ( 2 ，1 ) 圆 标号，的k = 0 2 ，l ( g ) ，则称，是图g 的一个a 2 1 - 标号 对于图g 的l ( 2 ，1 ) 一标号数和l ( 2 ，1 ) 一圆标号数，有如下关系 引理1 1 1 【4 】对于任意的图g ，有 a 2 ，l ( g ) + 1 眈，i ( g ) a 2 ，l ( g ) + 2 ( 1 1 ) 但通常即使已知了a 2 ，l ( g ) 的情况来确定a 2 ，1 ( c ) 究竟是入2 ，i ( g ) + 1 还是a 2 ，l ( g ) + 2 也 不是件简单的事情 1 东南大学硕士学位论文 一直以来，对于图的l ( 2 ，1 ) 圆标号( l 0 ，后) 一圆标号) 的研究并不多见对于一些比较特 殊的相对规则的图，已经有了完整的结果l a i n ，l i n ，w u 5 】给出了j k 的情形下两个完全 图笛卡尔乘积图和直积图的l ( j ，七) 圆标号数而w u 6 】利用两个完全图笛卡尔乘积图与直 积图之间的互补性，得出了j 一 一 m m m 第二章p m 的l ( 2 ，1 ) 一圆标号 2 1 前言 设l 是图g 的一个k - l ( 2 ，1 ) 圆标号，对于0 i k 一1 ，记l t = t ，y ( g ) l l ( u ) = 班 如= i l i l ，这样厶中的点可以表示为z ；( 1 j u 如果如= 1 ，将z i 简记为记 h ( l ) = 0 ：厶= g ) ，称为l 的洞集合 g ( l ) = a ：厶= a ，l i - i = l i + l = 1 且x i 一1 z 件1 e ( g ) ，称为l 的缝集合 m ( l ) = 0 ：l i 2 ) ，称为l 的多重标号集合 其中所有的下标都对k 取模图g 的一个最小( 洞) 盯( 2 ，1 ) 一标号是指图g 的所有盯( 2 ，1 ) 标号中洞最少的标号，记作亏( 2 ，1 ) 标号 以下的引理在【4 】中已经被证明 引理2 1 1 【4 】设l 是图g 的子( 2 ，1 ) - 标号若h 日( l ) ，则l h l = l h + l o ；并且由 三 一lu l a + l 生成的诱导子图是一个完美匹配供中下标对矿取模，而且，若k l = l h + l = 1 ， 是一个缝 引理2 1 2 【4 】设l 是图g 的子( 2 ，1 ) 标号，那么g ( l ) = g 或者m ( l ) = 乃 设s y ( g ) ，若s 中任意两点的距离都大于2 ，则称s 为v ( a ) 的一个2 - 独立集图g 的极大2 独立集的势称为图g 的2 一独立数，记作a 2 ( g ) 设工是图g 的一个a ( 2 ，1 ) 一标号， 则对所有的i o ，1 ，盯一1 ) ，l 是图g 的一个2 _ 独立集 设f m 是由m 个点构成的路，是阶为n 的完全图为了方便，我们将，i m 的顶点记作 x l ，x 2 ，z m ，的顶点记作y l ，y 2 ，鲰对于虢y ( p m ) ，如y ( ) ，将p m 的 顶点( x i ，珊) 简记为( i ，歹) 记 巩= ( t ，j ) ：歹= 1 ，2 ，n ) ( i = 1 ，2 ，m ) ； y j = ( t ，歹) ：i = 1 ，2 ，m ) u = 1 ，2 ，礼) 图1 表示b 与甄的直积图 3 东南大学硕士学位论文 4 图1 只 l i n 和l a m 已经给出了路和完全图的直积图的l ( 2 ，1 ) 一标号数 定理2 1 3 【7 】设m 2 ，n 3 是整数，则 入2 。l ( p m ) = 2 n 一2 g n 一2 ， 2 ；一1 ) + 1 ， 墨n一12 ，- 2 ( n 一1 ) + 2 ， m = 2 ： m = 3 或者4 ，n 是偶数i m = 3 或者4 ，n 是奇数i ( 2 1 ) m 5 ，n 是偶数j m 5 ，n 是奇数 2 2 岛的l ( 2 ，1 ) 一圆标号数 关于路和完全图的直积图的l ( 2 ，1 ) 圆标号数，本文也得出了完整的结果 定理2 2 1 设m 2 ，n 3 是整数，则 f 2 俨1 ，m - 2 ； o 2 ，1 ( p mx ) = n ，m 3 ，n 是偶数； ( 2 2 ) 【；( 礼一1 ) + 3 ，m 3 ，n 是奇数 证明： ( i ) 首先考虑m = 2 时的情形根据定理2 1 3 和引理1 1 1 可知，0 2 ，l ( 最x j 厶) 2 n 一1 对 j = 1 ，2 ，佗，令f ( o ，j ) ) = ，( ( 2 ，j ) ) = 2 u 一1 ) ，不难看出，是p 2 的一个( 2 n - 1 ) l ( 2 ，1 ) 一 圆标号，即0 2 ，l ( 恳xj 厶) 2 n 一1 从而0 2 1 ( b ) = 2 n 一1 得证 东南大学硕士学位论文 5 ( i i ) 接下来考虑m = 3 时的情形设工是忍j 厶的个子( 2 ，1 ) 一标号，首先证明序列 f o ，z l ，f 矿一1 的下列性质 ( p 1 ) v t 【0 ，盯一1 】都有0 “2 成立； ( p 2 ) v t 【0 ，盯一1 1 ，如果“= 0 ，男瞄么l t - 1 = l t + t = 2 ； ( p 3 ) v t 【0 ，盯一1 1 ，如果“= 2 ，那么i t - 1 十l t + l 1 ； ( p 4 ) v t 0 ，盯一1 】，如果“= 1 ，那么l t - t 十l t + l 3 因为c x 2 ( p 3 x k ) = 2 ，并且p 3 x k 的任何个极大2 独立集都有这样的结构： ( i ，j ) ，( 2 ，j ) ， 其中i 1 ，3 ) ，歹 1 ，2 ，竹) 所以( p 1 ) 成立 因为i 【0 盯一1 】i = 盯n 3 ，根据( p 1 ) 有i t - 1 = l t + t = 2 ， l 与l 件1 分别位于巧与巧，其中工j 7 【l ，他】且j j ，这样就没有点可以标t ，矛盾，所 以( p 4 ) 成立 这四条性质可以用图2 来表示 从上图不难看出v t 【0 ，盯一1 】有篙f p 6 ，箸2 p 7 ，并且如果髫f p = 7 ，那么 ( j ，z t + l ，“+ 2 ，z t + 3 ，z 件4 ) 只能为( 2 ，1 ，1 ，1 ，2 ) 此外，因为l u ( l ) 0 ，所以至少有一个标号要标 两个点根据圆标号的可循环性，在以下的证明中不妨设l o = 2 令b = 【学j ，先将序列l o ，z 1 ，z ，1 分成以下子序列岛= ( 1 5 q ，1 5 q + l ，f 5 叮+ 2 ，1 5 口+ 3 ， 1 5 q + 4 ) ( o q b ) 和跏1 = ( 1 5 ( b + 1 ) ，z 矿一1 ) ( 若仃一1 5 b + 4 ) 若将s q ( o g 6 + 1 ) 的分量 和记作岛，很显然4 岛7 ( o 口6 ) ，如果s 4 1 非空，那么& + 1 中至多含有四个元，从而 风+ 1 6 记如= ( 饕。风) 一6 ( q + 1 ) ( osq56 ) 当n 是偶数时，岛i t = 3 n = 6 詈由定理2 1 3 和引理1 1 1 可知：a r 2 ，1 ( b ) n ， 下面证明不等式的相反方向分情况讨论： ( 1 ) 若如0 且口一1 = 5 b + 4 ，那么6 詈= a ：- 0 1 如6 ( b + 1 ) ，即b + 1 量，从而有 口一1 = 5 b + 4 = 5 ( b + 1 ) 一1 警一1 ，亦即盯虿5 n ) 东南大学硕士学位论文 6 0 2 o 2 图2 0 ( 2 ) 若如0 但仃一1 5 b + 4 ，再分两种情况讨论： a ) 如果届l = 6 ，则+ l 必须为( 2 ，1 ，1 ，2 ) ，根据( p 3 ) 有l o = 0 ，这与我们的假设矛盾 b ) 如果肌l 5 2 ( 3 ) 如果矗 0 ，那么必存在q ( osqsb ) 使得如= 1 设q o 是【o ，6 】中满足= 1 且 岛1 ( v q o q b ) 的最小整数这说明一1 = 0 ，艮= 7 ，岛6 ( v q o + 1 q 6 ) ，亦即 = ( 2 ，1 ，1 ，1 ，2 ) ，岛= ( o ，2 ，1 ，1 ，2 ) ( v q o + 1 q 6 ) ，因此而只能为1 因为岛“必须是6 的倍数，所以雕 1 必须为5 根据图2 可知：i + i i 4 又因为& + l 中至多含有4 个分量，所 以跏l = 4 由于f 5 4 = 2 ，1 5 b + 3 = 1 ，根据( p 3 ) 有1 5 ( b + 1 ) = 0 从而鼽1 只可能是( 0 ，2 ，0 ，2 ) 或者( 0 ，2 ，1 ，1 ) 无论哪种情形，风 1 都是4 而不是5 ，矛盾故n 是偶数且如 0 这种情形不 可能出现 1 2 3 4 1 2 ， 4 k k k k 0 “ k k k 东南大学硕士学位论文 当佗是奇数时，寄“= 3 n = 6 孚+ 3 根据定理2 1 3 和引理1 1 1 可知：a 2 ，l ( p 3 ) 鲁n + ，下面证明不等式的相反方向同样分情形讨论： ( 1 ) 如果而0 且盯一1 = 5 b + 4 ，那么3 n = 6 孚+ 3 = 留“6 ( b + 1 ) ，即 b + l 警+ = 号( 非整数) ，亦即b + l 里笋从而有盯一1 = 5 b + 4 = 5 ( 6 + 1 ) 一1 2 ( 佗+ 1 ) 一1 ， 即盯2 协+ 1 ) ( 2 ) 如果如0 但盯一1 5 b + 4 ，也同样分两种情况讨论： a ) 如果风 1 = 6 ，则+ l 必须为( 2 ，1 ，1 ，2 ) ，根据( p 3 ) 有l o = 0 ，这与我们的假设矛盾 b ) 如果4 阻l 5 ，则l 跏l i 3 从而有6 孚+ 3 = 持a - o i “6 ( b + 1 ) + 5 ，即 6 + 1 n - _ 2 a 一 ( 非整数) ，亦即6 + 1 孚，从而有盯一1 = 5 ( 6 + 1 ) + l s “l l - 1 业笋+ 3 1 ， 即盯；n + 趸1 c ) 如果阻l = 3 ，6 学+ 3 = 寄“= 6 ( 6 + 1 ) + 3 ，即6 + 1 = 孚，根据图2 知s b + 1 只 能为( o ，2 ，1 ) ，( 1 ，1 ，1 ) ，( 1 ，2 ，o ) ，( 1 ，2 ) 或者( 2 ，1 ) 考虑到我们的假设l o = 2 ，踮1 只能为( 1 ，1 ，1 ) 或者( 1 ，2 ，o ) ，从而盯一1 = 5 ( 8 + 1 ) + i s b + 1 i - 1 = 生产+ 3 1 = n 一 ，亦即盯= l n + 趸i d ) 如果0 阻l 2 ，则i 踮l l 1 从而有6 孚+ 3 = - a - 0 1 “6 ( b + 1 ) + 2 ，即 6 + 1 孚+ ( 非整数) ，亦即6 + 1 旦笋，从而有口一1 = 5 ( 6 + 1 ) + i & 啼1 i 一1 里号唑+ 1 1 ， 即口i 几十； ( 3 ) 如果如 0 根据n 是偶数时西 0 情形下的分析知如= 1 要使寄“= 3 n 是奇 数且是3 的倍数，风 1 只能是2 又因为f 5 5 = 0 ，所以岛+ 1 只能是( o ，2 ，0 ) 或者( 0 ，2 ) 考虑 到f o = 2 ，鼽1 只能是( 0 ，2 ，o ) 此时6 孚+ 3 = 寄“= 6 ( 6 + 1 ) + 1 + 2 = 6 ( 6 + 1 ) + 3 ，即 b + 1 = 孚，从而盯一1 = 5 ( 6 + 1 ) + i _ + l l 一1 = 5 孚+ 3 1 = 2 n 一 ，即o r = l n + 互1 ( i i i ) 当m = 4 时，因为p 3 是p 4 的子图，所以 观“只珞，晚，- c 忍，= ；n - 5 n ；：茎罢篓 又根据定理2 1 3 和引理1 1 1 可知： 眈“段， ；礼堂：茎薯萋： 所以m = 4 的情形得证 ( i v ) 当m 5 时，根据定理2 1 3 和引理1 1 1 可知： 7 东南大学硕士学位论文 c r 2 ，t c 只n k k ， ；。n 一。，j ： 又根据f 7 j 中的标号有 c r 2 ，- c 只n r _ ， ；。凡一。，耋： 故m 5 的情形得证 n 是偶数； 他是奇数 n 是偶数； n 是奇数 一 8 第三章p m 口g 的l ( 2 ，1 ) 一圆标号 3 1 前言 设p m 是由m 个点构成的路，g 是由n 个点构成的圈为了方便，在本章中，我们将 p m 的顶点记作x l ，x 2 ，z 。，g 的顶点记作y o ，y l i 一，y n 一1 对于翰y ( ) ，彩y ( g ) ， 将尸m 口g 中的点( x i ，可f ) 简记为( t ，j ) 这样p m 口g 的所有点构成一个m n 矩阵，矩阵 的某一行用巩= ( i ，o ) ，( i ，1 ) ，( f ，佗一1 ) 】表示( i 1 ，2 ，m 】) ；矩阵的某一列用巧= ( 1 ，歹) ，( 2 ，歹) ，( m ，歹) ) 表示0 o ，1 ，n 一1 ) ) 根据定义，不难看出，由阢生成的诱导子 图同构于g ，由巧生成的诱导子图同构于f m 点( 毛j ) 的标号记作，( ( i ，歹) ) ，则p m d g 的 标号也可以用一个m 他矩阵表示图3 表示只与锯的笛卡尔乘积图 i 、。一一，j j j r 。 rr 。 ，r 、 i r1，r 1 - ，一、 图3 只与g 的笛卡尔乘积图 关于路和圈的笛卡尔乘积图的l ( 2 ，1 ) - 标号数，d a v i dk u o 和j i n g - h oy a h 已经给出了完 整的结果 定理3 1 1 【8 】设m ，n 为整数，m 2 ，仇3 ，则 a 2 x ( p m 口g ) = 理 若m = 2 ，n 三0m o d3 i 若m = 2 ，礼0m o d3 im = 3 ，n = 3 或他6 im 4 ，他兰0m o d7 ；( 3 1 ) 若m = 3 ，佗= 4 或5 ；m 4 ，n 0m o d7 为了方便证明过程的描述和标号的给出，我们引入下面的定义和代数中的一个基本引 9 ) 东南大学硕士学位论文 设m 是一个矩阵，q ，p 是非负整数，a m 3 表示a p 分块矩阵，分块矩阵的每一个元素 是矩阵m 引理3 1 2 设矩阵x 和y 分别表示只口g 和只口c t 的k - l ( 2 ，1 ) 圃标号，其中s ，r ，t 3 如果分块矩阵( x l y ) 是只口q 件) 的k - l ( 2 ，1 ) 一圆标号，则对于任意的非负整数q ，p ，分块矩 阵( 1 x a l l y f l ) 是只口q 。+ 肛) 的k - l ( 2 ，1 ) 一圆标号 设r ，t 是整数，r 和t 的所有非负线性组合记为s ( 7 ，t ) = o l r + 肛：q ，p 为非负整数) 引理3 1 3 设7 ，t 为大于且互素的整数，那么对于所有的z ( r 1 ) 一1 ) ，有z s ( r ，t ) 且( r 1 ) ( 一1 ) 一1 管s ( r ，t ) 这是代数数论中的一个基本的定理，证明过程略去 定理3 2 1 3 2p m 口g 的l ( 2 ，1 ) - 圆标号数 肥叫黯麓 慨2 ， a = ( ：兰：) ， 不难验证( 1 a a ) 是p 2 n c s a 的一个的6 - l ( 2 ，1 ) 一圆标号故0 2 1 ( p 2 n c 孙) = 6 b = e4 6 垮 1 0 东南大学硕士学位论文 的一个7 - l ( 2 ，1 ) 圆标号 1 0 不妨设7 1 , = 3 7 + 1 ，y 为大于等于3 的整数时，令 c = 垮 不难验证( 1 a ( 7 2 ) 1 c ) 是p 2 c 3 什1 的一个7 - l ( 2 ，1 ) 一圆标号 ( 4 ) n 三2m o d3 且n 1 7 不妨设n = 3 ，7 + 2 ，叼为大于等于5 的整数令 = ( 2 4 1 6 。4 204 d 531625312 64 20 5 1 6 34 ) = ii 401 0 ， 不难验证( 1 a ( u 一5 ) i d ) 是p 2 c 3 , + 2 的一个7 - l ( 2 ，1 ) 圆标号 注：当亿 1 0 且既是7 的倍数也可以表示成3 ，y + 1 时，用( 2 ) 或者( 3 ) 中的标号均可；当 礼 1 7 且既是7 的倍数也可以表示成3 叩+ 2 时，用( 2 ) 或者( 4 ) 中的标号均可综合( 2 ) ( 3 ) ( 4 ) 可得：当n 0m o d3 且n 4 ，5 ，8 ，1 1 时，0 2 。i ( p 2 d ) = 7 ( 5 ) 最后我们考虑剩下的n = 4 ，5 ，8 ，1 1 的情形用反证法证叽假设0 2 , 1 ( p 2 n c l l ) = 7 设p 2 n c n 中的某一列的两个点为( 1 ，歹) ，( 2 ，j ) u t o ，1 ，2 ，1 0 ) ，根据圆标号的可平移性， 设 州1 ，j ) ) ，州2 ，j ) ) 】属于等价类炳= o ，2 ) ， 1 ，3 ) ， 2 ，4 ， 3 ，5 ， 4 ，6 ) ， 5 ，o ， 6 ，1 ”不失 一般性的假设，( ( 1 ，j ) ) = 0 ，( ( 2 ，歹) ) = 2 ，则州1 ，歹一1 ) ) 和b ( 1 ，歹+ 1 ) ) 可以标3 ，4 ，5 ，而 州2 ，歹一1 ) ) 和州2 ，j + 1 ) ) 可以标4 ，5 ，6 ( 这里的+ ，一均指模7 的运算) 这说明，( ( 1 ，j i 一1 ) ) 和，( ( 1 ，j + 1 ) ) 都不能标5 ，( ( 2 ，j 一1 ) ) 和州2 ，j + 1 ) ) 都不能标4 设g ：表示由 ，、 ( 1 ，j 一1 ) ( 1 ，j ) ( 1 ，j + 1 ) ( 2 ，歹一1 ) ( 2 ，j ) ( 2 ，j + 1 ) 生成的诱导子图，则此时g ：的标号只能是 04 、，4 i ，l 2 6 6 ，304 、 l 5 2 6 广 1 1 ，坞v 为号标的 ， g 没 妨不性称对据根 东南大学硕士学位论文 通过类似的分析有，( ( 1 ，歹+ 2 ) ) = 1 ，( ( 2 ，j + 2 ) ) = 3 ，f ( o ，j 一2 ) ) = 6 ，( ( 2 ，歹一2 ) ) = 1 ，这样 继续下去，我们得到 6 4 ：2 04 6 4 6 3 1 5 2 6 观察此矩阵，我们有如下结论： ( i ) 每一列的标号都属于等价类m 1 ； ( i i ) 每连续7 列标号发生一次循环； ( i i i ) 当竹不是7 的倍数时，矩阵不可能是t 2 t 2 c , 。的一个7 - l ( 2 ，1 ) 圆标号 当 ，( ( 1 ，歹) ) ，州2 ，歹) ) ) 是尬中的其它元时，可以类似地证出同样的结论若，( ( 1 ，j ) ) = 2 ，( ( 2 ，j ) ) = 0 ，根据岛的对称性和以上分析可以认为i f ( ( 1 ，歹) ) ，烈2 ，j ) ) ) 属于等价类m i = 2 ，o ) ， 3 ，1 ) ， 4 ，2 ) ，( 5 ，3 ， 6 ，4 ) ， o ，5 】， 1 ，6 ) ，经过类似的证明我们也可以得到同样的结论 因为d g ( ( 1 ，歹) ，( 2 ，歹) ) = 1 ，所以i 州1 ，歹) ) 一州2 ，j ) ) l v 2 ，从而 ，( ( 1 ，j ) ) ，州2 ，j ) ) ) 除了属 于等价类尬，州之外，只能属于等价类m 2 = o ，3 ， 1 ，4 ) ， 2 ，5 ) ， 3 ，6 ， 4 ，o ， 5 ，1 】， 6 ，2 ) 】i 或者等价类鹏= 3 ，o ，_ 【4 ，1 ， 5 ，2 ) ， 6 ，3 ) ， o ，4 ) ， l ，5 ) ， 2 ，6 ” 如果 ，( ( 1 ，j ) ) ，州2 ，歹) ) 毛，根据圆标号的可循环性，不失一般性地假设，( 1 ，j ) ) = 0 ，( ( 2 ，j ) ) = 3 ，则，( ( 1 ，j 一1 ) ) 和，( ( 1 ，j + 1 ) ) 可以标2 ，4 ，5 ，而，( ( 2 ，歹一1 ) ) 和，( ( 2 ，j + 1 ) ) 可 以标1 ，5 ，6 ，考虑了圈的对称性，g ：的标号只能是以下6 种情况之： ( ：9 ，( ：0 ，( ：兰：) ，( ：；) ，( ；：三) ，( ； 但最后两种情况不会出现，因为一旦出现 ， 则，( ( 1 ，j + 2 ) ) 和，( ( 2 ，歹+ 2 ) ) 只能标l 或2 ，由于距离2 的限制，导致矛盾所以当，( ( 1 ，j ) ) = 0 ，( ( 2 ，歹) ) = 3 时，q 的标号只可能是前四种情况之一我们依次记作丑，噩，t 3 ，t 4 类似的， 若，( ( 1 ，j ) ) = 1 ，( ( 2 ，歹) ) = 4 时，q 的标号只可能是以下四种情况之一： 噩= ( ：三i ) ，= ( ：三：) ，乃= ( ：4 1i ) ，珏- ( ：4 1 ：) 1 2 东南大学硕士学位论文 看州1 ，歹) ) = 2 ，( ( 2 ，歹) ) 25 时，q 的标号只口j 就是以卜四种情况之一： 马= ( ：, t l o = ( ：) ，n ，( ；：) ，乃。( ：) 若州1 ，歹) ) = 3 ，( ( 2 ，歹) ) = 6 时，q 的标号只可能是以下四种情况之一： 五s = ( ；：兰) ，丑t = ( ；三：) ，噩s = ( i ：，矸6 = ( i ：) 若州1 ，j ) ) = 4 ，( ( 2 ，歹) ) = 0 时，q 的标号只可能是以下四种情况之一： n ，= ( ：4 。i ) , t l s = ( ：。4 , t 1 9 = ( ：。4 ：) ，= ( ：。4 ：) 若州1 ，歹) ) = 5 ，f ( o ，歹) ) = 1 时，q 的标号只可能是以下四种情况之一： 死t = ( 兰：) ，z k = ( ：) ，丁h = ( 0 ；：) ，丁h = ( 0 ；：) 若，( ( 1 ，歹) ) = 6 ，( ( 2 ，j ) ) = 2 时，骘的标号只可能是以下四种情况之一； 丁k = ( ：) ，死e = ( ：三) , t 2 7 - ( ：) ，z k = ( ：) 观察正“= 1 ，2 ，2 8 ) 有如下结论： ( i ) 矩阵中每一列的标号均属于等价类m 2 或者啊； ( i i ) 如果把丑中的每个元素在长度为7 的圆上依次平移一个单位，将陆续得到如，t 9 ， t 1 3 ，t i t ，t 2 1 ，疋5 ；如果把t 2 中的每个元素在长度为7 的圆上依次平移一个单位，将陆续得到 珏，丑o ，丑4 ，丑8 ，乃2 ，乃6 ；对于乃，z i 也有类似的结论； 注：由于圈的对称性，我们把第二列相同，第一列和第三列互换的矩阵看作同一个矩阵 例如 e 垮) 1 3 东南大学硕士学位论文 如果 ，( ( 1 ，j ) ) ，州2 ，j ) ) ) ，通过类似的分析也能得到2 8 个矩阵，分别记作巧“= 1 ，2 ，2 8 ) 其中巧是由五的第一行和第二行互换得到 根据( i i ) ，我们不妨假设p 2 0 c l l 的子图g ；的标号必为乃，死，马，乃之一事实上， 因为p 2 0 c n 总是包含p 2 0 p s 这样的子图，我们可以把互( i = 1 ，2 ，3 ，4 ) 看作p ：o p 3 的一个 7 - l ( 2 ，1 ) 一圆标号然后按照一个方向扩展标号，观察能否找到p 2 0 c i l 一个7 - l ( 2 ，1 ) 圆标号 如果在列举的全部情况下找不到这样的标号，就证明了o 2 , 1 ( 最口c 1 1 ) = 8 为了方便证明的给出，下面我们结合图形来表达在下面的树图中第0 层表示恐口p 3 的 标号，第1 层表示在p 2 0 p a 的标号已经确定的情况下p 2 0 p 4 的所有可能标号，第2 层表示在 p 2 0 p 4 的标号已经确定的情况下p 2 0 p 5 所有可能的标号，依次类推，第8 层表示在 2 口p l o 已经确定的情况下p 2 0 c 1 l 所有可能的标号为了减少树图的分支，当出现以下情况之一时， 可以将分支进行合并： a ) 当两种可能的标号位于同一层并对下一列的标号影响相同时； b ) 当两种可能的标号位于的层数都可以表示成3 k 且对下一列的标号影响相同时； c ) 当两种可能的标号位于的层数都可以表示成3 m + 1 且对下一列的标号影响相同时； d ) 当两种可能的标号位于的层数都可以表示成3 l4 - 2 且对下一列的标号影响相同时 如果p 2 0 p a 的标号为 ) 结果如图4 所示，不存在p 2 口c 1 1 的7 - l ( 2 ，1 ) 圆标号 如果忍o p s 的标号为 ) ， 结果如图5 所示，不存在p 2 0 c 1 1 的7 - l ( 2 ，1 ) 一圆标号。 如果p 2 0 p a 的标号为 ) 其扩展标号与图4 的区别在于每一层标号中，( ( 2 ，1 ) ) = 6 ，不难验证也不存在p 2 0 c 1 1 的 7 - l ( 2 ，1 ) 圆标号 1 4 东南大学硕士学位论文 如果p 2 0 p 3 的标号为 ) 其扩展标号与图5 的区别在于每一层标号中，( ( 2 ，1 ) ) = 6 ，不难验证也不存在p 2 d c l l 的 7 - l ( 2 ，1 ) 一圆标号 因此，眈，l ( p 2 d 0 1 1 ) = 8 对于n = 4 ，5 ，8 的情形，其结果已经包含在图4 和图5 中，故 c r 2 ，1 ( 尼口q ) = 0 2 ，l ( 忍口g ) = 0 2 ，l ( p 2 0 c s ) = 8 _ 定理3 2 2 ( p 3 0 c ) ： 7 一兰0 删7 ； ( 3 3 ) i8 ，n 0m o d 7 证明： 我们对n 分三种情况讨论 ( 1 ) 佗= 4 或5 首先由定理3 1 1 知：a 2 ，l ( p 3 0 c 4 ) = a 2 ，l ( p 3 0 c 5 ) = 7 ，再根据引理1 1 1 有 c r 2 ，l ( p 3 0 q ) 8 ，0 2 ，1 ( p 3 0 瓯) 8 令 a = gi il ) ，b = ( ii i i c 憾， 1 5 东南大学硕士学位论文 ( ； ；： 弋 五i ( ； 返回镐i 6 34 ) 正( ；：习五( ；：翁五( ；5 。：) i ( ；：；主冀夏( ：4 0 吼： e 砜g 返回第 返回第2 层 ：瓶( ：习五 l 4 l 4 飘g r 1 6 5 3i 、 2 0 5 j j l “7 ：五：( ：；： 7 ；7 ： ：； 五五：瓦，( ：i ) 五夏：瓦， ：! ) 瓦瓦( ：0 正疋瓦( ： z 疋瓦( ：) 五t 瓦( ：；) 五j 。( ：；) 正瓦：( ：6 2 圈4 扣3 舛标锄g ；加4 所舸黜杯蟹 弱 2 6 订 心 3 o 5 2 3 6 ，_ 瓦 层 7 j 3 第小，吖返 东南大学硕士学位论文 疋瓦 ，s 瓦瓦互。i ： l l g 0531 个f ，3 164 2 1 如1 6 4 2 0 5 j 瓦瓦 三 5 i 5 l ( ； 。 疋( ： 、 ； ； ； ：) 归j 到湖4 ，f 树豹第l 璎 ；3 64 。1 5 3l j 归并到圈4 中树的第2 瑶 瓦( ：二2 6 习 归并列阁4 中树的第4 联 l6 4 2 瓦( ：2 5 霎 归并到图。中树的第6 层 瓦瓦雕：a 、 7 j 并到圈4 ，树的第7 联 t 瓦n ( ； 嘲s 当n = 3 时标吁为g ；) 时，4 5 栉s t - 时所柯可能的标蟹 1 7 层第 的 树 乱纠阶 。4 粕 3 6 步 ，。，。k 疋。 瞄 5 第的树 4 簸到并0 归 4 o 东南大学硕士学位论文 ( 3 ) l r , 不是7 的倍数且n 4 ，5 根据定理3 1 1 和引理1 1 1 有7 a 2 ，1 ( b 口“) 8 下面用反证法证明，假设对某个礼，存在一个7 - l ( 2 ，1 ) 圆标号设p 3 0 g m 0m o d7 且 礼4 ，5 ) 中某一列的点为( 1 ，j ) ，( 2 ，歹) ，( 3 ，歹) 因为p 2 0 c , ，是恳口g 的子图，由定理3 2 1 的证明过程可知，若某一列两点的标号 ，( ( 1 ，) ) ，州2 ，j ) ) 属于等价类m i ( 或者州) ，那么 对所有的j ( j = 0 ，1 ，n 1 ) ， ，( ( 1 ，歹) ) ，州2 ，歹) ) 属于等价类m i ( 或者叫) ；若某一列两 点的标号 州1 ，歹) ) ，( ( 2 ，j ) ) ) 属于等价类u 2 ( 或者鸩) ，那么对所有的j ( j = 0 ，1 ，n 一 1 ) ， ，( ( 1 ，歹) ) ，( ( 2 ，歹) ) ) 属于等价类m j 和叫；对 ，( ( 2 ，j ) ) ，( ( 3 ，歹) ) ) 也有类似的结论且 i f ( ( 1 ，歹) ) ，( ( 2 ，j ) ) ) ， ，( ( 2 ，j ) ) ，( ( 3 ，j ) ) 不可能一个属于坛，另一个属于联( t = 1 ，2 ) 下面我 们分成八种情况讨论 情况1 如果 ，( ( 1 ，j ) ) ，州2 ，j ) ) 】和i f ( ( 2 ，j ) ) ，( ( 3 ，歹) ) ) 均属于等价类尬，我们可以不失 一般性的假设，( ( 1 ，歹) ) = 0 ，州2 ，歹) ) = 2 ，则州3 ，歹) ) 只能标4 ，依次扩展下去，我们得到唯一 的标号 4l 6 3 15 52 0 4 2 6 63 15 30 o4 2 6 4l 1 5 3 o 52 04 26 4l 1 5 30 52 26 41 63 我们发现，每连续的7 列标号发生一次循环当礼0r o o d7 时，矩阵不可能是一个7 - l ( 2 ，1 ) 圆标号 情况2 如果 ，( ( 1 ，j ) ) ，( ( 2 ，j ) ) 和 ，( (