（应用数学专业论文）超立方体可区别数的研究.pdf

摘要 本文主要研究了超立方体的一种结构特性超立方体三次幂的可区别数和 超立方体及其高次幂的边可区别数问题图的可区别数是破坏图对称性的最小可 区别的顶点标号数( 颜色数) ；图的边可区别数是破坏图对称性的最小可区别的边 标号数( 颜色数) 对于图的可区别数问题，b o g s t a d 和c o w e n 在d i s c r e t em a t h 2 0 0 4 年发表的 论文中研究了超立方体及其二次幂的可区别数，并提出了如下猜想：对于给定的 正整数p ，当n 充分大时，n 维超立方体p 次幂的可区别数等于2 根据这个猜想 本文作了如下研究 1 根据，l 维超立方体p 次幂的结构特性，研究了其顶点间距离与海明距离的 关系，给出了确定顶点坐标的充分必要条件，并结合“脊”的技术和顶点着色的方 法对n 维超立方体三次幂圩：的可区别数进行了研究得到h ：可区别数的一个上 界，即，当n 6 时，h ：的可区别数不超过5 2 在给出了n 维超立方体三次幂一可区别数的一个上界的基础上，对维数不 超过7 的超立方体三次幂的可区别数进行了研究通过适当地选取顶点得到了h i 的可区别数为8 ，h ：的可区别数为5 ，日；和h ；的可区别数都为2 ，及h ；可区别 数的一个上界为3 3 提出了图的边可区别数概念给出了n 阶路只和n 阶圈e 的边可区别数： 根据n 维超立方体以及其p 次幂 醋的结构特性，对h 维超立方体日。，h 维超立 方体二次幂t 2 和，l 维超立方体p ( 2 ) 次幂h ? 的边可区别数进行了研究，得到了n 维超立方体及其二次幂研的边可区别数，和 维超立方体高次幂e r p 的边可区别 数的一个上界即，当n = 2 时，见的边可区别数为3 ；当n z 3 时，以的边可区 别数为2 ；当，1 2 6 时，h ：的边可区别数为2 ；当h z 4 , n z p ，2 时，h ：的边可区 别数小于等于3 关键词：图论；超立方体；可区别数；边可区别数；图着色 o nt h ed i s t i n g u i s h i n gn u m b e ro fh y p e r c u b e s a b s t r a c t t h i sp a p e ri n v e s t i g a t e sm a i n l yt h es t r u c t u r a lp r o p e r t i e so ft h eh y p e r c u b e - 一t h e d i s t i n g u i s h i n gn u m b e ro ft h ec u b eo fh y p e r c u b ea n dt h ee d g ed i s t i n g u i s h i n gn u m b e ro f h y p e r c u b ea n di t spp o w e r s t h ed i s t i n g u i s h i n gn u m b e ro fag r a p hgi st h em i n i m u m n u m b e ro ft h ed i s t i n g u i s h i n gl a b e l i n g s ( c o l o r s 、o ft h ev e r t i c e si ngf o rw h i c hd e s t r o y s t h es y m m e t r i e so fg ：t h ee d g ed i s t i n g u i s h i n gn u m b e ro fag r a p hgi st h em i n i m u m n u m b e ro ft h ed i s t i n g u i s h i n gl a b e l i n g s ( c o l o r s ) o ft h ee d g e si ngf o rw h i c hd e s t r o y st h e s y m m e t r i e so fg f o rt h ed i s t i n g u i s h i n gn u m b e ro fag r a p hg ，b o g s t a da n dc o w e ni n v e s t i g a t e dt h e d i s t i n g u i s h i n gn u m b e ro ft h eh y p e r c u b ea n di t ss q u a r e ，a n dp r o p o s e dac o n j e c t u r ei n d i s c r e t em a t h 2 0 0 4a sf o l l o w s ：f o rf i x e dp ，w h e nhi s s u f f i c i e n t l yl a r g e ，t h e d i s t m g u i s h i n gn u m b e ro ft h epp o w e r so ft h e ，l - d i m e n s i o n a lh y p e r c u b ee q u a l st o 2 b a s e do nt h ec o n j e c t u r e ，t h i sp a p e rs t u d i e sa sf o l l o w 1b a s e do nt h es t r u c t u r a lp r o p e r t i e so ft h e pp o w e r so ft h en - d i m e n s i o n a lh y p e r c u b e ， t h i sp a p e rs t u d i e st h er e l a t i o n sb e t w e e nt h ed i s t a n c ea n dh a m m i n gd i s t a n c eb e t w e e ni t s v e r t i c e s ，p r e s e n t st h es u f f i c i e n ta n dn e c e s s a r yc o n d i t i o n sf o rd e t e r m i n i n gt h ev e r t e x c o o r d i n a t e ，a n dc o m b i n e sw i t ht h em e t h o d so ft h e “s p i n e t e c h n o l o g ya n dv e r t i c e s c o l o r i n g , a n dt h e ns t u d i e st h ed i s t i n g u i s h i n gn u m b e ro ft h e c u b eo ft h e ，l ( _ 6 ) 一 d i m e n s i o n a lh y p e r c u b e ，g e t st h eu p p e rb o u n d a r yo ft h ed i s t i n g u i s h i n gn u m b e ro fh ： i s5 f o rn 之6 2o nt h eb a s i so fg e t t i n ga nu p p e rb o u n d a r yo ft h ed i s t i n g u i s h i n gn u m b e ro ft h e c u b eo ft h e 玎( = 6 ) - d i m e n s i o n a lh y p e r c u h e 日：，t h i sp a p e rs t u d i e st h ed i s t i n g u i s h i n g n u m b e ro ft h ec u b eo ft h e 疗( s 7 ) 一d i m e n s i o n a lh y p e r c u b e ，o b t a i n st h ed i s t i n g u i s h i n g n u m b e ro fg r a p h 硪，h ：，磁a n dh ；i s5 ，8 ，2a n d2 ，r e s p e c t i v e l y ，a n dt h eu p p e r b o u n d a r yo ft h ed i s t i n g u i s h i n gn u m b e ro fg r a p hh ；i s3b ys e l e c t i n gv e r t i c e sp r o p e r l y 3b a s e do i lt h ed i s t i n g u i s h i n gn u m b e ro fg r a p h ，t h i sp a p e rp r o p o s e st h ee d g e d i s t i n g u i s h i n gn u m b e ro fg r a p h ，a n do f f e r st h ee d g ed i s t i n g u i s h i n gn u m b e ro ft h e l l 一v e r t e xc y c l ec 。a n dt h en v e r t e xp a t hp n a c c o r d i n gt ot h es t r u c t u r a lp r o p e r t i e so f t h en 一6 i m e n s i o n a ih t y p e r c u b eg x a p h a n di t spp o w e r sh ：，t h i sp a p e rs t u d i e st h e e d g ed i s t i n g u i s h i n gn u m b e ro ft h en d i m e n s i o n a lh y p e r c u b eg r a p h 风，t h es q u a r eo f t h en d i m e n s i o n a l h y p e r c u b eg r a p h p a n dt h e p ( 2 ) p o w e r so f t h en d i m e n s i o n a lh y p e r c u b eg r a p hh ：，a n do b t a i n st h ee d g ed i s t i n g u i s h i n gn u m b e ro ft h e n - d i m e n s i o n a ih y p e r c u b eg r a p ha n di t s s q u a r e a n d a l l u p p e rb o u n d a r y o ft h e p ( 2 ) p o w e r so f t h e 玎一d i m e n s i o n a lh y p e r c u b eg r a p h ，n a m e l y , t h ee d g ed i s t i n g u i s h i n g n u m b e ro f g r a p h h 2 i s 3 f o rn 一2 ，a n d 2 f o rn 3 ，t h ee d g e d i s t i n g u i s h i n g n u m b e r o f g r a p hh ：i s2f o r ，l2 6 ，a n dt h eu p p e rb o u n d a r yo ft h ee d g ed i s t i n g u i s h i n gn u m b e ro f g r a p h 日：i s3 f o r ，l 七4 a n dn 苫p 2 k e y w o r d ：g r a p ht h e o r y ；h y p e r c u b e gd i s t i n g u i s + h i n gn u m b e r ；e d g ed i s t i n g u i s h i n g n u m b e r ；g r a p hc o l o r i n g m 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成硕士学位论文 ：! 担童直链亘匡剔数的班塞：。除论文中已经注明引用的 内容外，对论文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。 本论文中不包含任何未加明确注明的其他个人或集体已经公开发表或未公开发表 的成果。 本声明的法律责任由本人承担。 论文作者签名：年月同 学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连海事大学研究生学位论文提交、 版权使用管理办法”，同意大连海事大学保留并向国家有关部门或机构送交学位论 文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将本 学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫 描等复制手段保存和汇编学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于：保密口 不保密口( 请在以上方框内打“”) 论文作者繇 翩签冬；弱磊 日期：嘶，月少日 第1 章绪论 1 1 引言 图可区别数的概念是由图的破坏对称性问题引入的图的破坏对称性这个概 念最早是在r e c r e a t i o n a l 数学期刊的第7 2 9 个问题中被引入的【2 1 第7 2 9 个问题描 述如下：有一个盲人教授x ，他有一串用来开不同门的环形钥匙串，这些钥匙在 外表上看似乎都是一样的，以至于通过各种方法难以区分为此，很多人向这个盲 人教授x 提供了一些区分方法，由于这个教授是个盲人，有人建议盲人教授x 对 钥匙串上钥匙的手柄选择多种不同形状，使得他通过用手触摸的方法就能够逐一 区分出环形钥匙串上的每一个钥匙但是，又由于环形钥匙串的旋转性，使得从其 中的一个钥匙不能够察觉出其它钥匙，那么要使这个钥匙串上的所有钥匙彼此被 区分开，盲人教授x 至少需要多少种不同形状的钥匙手柄? 为了使这个问题更加一般化和理论化，有人把环形钥匙串问题引入到了图论 中图的顶点标号问题上加以研究他们把钥匙看作图的顶点，若两个钥匙在钥匙串 中是相邻的，则它们所对应图的两顶点间有一条边相连接，然后，再对图中的顶点 适当标号来破坏图中顶点的对称性，由此区分钥匙的问题就转化成去寻找它们所 对应图顶点可区别标号的最小个数问题，这个最小的可区别标号个数即被称为图 的可区别数 1 2 图的可区别数与局域可区别数的研究现状 1 2 1 关于图的可区别数研究 关于环形钥匙串展小标号数的问题研究，1 9 9 6 年，a l b e f t s o n 和c o l l i n s t m 结合 图顶点标号的自同构群理论，首次提出了图的可区别数的概念，图的可区别数是 图g 的所有顶点存在能够保持颜色分配的自同构群仅由单位元组成的最小色数 ( 简记为d ( g ) ) 首先，把带有n 把钥匙的环形钥匙串简化为具有n 个顶点的圈e ， 然后，对图中的顶点进行标号，井寻找到最小的可区别标号数当这个环形钥匙 串上的钥匙个数介于3 到5 之间，最小可区别标号数为3 ( 如图1 1 所示) ；若钥匙 的个数大于等于6 时，则最小可区别标号数仅为2 ( 如图1 2 所示) ，即d ( e ) - 3 ( 开一3 ，4 ，5 ) ，d ( c o ) - 2 ( 以6 ) ( a ) 圈c 3 的可区别标号图( b ) 圈c 4 的可区别标号图( c ) 圈c 5 的可区别标号图 图1 1 圈e0 - 3 , 4 ，5 ) 的可区别标号图 f i g 1 1 t h e d i s t i n g u i s h i n g l a b e l i n g g r a p h s o f t h ec y c l eef o rn - 3 , 4 ，5 22 2 图1 2 圈q 0 6 ) 的可区别标号图 f i g 1 2t h ed i s t i n g u i s h i n gl a b e l i n gg r a p ho fc y c l eef o r 月6 如果此环形钥匙串改为线形钥匙串，类似地，把带有n 把钥匙的线形钥匙串 简化为具有，1 个顶点的n 阶道路图只，然后，对图只的顶点进行标号，并寻找到最 小的可区别标号数当钥匙的个数为1 时，显然，最小标号数为1 ；当钥匙的个数 大于1 时，得到了最小标号数都为2 的结论( 如图1 3 所示) ，即d 假) 1 ， d ( 只) 一2 0 2 ) 1 2222 2 一_ 图1 3 道路只( ”2 ) 的可区别标号图 f i g 1 3t h ed i s t i n g u i s h i n gl a b e l i n gg r a p ho f p a t h 只f o rh 2 a l b e r t s o n 和c o l l i n s 3 】等人结合群论，把此类问题推广到其它的一般图及其所 对应的自同构群上a l b e r t s o n 和c o l l i n s 认为，对于具有相同顶点个数的两个标号 图，如果它们的自同构群相同，则它们具有相同的可区别数；如果两标号图的顶 点数不同，虽然他们具有相同的自同构群，但他们的可区别数可能不相同例如： t l 阶完全图蜀，岛的补图厶，单星图k 及n 阶完全图蜀的每一个顶点都附加一 个顶点且两点对应连接生成的知阶图q ，这4 个图的自同构群都恰好为n 阶对称 群e ，对于前三个图，不难得知d ( 疋) 一d ( j n ) 一d ( 墨，) - n ，而对于瓯也很容易 得到d ( g 。) ：f i 1 ( 如图1 4 所示) a l b c r t s o n 和c o l l i n s 3 1 又论证，如果一个图的 i i 自同构群a u t ( g ) 与二面体群同构，则此图的可区别数小于等于3 ；若一个图的自同 构群a u t ( g ) 为a b e l i a n 可交换群，则此类图的可区别数小于等于2 2 图1 。4 图g 5 一个可区别标号图 f i g 1 4ad i s t i n g u i s h i n gl a b e l i n gg r a p ho fg 5 3 c h e n g l 4 】在图的可区别数方面也作了很多的工作，他主要从组合学的角度对图 的可区别数进行了大量的研究首先，他仿照一般简单图的色多项式给出了一般简 单图g 的可区别多项式 旷( g ) | d ( g ：七) 一d ，( g ) h 其中，k f ，1 = k ( k 一1 ) 似一r + 1 ) ，d ，( g ) 表示用r 种颜色标号后的可区别标号图g 的顶点集坎g ) 的不同分区数然后，他又对树r 或森林f 的可区别数作了研究， 提出了对有根树从树根取可区别标号的方法，把此方法推广到无根树上，并对确 定树r 或森林，的可区别数给出了两个多项式时间算法 最近，b o g s t a d 和c o w e n 1 】提出了一个基于“脊”的技术和顶点着色的方法解 决了超立方体及其二次幂的可区别数问题，得到了n 维超立方体风及其2 次幂h ； 的可区别数为d ( h ) - - 3n ；2 3 ) ，d ( ) = 2 0 苫4 ) ，d 饵：) t 4 0 2 ，3 ) ，d 孵) 一2 4 ) 同时，对超立方体高次幂的可区别数问题提出了如下几个猜想和公开问 题： ( 1 ) 对于任意给定的正整数，l 和p ，e n 一1 p ，2 ，试确定，l 维超立方体p 次幂钟的可区别数d ( 日? ) ( 2 ) 对于指定的正整数p ，当n 充分大时，t , t 维超立方体p 次幂h i 的可区别 数d 瞪：、一2 ( 3 ) 当n 充分大时，对于变量p ，是否存在某一个恒定的正实数c ，使得n 维超立方体p 次幂日? 的可区别数d ( 日? ) sc p 1 2 2 关于图的局域可区别数研究 c h e n g 和c o w e n 5 1 在图可区别数理论研究的基础上，对图的可区别数进行了推 广，提出了图的局域可区别数的概念，图g 的局域可区别数是对图g 的顶点存在 f 局域可区别颜色标号数的最小颜色数，简记为l d ( g ) 其中，图g 的i 局域可区 别标号中是图g 的所有顶点在映射中：矿( g ) 一仉2 ，r t 进f f 标号后，标号图 g 的任意两个不同顶点u ，v 都有圮与m 不同构的标号m ( 研表示在图g 中以任 4 意顶点“为根且到顶点“的距离小于等于i 的所有顶点诱导出的子图) c h e n g 和c o w e n 5 1 又对图的局域可区别数进行了研究他们认为对于所有一般 图g 都有厶d 1 ( g ) 一o ( 1 0 9 n ) ，并特别地对圈q 的局域可区别数进行了研究，得到 了l d ( g ) = q 0 巩2 “”) ，又结合概率统计的方法得到了 l d 。( e ) s2 4 ( 2 t + 珈”。哪0 0 9 n ) 驯“ 最后，他们对超立方体图的局域可区别数问题提出了一些猜想和公开性问题 综上，图的可区别数问题，虽然来源于一个看似简单的钥匙串问题，但是， 它激发了很多学者的兴趣，推动了图与群论的研究，得到了很多良好的结论，并 提出了很多有待研究和解决的问题 1 3 本文的主要研究成果 本文主要研究了超立方体的一种结构特性超立方体三次幂可区别数和超 立方体及其高次幂的边可区别数问题 本文主要结构和研究结果： ( 1 ) 根据n 维超立方体及其高次幂的结构特性，研究了其顶点间距离与海明 距离的关系，给出了确定顶点坐标的充分必要条件，并结合“脊”的技术和顶点着 色的方法对n 维超立方体三次幂硪的可区别数进行了研究得到h 。3 可区别数的 一个上界：d ( 日；) 50 之6 ) ( 2 ) 对维数不超过7 的超立方体的可区别数进行了具体讨论，得到了 d ( h ；) 一8 ，d ( 日：) 一5 ，d ( h ；) 墨3 ，d ( h ：) t 2 0 = 6 ，7 ) ( 3 ) 在图可区别数研究的基础上，提出了图的边可区别数给出了行阶路只和 n 阶圈e 的边可区别数：根据n 维超立方体日。及其p 次幂睇的结构特性，得到 了，l 维超立方体以、订维超立方体的二次幂- 2 的边可区别数和n 维超立方体的 p ( 2 ) 次幂日：的边可区别数的一个上界，即见( ) = 3 ，见( 。) 一2 0 苫3 ) ， d 1 0 h ：) = 2 ( 订6 ) ，d ：( 砰 王3 0 24 ，n p 2 ) 第2 章基础知识 2 1 图论概念与记号 为讨论方便起见，首先引入些图论术语和记号，这些术语与记号主要来源 于参考文献 6 ，7 ，8 ，9 ： 图：所谓图g 是个三元组，记作g = ( h g ) ，e ( g ) ，妒( g ) ) ，其中 ( 1 ) h g ) = ( p l ，v 2 ，h ) ，h g ) 垂，称为图g 的结点( 顶点) 集合 c 2 ) e ( g = e l ，e 2 ，) 是g 的边集合，其中e i 为( ? ，v f ) 或( 崎，n ) 若e f 为( ”f ，v t ，) ，称e l 为以u 和u 为端点的无向边；若e f 为( ” h ) ， 称g i 为以v j 为起点，h 为终点的有向边 ( 3 ) 妒( g ) ：e 一陬y 称为关联函数 邻接结点：关联于同一条边的两个结点称为邻接结点 孤立结点：不与任何结点相连接的结点称为孤立结点 邻接边：关联于同一个结点的两条边称为邻接边 环：两个端点相同的边称为环或自回路 重边：两结点间方向相同的若干条边称为平行边或重边 无向图：每条边都是无向边的图称为无向图 平凡图：只有一个孤立结点的图称为平凡图 简单图：无环并且无平行边的图称为简单图 完全图：任何不同两结点之间都有边相连接的简单无向图称为完全图n 个结 点的完全图记作凰 阶：顶点的个数l 坎g ) i 称为图g 的阶 度数：设g 是任意图，x 为g 的任一个结点，与结点x 关联的边数( 一条环要 记两次) 称为x 的度数，记作d e g ( x ) 子图：如果v ( n ) c v ( c ) ，z ( 1 4 ) c e ( g ) ，称图h 是图g 的子图 补图：设g = ( ne ) 是，l 阶无向简单图以y 为顶点集，以所有能使g 成为 完全图蚝的添加边组成的集合为边集的图，称为g 相对于完全图为的 补图，简称g 的补图，记作g 圈：如果路p 的起点与终点相同，且起点与内部顶点互不相同，则称p 为圈， 长为n 的圈称为n 长圈，记为q 同构映射：设g ，h 是两个图，如果存在双射妒：v ( o ) 一v ( h ) ，使得 v ( u ，v ) e ( g ) 均有他以) ，妒( v ) ) e ( 日) ，则称妒为g 到日的同构映射， 且称g 与日同构，并记为g 日；图到自身的同构映射称为自同构映射 二进制标号图：设z - 1 五是长度为n 的二进制串，其中t 0 ，q f = 1 ，n 1 ，l ；如果对于图中的每一个顶点都用长度为甩的一个二进制 串来标记，则称该图为行：二进制标号图 p j 表示不超过x 的最大整数，卜1 表示不小于善的最小整数 2 2 超立方体 超立方体最早是由m i c h i g a n 大学的s q u i r e 和p a l a i s 从图论的角度提出来的多 年来，许多人对超立方体拓扑结构进行了较全面的分析和研究 玎维超立方体( 记为h 。) 是一个具有矽个结点的图它的结点度是n ，它的直 径也是，1 在咒维超立方体中，每个结点与其它栉个结点直接相连其结点采用 b r g c ( b i n a r yr e f l e c t e dg r a yc o d e ) 编码，任两个结点邻接当且仅当它们的编码只 有一位不同即y x ，y y ( 巩) ：x - x x 1 薯，y i y y n - l y 1 ，( x ，y ) e e 饵。) 当 且仅当3 k ：1 k 蔓n 使得 r y i ，f k ， x s 。1 只，f 。k 超立方体具有很好的网络特性和参数【1 0 ，1 1 1 ，如：边数为n x 2 、具有h a m i l t o n 性 等 一个n 维超立方体可以通过连接两个万一1 维超立方体的对应结点得到例如， 0 维超立方体有1 个结点；1 维超立方体有2 个结点，2 个结点的地址为0 和1 连 接两个1 维超立方体对应的结点，得到2 维超立方体，共有4 个结点这时结点地 址编号方法如下：保留原来的地址，并在地址高位另附加一位二进制位，把其中 的一个1 维超立方体的附加位设置为0 ，另一个1 维超立方体的附加位设置为1 这 样的编号方法能够保证相邻结点的地址只有一位不同如此，连接两个n 维超立方 体的对应结点得到n + 1 维超立方体低维超立方体的拓扑结构如图2 1 所示 0 o ol o 厂 。一 ( a ) h 1( b ) h ： o 0 0 1 0 0 0 00 1 0 ( c ) 也 ( d ) h 。 图2 11 ，2 ，3 ，4 维超立方体 f i g 2 11 ，2 ，3a n d4 - d i m e n s i o n a lh y p e r c u b e s 0 o o 2 3 超立方体的性质 超立方体结构具有正则性、对称性、结构递归性、可靠性、直径短等特点 2 3 1 正则性 n 维超立方体结点度为h ，即任意的顶点x 矿( 致) 都有d e g ( x ) 一n ，所以它是 n 正则图 n 维超立方体是正则的，说明它具有良好的对称性f 1 2 i ，也就是说它们的边和结 点的负载量分布是均匀的 2 3 2 结构递归性 定义2 1 设图g 1 - 以，巨) ，g 2 一( ，岛) ，g 1 和g ：的积( 记作g ；g 1 x g 2 ) 定义为： 矿( g ) - “，v ) l “k ，v k ， e ( g ) 一 ( 。，v m ) ，0 ：，v ：) ) i ( 。，u ：) e l 且u - v 2 ) ，或 。- “2 且( h ，v 2 ) e e ：) ) n 维超立方体巩也可递归地定义为： 叫妈麓。，置 其中岛为2 阶完全图 超立方体是一种可递归定义的网络结构，即它与其某些子图的结构在逻辑上 是等价的 2 4 超立方体的高次幂 定义2 2 嗍设g 是一个图，毛y 矿( g ) ，g 中所有从石到_ ) ，( 或y 到x ) 的路 的最小长度称为x 与y 的距离，记作d o ，) ，) ( 或d ( y ，x ) ) 若石不可达y ，则约定d ( x ，y ) a m 距离显然满足下列性质： ( 1 ) d 0 ，y ) 苫0 ； ( 2 ) d ( x ，x ) 一0 ； ( 3 ) d ( x ，_ ) ，) + d ( _ ) ，z ) 乏d ，z ) 另外，称 d ；m a x d 0 ，) ，) i v x ，y 矿( g ) 为图g 的直径 定义2 3 “”设工，_ ， 0 ，掣，则x 与y 间的h a m m i n g 距离 ，) ，) 指的是x 与y 间 取不同分量的个数( 许多文献也将之记为d u o ，) ，) ，本文采用前一种记法) 傍42 1 x 一( 0 1 1 0 0 1 0 1 ) ，y - 0 0 0 0 0 1 1 1 ) ，z 。( 0 1 1 0 0 1 0 1 ) 贝0 h ( x ，y ) 4 ，矗0 ，z ) ；0 定义2 4 图片：表示，l 维超立方体图以的p 次幂，它与以有相同的顶点集 若顶点z ，y 在巩中的距离小于等于p ，则x ，y 在h ：中有一条边相连接 显然，当p 一1 时，图日：就是图风 当p 一2 时，低维超立方体二次幂的拓扑结构如图2 2 所示 o o ( a ) 啦 0 0 00 1 0 ( b ) 研 o 图2 22 ，3 维超立方体_ = 次幂 f i g 2 2t h es q u a r eo ft h e2 a n d3 - d i m e n s i o n a lh y p e r c u b e s 第3 章超立方体三次幂的可区别数 1 9 9 6 年，a l b e r t s o n 和c o l l i n s l 3 1 提出了图的可区别数的概念，并进行了一般性 的研究，得n t 如下一些结论：若图g 的自同构群是可换群，n o ( g ) 王2 ：若图 g 的自同构群与二面体群同构，则d ( g ) s 3 ：，l 阶路只的可区别数为d ( p n ) = 2 0 2 ) ；订阶圈g 的可区别数为d ( g ) = 2n ；3 , 4 ，5 ) ，d ( g ) = 2 苫6 ) b o g s t a d 和c ( ，w e n 【1 】确定了开维超立方体塌及其2 次幂斫的可区别数为d ( 磁) - 30 一z 3 ) ， d ( 峨) = 20 2 4 ) ，d ( 日：) = 4 = 2 ，3 ) ，d 忸：) 一2o 芑4 ) 关于图可区别数的其他 研究可参考文献【4 ，5 ，1 3 】 3 1 预备知识 3 1 1 图的可区别数概念 定义3 1 “1 设g 是一个图，若存在映射垂：v ( a ) 一 1 ，2 ，) ，则称图g 为一 个r 标号图，记作( g ，西) 定义3 2 “1 若矿( g ) 存在一个置换石不仅能够保持圈g 的邻接关系，而且能够 保持图g 的标号，则称玎为( g ，叫的一个自同构；即在自同构玎下，v v v ( a ) 都 有中( v ) 一西( 玎p ) ) ，并e a t ( a ，中) 为图g 在映射中下的保持标号的自同构群 定义3 3 “1 若r 标号图( g ，圣) 的自同构群a u t ( g ，中) 仅由单位元组成，则称图 ( g ，中) 是r 可区别的 定义34 。1 若图( g ，中) 是个r 可区别的标号图，则称最小的数r 为图( g ，中) 的可区别数 在下文中也会使用不同颜色来代替不同的标号，由此，为标号图( g ，币) 寻找最 小的可区别数可以转化为寻找最小的颜色数b 3 1 2 记号 记u ( f = 1 ，2 ，n ) 为日：中坐标左起第1 位至第f 位都为0 ，其余位都为1 的顶 点，为所有位皆为1 的顶点： ”l - 0 1 1 1 1 1 1 1 ， 1 2 2 0 0 1 1 1 1 1 1 ， v = 0 0 0 0 0 0 0 0 ， 一1 1 1 1 1 1 1 1 ， 即，u = 0 t 一0 = 1 , 2 ，n ) ，一r 用o ，y ) 和 w 0 ，y ) 分别表示z 与y 在群 中的距离和海明距离( 在不至于混淆的情况下分别筒记为d ( x ：y ) 和 0 ，y ) ) 32 超立方体高次幂可区别数的几个结论 引理3 一，y h ? 印z p ，1 ) ，有 删吖警1 引理3 2v y h ? o p 1 ) ，石pp 。g - o ，1 ，2 ，h ) ，有 ( 1 ) d o ，u ) - a ( x ，叶一。) + 1 的充分必要条件是 h ( x ，u 一。) = p 矗( x ，k ，) 丘“，u ) # p d ( x ，v f _ 1 ) + l 此时x 的第i 位坐标是1 ( 2 ) d ( x ，q ) = d ( x v f 一。) 一1 的充分必要条件是 ( z ，u _ 1 ) 一p d ( x ，q ) + 1 h ( x ，u ) 一p d ( x ，u ) 此时x 的第i 位坐标是0 证明( 1 ) 由引理3 1 易知充分性成立下证其必要性 显然，v x 只? ，有 0 ，v 。) z 0 ，v 。) + - 1 由引理3 1 ，有 f 掣卜昨小俐吖掣 所以，必有 0 ，v ，) = h ( x ，p 。) + 1 进而x 的第f 位坐标是1 - 下i e h ( # ，k 4 ) 墨p d ( 茗，v ；一。) 若不然，由引理3 1 及d 0 ，u ) - d o ，q 。) + 1 ，设 若不然，由引理3 1 及d 0 ，u ) - a ( x ，q 。) + 1 ，设 0 ，v f 1 ) 害p d o ，v i 1 ) 一r ( 0 1 ) ，有h ( x ，) + 矗 ，k ) = 押 证明 由于h ? 中的顶点x 所对应的标号为h 长o l 串，即h ( x ，i ：o ) 为z 所对应 标号中所有0 的个数，h ( x ，k ) 为x 所对应标号中所有1 的个数，所以 a ( x ，f o ) + i l ( z ，u ) 一n 3 3 超立方体三次幂可区别数的一个上界 b o g s t a d 和c o w e n 1 1 提出了一个基于“脊”和对顶点适当着色的方法，确认了 所有顶点的坐标，解决了超立方体及其二次幂可区别数的问题本文借助日：中顶 点的距离和海明距离的关系，以及b o g s t a d 和c o w e n l l 】的方法给出了超立方体三次 幂日：0 z6 ) 可区别数的一个上界 引理3 5 设g 为h ：q 6 ) 中的顶点v 0 ，q ，v ：，v l 和w ；1 2 0 ”2 诱导出的子图 如对g 中顶点着白色，则在日；中g 的顶点可被确认 证明如图3 1 所示，在子图g 中，由w 与诸v ；的距离以及诸v ；之间的距离易 l4 日d e g o ( 一2 ，d e g g ( v o ) 一3 ，d e g g ( h ) 。4 ，d e g g ( v 2 ) = d e g g o _ 一2 ) = d e g g ( k 一1 ) = 5 ， d e g 。0 。) 一4 ，d e g 。( u ) 一6 ( f 一3 ，4 ，- 一，n 一3 ) ( 1 ) 由于只有w 的顶点度数为2 ，w 可先被确认； ( 2 ) 与w 邻接的点只能有一1 和咋，因d e g g “一1 ) - 5 # 4 = d e g g n ) ，故咋_ l ，匕 可分别被确认； ( 3 ) 因只有的顶点度数为3 ，故可被确认； ( 4 ) 除k 外，只有v l 的顶点度数为4 ，故y 。可被确认； ( 5 ) 除k 一。外，顶点度数为5 的点只有y ：和k 一：，因v ：与邻接，而一：( n ，5 ) 不与v 。邻接，故v 2 与k 一2 也可被确认； ( 6 ) 由于月 5 ，所以，至少存在一个顶点v ，使d e g 。( v ，) 16 ( 3 s ，n - 3 ) 若 r ；6 ，则只有d e g g 化) 一6 ，v ，可被确认若n 6 ，由递归法，首先，虽然 d e g g ( v 3 ) = d e g g ( v 。) - 6 ，f ge h s ：v ，与v 0 相邻，而y 。不与v o 相邻，因此，b 与v 。被 确认；令k ，4 ，假设当，c k 时，所有v ，都被唯一确认；最后，因v 。与v k - 3 相邻， 可以确认最后一个未被确认的v 。至此，白色点都被确认 苗 巧 g 3 苫 图3 1 子圈g f i g 3 1t h es u b g r a p hg 在日：中，对于非白色点石，2 及v i e o ，1 ，忍 ，若由d ( x ，u ) 的确定性及引理3 2 ， 3 3 和3 , 4 ，仍存在七一1 个，使得j l 亿”j ) 7 苜h ( x ，”h ) = 3 r + 2 ，_ j 1 0 ，”) = 3 r + 域 3 r + 3 ， 0 ，v m ) 一3 r + 2 的情况( 其中r * d o ，匕) 一1 ) ，则称这样的z 为职的第七类 相似点：若存在异于x 的非白色点y ，对 0 ，1 ，n ) 都有d 0 ，u