（运筹学与控制论专业论文）路和圈的定位控制集问题.pdf

- m a s t e rd i s s e r t a t i o no f2 010s c h o o lc o d e ：1 0 2 6 9 a c a d e m i cn u m b e r ：510 7 0 6 010 8 3 e a s tc h i n an o r m a lu n i v e r s i t y l o c a t i n g - d o m i n a t i n gs e t so np a t h sa n d c y c l e s 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 di 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 ： m i n y a nq i n 2 0 1 0 5 ) _ 学攻 华东师范大学学位论文原创性声明 人所呈交的学位论文逸和圆崩龇细) 缸谴，是在华东师范大 ( 请勾选) 学位期r - j ，在导师的指导下进行的研究工作及取得的研 究成果除文中已经注明引用的内容外，本论文不包含其他个人已经发表或撰写过的 研究成果对本文的研究做出重要贡献的个人和集体，均已在文中作了明确说明并表 示谢意 作者签名：掷 日期：小年牛孕泸日 完成 同意 华东师范大学学位论文著作权使用声明 国家图书馆、中信所和“知网 送交学位论文的印刷版和电子版；允许学位论文进入 华东师范大学图书馆及数据库被查阅、借阅同意学校将学位论文加入全国博士、硕 士学位论文共建单位数据库进行检索，将学位论文的标题摘要汇编出版，采用影印、 缩印或其他方式合理复制学位论文 本学位论文属于( 请勾选) ( ) 1 经过华东师范大学相关部门审查核定的“内部 或“涉密 学位论文 于e t 解密，解密后适用上述授权 密，适用上述授权 导师签名：扬名杪- 本人签名：么蚺 纠口年中月如日 “涉密”学位论文应是已经华东师范大学学位评定委员会办公室或保密委员会审定过的学位论文 ( 需附获批的 掣1 又因为d = 1 4 ，5 ，6 ，9 ，1 0 ，l l l 是p 1 4 的一个3 l d s ，所以衅( p 1 4 ) = r 掣1 + 1 = 6 口 7 华东师范大学路和圈的定位控制集问题 定理2 6 2 n 7 , 1 - ， 蟮d ( g ) = n 一1 n = 6 k ( k 2 ) 时，j l 驴( g ) = ；1 = 2 k 刀= 6 k + l 2 ) 时， 万尹( g ) = r ；1 = 2 k + 1 n = 6 k + 2 ( k 2 ) 时，l 重 d ( g ) = f ；1 = 2 k + l 疗= 6 k + 4 ( k 1 ) 时，1 1 4 尹( g ) = r 1 = 2 k + 2 n = 6 k + 5 ( k 1 ) 时，i l 鹭d ( g ) = ；1 = 2 k + 2 特别地，n = 8 ( n = 6 k + 2 ，k = 1 ) 时， 鹭d ( g ) = 2 1 + 1 = 4 证明设j r i ，j r 2 而，柏是长为，l 的圈，为简单起见，用f 代表而 当2 n57 时，圈上任何两点的3 m 都相同，故肘p = n 一1 当n = 6 k ( k 2 ) 时，取d = l + 6 p ，p 0 u 5 + 6 q ，g o 当n = 6 k + l ( k 2 ) 时，取d = 1 1 ，6 ，7 u1 3 + 6 p ，p 1 u 5 + 6 q ，q l 当n = 6 k + 2 ( k 2 ) 时，取d = 1 1 ，7 u 6 p ，p l u 4 + 6 q ，q 1 1 当n = 6 k + 4 ( k 1 ) 日寸，取d = 1 ，7 ，9 u 6 p ，p l u 2 + 6 q ，g 2 当，l = 6 k + 5 ( k 1 ) 时，取d = 6 u l + 6 p ，p 0 lu 3 + 6 q ，q l 当n = 8 时，3 ( 1 ) = 2 ，3 ，4 ，6 ，7 ，8 ，3 ( 5 ) = 2 ，3 ，4 ，6 ，7 ，8 d 故1 和5 至少一个d 同理， 2 和6 ，3 和7 ，4 和8 各至少一个d 因此idi 4 ，又d = 1 ，2 ，3 ，4 是一个3 l d s 故哗( c 8 ) = 1 + 1 = 4 口 注4 n = 9 ( 6 k + 3 ，k = 1 ) 时，下界是不能达到的若取得下界ldl - 3 ，则剩下6 个 点，其中至少有两个点，其邻域仅包含d 中的一个点由对称性，不妨设n 3 ( 1 ) = 1 2 ，3 ，4 ，7 ，8 ，9 l 仅有一个点在d 中，剩下1 5 ，6 ) d 若2 d ，d = 1 2 ，5 ，6 1 ，显然它不是3 l d s ，矛盾若3 d ，d = 3 ，5 ，6 l ，它也不是3 l d s 若4 d ，d = 1 4 ，5 ，6 ，它也不是3 l d s 7 , 8 ，9 的情形类似所以衅( c 9 ) 4 取d = 1 1 ，6 ，7 ，9 即可所以哗( g ) = 4 对于一般的n = 6 k + 3 ，我们有如下结论： 定理2 7 对于n = 6 k + 3 时，衅( g ) = ；1 + 1 证明由定理2 2 知，哗2 k + 1 我们假设d 是一个3 一l d s ，并且ldi _ r ；1 = 2 k + 1 剩 下微+ 2 对d 连续点，那么每个d 中的点刚好区分两对d 一连续点，并且这些d 连 续点都是不同的同时，每对d 连续点恰好被d 中某个点区分我们得到下面两个结 论： 8 华东师范大学路和圈的定位控制集问题 结论1 d 包含至多2 个连续的点 结论1 证明因为每个d 中的点区分两对d 连续点，故d 至多包含6 个连续的 点假如d 包含6 个连续的点在g 中，不失一般性，设 x l , x 2 ，物，x 4 ，玛，粕 d ，那么， x i 和粕同时区分了 翰，却 ，矛盾假如d 包含5 个连续的点在g 中，不失一般性， 设 工l ，耽，x 3 ，x 4 ，嬲 d ，那么，石i 和如同时区分了 而，粕l ，矛盾假如d 包含4 个连续 的点在g 中，不失一般性，设 x l , 娩，物，x 4 d ，那么，工l 和x 4 同时区分了 而，玛 ，矛盾 假如d 包含3 个连续的点在g 中，不失一般性，设 柏，娩，的lt ed ，x n 圣d ，x 4 星d ，因为 要区分 ，缸 ，札l ，而_ 2 而_ 3 ，玛，粕，却中至少一个在d 中又因为 而，拗 只需要一个 点来区分，故砀一1 ，x n 一2 ，而一3 ，如，x 6 ，x 7 至多一个在d 中因此，而一l 而一2 ，而- 3 ，奶，粕，却中 恰好一个在d 中由对称性，假设j r 5 或或x 7 d ，x n - l x n - 2 ，x n 一3 d 这样， 而- 4 隹d ，否则而- 4 和j r 3 同时区分了 而，x n l ；x n - - 5 彗d ，否则而_ 5 和耽同时区 分了 而- l ，而一2 ；而一6 萑d ，否则而_ 6 和肋同时区分了 而2 而一3 这样，我们得 到而，而一l ，而一2 ，而一3 而- 4 ，粕- 5 ，而“都不在d 中，岛( 而一3 ) = 1 2 i 矛盾 下面我们假设d = i x i i ，+ l l ，i l i 2 讯i 结论2 i j i j + ll _ 2 或者6 ，j i l ，2 ，2 七 结论2 证明因为对任意的x v d ，有d 3 ( x ) o ，故lf f f + li 7 如果，lf 广f + 1i - 7 ，对某个j f 1 ，2 ，2 七 ，则置，和而件同时区分了 而，+ 3 x i l + 4 矛盾 首先假设li j f 件l | _ l ，对某个j 1 ，2 ，放 不失一般性，我们假设x l ，耽d 由 结论1 我们知道勋薯d ，而萑d 假设瓤d 则由每个d 中的点区分两对不同 的d 一连续点，可知而一l ，而一2 ，而一3 ，而_ 5 ，而- 6 岳d ，而- 4 d 若玛d ，则 物，托 同 时被x l 和娩区分，矛盾故有奶岳d 则有托，勋，抛，x 9 ，却l 叠d ，x l o ，x 1 2 d 如 果柏3 萑d ，工1 4 d ，继续这样一隔一地取，无法出现连续的4 个点d 因此一定有两个 连续的点d 不失一般性，设柏2 ，x 1 3 d ，则x 1 4 , 却5 ，期6 ，x 1 7 ，朋9 ，砌隹d ，j c l 8 d ，娩l 或 者x 2 2 d 若恐i d ，则砌，翰，x 2 5 譬d ，x 2 3 d ，x 2 6 或着勋7 d ：如果x 2 6 d ，继续 下去，无法出现连续的4 个点仨d ；如果x 2 7 d ，则，娩8 岳d ，x 2 9 d 继续下去，也无 法出现连续4 个点隹d 若x 2 2 d ，同理，也不能出现连续4 个点莹d 所以，舰芒d 对 称地，有x n 一1 垡d 如果x 5 ，而一2 都d ，则它们同时区分了 x 3 ， 故不妨设奶岳d 所以有却 d ，x 8 d 若t ed ，则而一2 ，而- 3 ，南一5 ，翰一6 ，x 9 ，x i o ，x l l ，x 1 3 ，x 1 4 萑d ，x n - 4 ，柏2 d ，x 1 5 或 者x 1 6 d 如上的讨论，无论怎样，都不会出现连续4 个点簪d 若x 6 隹d ，则初 d ，确，x 9 隹d ，x l o 或者x l i d 若x l o d ，则x l l 譬d ，工1 2 d 同理，继续下去无法出现 连续4 个点仨d 若x l l d 则x l o 譬d ，为了区分i x 9 ，工l o ，必须工1 2 ，x 1 3 d 这样出现了 9 华东师范大学路和圈的定位控制集问题 连续的3 个点d 矛盾 假设ii j i j + ii - 3 ，对某个j 1 ，2 ，放 不失一般性，我们假设x i , 瓤d ，x 2 ，x 3 星 d 由上可知，而，玛垡d 而一l 或者粕d 由对称性，设托d ，则如一lgd 因 此x 7 ，魂，而一l ，翰一2 ，而一3 叠d ，x n - 4 d ，勋或者x 1 0 d 若x 9 d ，则x l o ，工l l ，柏2 ，x 1 3 圣 d ，工1 4 ，工1 5 d 矛盾因此，x 9gd ，工i o d ，x i i ，x 1 3 ，x 1 4 岳d ，x 1 2 d ，x 1 5 或者x 1 6 d 如 此下去，或出现两个连续的点d ，或不会出现连续4 个点譬d 假设lf ，一i j + li - 4 ，对某个j i l ，2 ，2 七 不失一般性，我们假设x i ，秘 d ，娩，物，x 4 隹d 由上可知，而，粕d ，x n l ，却d ，粕一2 ，而一3 ，粕，两莹d ，而- 4 或者而- 5 d 因为不会出现距离为3 的，故而- 5 d ，而- 4 岳d ，继续下去，可得d 中的点是距 离2 和4 间隔的，但是这样无法构成3 l d s 假设ii j i i + l | = 5 ，对某个j i l ，2 ，2 七 不失一般性，我们假设x i ，粕 d ，娩，x 3 ，期，奶仨d 则由上可知，而，却芒d ，那么 x 3 ，拗 无法区分，矛盾 这样只剩下距离为2 和6 的点，如果只有距离为2 的点，显然不能构成3 - l d s 故d 中一定有距离为6 的点不妨设工l ，却d ，x 2 ，翩，托，j r 5 ，x 6 萑d ，则粕，而岳 d ，x 9 ，而一l d ，工i l ，x 1 3 ，而一3 ，而一5 d ，x 1 4 ，x 1 5 垡d x 1 6gd ( 不存在距离为3 的点) ，x 1 7g d ( 不存在距离为4 的点) ，工1 8 萑d ( 不存在距离为5 的点) ，工1 9 d 同理，x 2 0 ，娩2 隹 d ，耽l ，娩3 d ，如此下去，因为n = 6 k + 3 是奇数，所以一定会出现两个d 中的点之间 距离是奇数的情形，即1 ，3 ，5 矛盾 综上，我们得到肘 d ( g ) 2 k + 2 ，d = x ilf 6 p + 1 和6 p + 3 ，p 0 lu 而l 是一 个3 一l d s 因此 f p ( g ) = 2 k + 2 = ；1 + 1 口 由定理2 6 和定理2 7 得到： 1 0 华东师范大学 路和圈的定位控制集问题 定理2 8 2 以7 时， n = 6 k ( 七2 ) 时， n = 6 k + l ( k 2 ) 时， n = 6 k + 2 ( k 2 ) 时， n = 6 k + 3 ( k 1 ) 时， n = 6 k + 4 ( k 1 ) 时， n = 6 k + 5 ( k 1 ) 时， 特别地，n = 8 ( n = 6 k + 2 ，k = 1 ) 时， m p ( g ) = n 一1 鲈( g ) = r ；1 = 2 k m ；d ( c n ) = 嘲= 2 k + 1 孵d ( g ) = ；1 = 2 k + 1 哗( g ) = r ；1 + 1 = 2 k + 2 f 尸( g ) = 等1 = 2 k + 2 m 3 l d ( c , , ) = q l = 2 k + 2 m 尹( g ) = 等1 + 1 = 4 第三章关于厂l d s 的界 关于路和圈的 肇d ( g ) ，【2 】已经给出了它的下界在本章中我们讨论它的上界 定理3 1 ( 【2 】) 令k 是一个非负整数，r 2 ( i ) 如果，是偶数，并且n = 3 k r + 2 r + l ，则 衅d ( r ) s 丁n + l + 下r + l ； ( i i ) 如果r 是奇数，并且n = 故3 r + 3 ) + 2 r + 1 ，则 舻( ) 5 丁n + l + 孚； ( i i i ) 对于任何疗2 r + l 矽( r ) r 学+ 7 r 3 + 5 1 证明 rr + lr+l红-l ro d d ： rr + 1 rt2墨+1 图1 ( i ) 首先考虑当r 是偶数的情形如图1 ，如果k = 1 ，就是图1 表示的情况如 果k = 0 ，我们只取左边的部分，顶点数为2 ，+ 1 如果k 2 ，我们把括号内的部分 重复k 1 次即可这样d 由b + 厂+ 1 个点组成，而总的路长为n = 3 k r + 2 r + 1 ，因 此idi - 伽+ r + 2 ) 3 ，容易验证d 是一个r l d s ( i i ) 现在我们构造d 在，- 为奇数时的情形d + 有k ( r + 1 ) + r + 1 个点，总的路长 为n = k ( 3 r + 3 ) + 2 r + 1 ，因此id + i - o + r + 2 ) 3 ，并且容易验证是一个r l d s ( i i i ) 假如r 是偶数，在上面d 的构造中在路的左边加上s 个d 中的点，并且l s 1 2 华东师范大学路和圈的定位控制集问题 3 r _ 1 这样新的风包含了打+ r + 1 + j 个点，总的路长为n = 3 k r + 2 r + 1 + j ，它介 于3 k r + 2 r + 2 和3 k r + 2 r + 1 + 3 r l = 3 r ( k + 1 ) + 2 r 之间：这样所有的长度n 2 r + l 的 路都被考虑了，并且职是一个r l d s ，大小为( + r + 2 + 2 s ) 3 ( n ，+ 7 r ) 3 假如r 是奇数，同样在j d 的构造中在路的左边加上j 个d 中的点，并且1 j 3 r + 2 这样新的d i 包含了h r - t - 1 ) + r + l + s 个点，总的路长为n ：= k ( 3 r + 3 ) + 2 r + l + s ，它 介于以3 r + 3 ) + 2 ，+ 2 和k ( 3 r + 3 ) + 2 r + l + 3 r + 2 = ( 七- i - 1 ) ( 3 r + 3 ) + 2 r 之间： 这样所有的长度n 2 r + 1 的路都被考虑了，并且d ：是一个，l d s ，大小 为( n ：+ ，+ 2 + 2 s ) 3s ( 咒：+ 7 r + 6 ) 3 r a 定理3 2 ( 【2 2 】) 如果r 兰1 ，2 ，3 ，4 ( m o d 6 ) ，r 2 ，对所有n 2 r - i - 1 ，有 畔d ( n ) s 丁n + 2 r + 3 显然，加入的j 个点不必全是d 中的点我们下面通过对加入的j 个点进行讨论， 从而修改一下它的上界 定理3 3 对任何以4 r + 2 ，舻( 一) n + 1 i + 7 r + 8 ，1 证明假如r 是偶数在上面图1 的构造中在路的左边加上s 个