（应用数学专业论文）archimedean平铺与二进制hamming图.pdf

中文摘要 摘要 化学图论中，有许多拓扑参数是以图中点距为基础的，w i e n e r 数就是其 中之一。它是w i e n e r 在1 9 4 7 年首次提出的人们对w i e n e r 数的研究也持 续了半个多世纪，获得了一系列的结果本文研究某些a r c h i m e d e a n 平铺的 有限子图的w i e n e r 数 本文分为三章，第一章为引言，第二章着重考虑a r c h i m e d e a n 平铺。我 们找出了其中所有的对应于二进制h a m m i n g 图的平铺，以后我们称这类平 铺为二进制h a m m i n g 平铺事实上，这样的二进制h a m m i n g 平铺只有四 个，恰是a r c h i m e d e a n 平铺中的点类型为4 4 4 4 ，6 6 6 ，4 8 8 ，4 6 1 2 这四个平 铺进而我们推广了计算苯系统w i e n e r 数的方法于这四个平铺，并用于计算 了若干个例子 在第三章中，我们简单阐述了广义四角链关于w i e n e r 数的极链的结论 对矗磊，用形( 瓦) 表示瓦的w i e n e r 数我们证明了对任意的广义四 角链瓦兀，当n 为奇数时，有w ( h n ) w ( t n ) w ( l n ) ，左边的等式成 立当且仅当及= 冠；，右边的等式成立当且仅当瓦= 厶，当n 为偶数时，有 ( 磁) ( 已) w ( l 竹) ，左边等式成立当且仅当死= 上砭，右边等式成立 当且仅当矗= n ，这里l n 表示线性四角链，王k ( n 为奇数) 是螺旋链， 磁( n 为偶数) 我们会在文中给出定义 关键词。w i e n e r 数；a r c h i m e d e a n 平铺；二进制h a m m i n g 图 英文摘要 a b s t r a c t i nc h e m i c a lg r a p ht h e o r y , s e v e r a lm o l e c u l a rt o p o l o g i c a li n d i c e sa l eb a s e d o nv e r t e xd i s t a n c e s w i e n e rn u m b e rw h i c hc o n c e i v e db yw i e n e ri n1 9 4 7i so n e o ft h e m p e p o l eh a v es t u d i e dw i e n e rn u m b e rf o rm o r et h a nh a l fo fa c e n t u r y a n do b t a i nas e r i e so fr e s u l t s 。i nt h i st h e s i s ，w ec o n s i d e rt h ew i e n e ri n d e xo f s e v e r a ls u b g r a p h so fs o m ea r c h i m e d e a nt i l i n g s t h ew h o l ed i s s e r t a t i o ni n c l u d e st h r e ec h a p t e r s t h ef i r s tc h a p t e ri si n t r o - d u c t i o n i nt h es e c o n dc h a p t e r ，w er e s t r i c ta t t e n t i o nt oa r c h i m e d e a nt i l i n g s w ef i n da l lt h et i l i n g sc o r r e s p o n d i n gt ob i n a r yh a m m i n gg r a p h ( s a yb i n a r y h a m m i n gt i l i n g ) i na r c h i m e d e a nt i l i n g aa c t u a l l yt h e ya r eo n l yf o u rs u c h t i l i n g s ：( 4 4 4 4 ) ，( 6 6 6 ) ，( 4 8 8 ) a n d ( 4 6 1 2 ) t h e nw ee x t e n dt h em e t h o dt o c o m p u t i n gt h ew i e n e rn u m b e ro fb e n z e n o i ds y s t e mt ot h e s ef o u rt i l i n g s ，a n d c o m p u t es o m ee x a m p l e s i nt h et h i r dc h a p t e r ，w em a k eab r i e fi n t r o d u c t i o no nt h ee x t r e m a lg e n e r a l - i z e dp o l y o m i n oc h a i n so nw i e n e rn u m b e r f o ra n yg e n e r a l i z e dp o l y o m i n oc h a i n 死磊，d e n o t ew ( ) t h ew i e n e rn u m b e ro f 瓦w es h o wt h a tf o ra n yg e n e r - a l i z e dp o l y o m i n oc h a i n 瓦磊，w h e nni so d d ，( 日。) w ( 死) w ( l n ) ， w i t ht h el e f te q u a l i t i e sh o l d i n go n l yi f 瓦= 巩，a n dt h er i g h te q u a l i t i e sh o l d - i n go n l yi f 已= 五n ，w h e nni se v e n ，( 硪) s ( 瓦) w ( l n ) ，w i t ht h el e f t e q u a l i t i e sh o m i n go n l yi f 瓦= 磁，t h er i g h te q u a l i t i e sh o l d i n go n l yi f 死= l n ， w h e r eki st h el i n e a rc h a i n s ，风i so d d ) i st h eh e l i xc h a i n sa n d 磁i s e v e n ) w i l lb ed e f i n e di nt h ea r t i c l e k e yw o r d s ：w i e n e rn u m b e r ；a r c h i m e d e a nt i l i n g ；b i n a r yh a m m i n gg r a p h 厦门大学学位论文原创性声明 兹呈交的学位论文，是本人在导师指导下独立完成的 研究成果。本人在论文写作中参考的其他个人或集体的研 究成果，均在文中以明确方式标明。本人依法享有和承担 由此论文而产生的权利和责任。 声明人( 签名) ：滔蕴箭 年月 e t 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规定。 厦门大学有权保留并向国家主管部门或其指定机构送交论 文的纸质版和电子版，有权将学位论文用于非赢利目的的 少量复制并允许论文进入学校图书馆被查阅，有权将学位 论文的内容编入有关数据库进行检索，有权将学位论文的 标题和摘要汇编出版。保密的学位论文在解密后适用本规 定。 本学位论文属于 1 、保密() ，在年解密后适用本授权书。 2 、不保密( ) ( 请在以上相应括号内打 广) 作者签名： 导师签名： 滔旌静 7 z 磁 日期： 日期： 年月 日 年月 日 第一章引言 第一章引言 平铺( t i l i n g ) ，拥有很悠久的历史，起源可追溯到公元前四千年，当时古 希腊人用规则的几何图案与瓷砖来装饰庙宇【1 1 平铺最早是由k e p l e r 作为数 学对象进行研究的【2 】，他发现了各种各样的平铺，并对它们进行系统思考 平铺用数学语言来阐述如下【3 】。 个平面平铺t 是指一族可数闭集t = 丑，t 2 ， 这些闭集能够无空 隙且不重叠的覆盖平面其中五，正，称为平铺z 的瓷砖 这里我们要说明两点： 1 、可数闭集t = 丑，t 2 ，) ，这里就排除了面积为零的瓷砖( 如点或 线段) ，因为面积为零的瓷砖当它们无空隙的覆盖平面时，其数目一定是不可 数的 2 、不重叠意味着t 中的任意两块瓷砖的交集面积为零 在个平铺中，两个瓷砖的边界称为棱( e d g e ) ，梭的端点称为点( v e r t e x ) 对于一片瓷砖，它的边称为边( s i d e ) ，两条边的交点称为隅角( c o r n e r ) 如图 1 所示，b c d e 是瓷砖r 与s 的边界，所以它是一条棱，但不是任何块 瓷砖的边b c ，c d ，d e ，f g 是瓷砖s 的边，但不是平铺的任何一 条棱g 是瓷砖s 与t 的隅角，但不是平铺的任何一个点 图1 对于个平铺，如果其瓷砖的边与隅角分别与平铺的棱与点重合，称这个 平铺是边对边的，否则这个平铺不是边对边的【3 ，4 】 在本文中，我们只考虑由正多边形构成的边对边的平铺 1 第一章引言 2 因此，对于平面上的一个点，如果它是任意一个由正多边形构成的边对边 的平铺t 中个正多边形的顶点，那么它肯定也是它所在的其它正多边形的 顶点，我们就可以称这个点为平铺r 的点，同样的，对于任意一条边，如果它 是一个正多边形的一条边，那么它也恰是另外一个它所在的正多边形的边， 我们把这条边称为平铺t 的边实际上，平铺从定义上是一个可数闭集的集 合，当把平铺的瓷砖铺成平面后，这时平铺就成了平面的平铺，它的点和边就 可以理解为一个图，所以我们可以从图论的角度来看待平铺 有了平铺的数学定义，在继k e p l e r 将近三百年之后，平铺重新出现在数 学家的视野中【5 ，6 】众所周知，瓷砖是相同的全等正多边形所构成的平铺， 它们的瓷砖必定是只有正三角形、正方形或正六边形，如图2 所示 随后数学家开始从点的类型来描述正多边形构成的边对边的平铺以下我 们研究的有正多边形构成的边对边的平铺可以有不同类型的瓷砖 1 a ) ( ” 图2 在平铺中，如果一个点轮转( 顺时针或逆时针) 地被正扎边形( 依次为正 n 1 ，他，珥边形) 共用，则称这个点是n i 佗2 狲类型( t y p e ) 由于每个正礼边形的内角为m 一2 ) 7 r 肛。通过简单的推导，很快能得到 点的类型共2 1 种( 见【3 】) ，如下所列 ( 1 ) 3 3 3 3 3 3 ( 2 ) 3 3 3 3 6 ( 3 ) 3 3 3 4 4 ( 4 ) 3 3 4 3 4 ( 5 ) 3 3 6 6 ( 6 ) 3 6 3 6 ( 7 ) 3 4 4 6 ( 8 ) 3 4 6 4 ( 9 ) 4 8 8 ( 1 0 ) 6 6 6 ( 1 1 ) 5 5 1 0 ( 1 2 ) 3 7 4 2 ( 1 3 ) 3 4 3 1 2 ( 1 4 ) 4 4 4 4 ( 1 5 ) 3 8 2 4 ( 1 6 ) 3 1 2 1 2 ( 1 7 ) 3 9 1 8 ( 1 8 ) 3 3 4 1 2 ( 1 9 ) 4 5 2 0 ( 2 0 ) 4 6 1 2 ( 2 1 ) 3 1 0 1 5 很自然的，人们思考什么样的平铺中所有点的类型都一样对此，有这样 的结果。在由边长相同的正多边形构成的边对边的平铺中，仅有1 1 种平铺，它 们的点都是同一类型的人们把这样的平铺称为a r c h i m e d e a n 平铺事实上， 在上面所列的2 1 种点类型中，有1 0 种点类型作为起始点的类型是无法得到 个平面的a r c h i m e d e a n 平铺的剩余的1 1 种点类型作为起始点的类型，确 实可以得到个平面的a r c h i m e d e a n 平铺【4 】对于任意个a r c h i m e d e ：a n 第一章引言 3 平铺，若它的点类型为a b c ，我们用( a b c ，) 来表示这个平铺 如果平铺t 中有k 类顶点，那么称t 为k a r c h i m e d e a n 平铺 同时，人们又从另一个角度来研究点对平铺中的两个顶点a 、b ，称 a 、b 是等价的，如果存在平铺t 的个对称变换，( 由一些平移或旋转构 成的变换) ，使得f ( a ) = b 所有与a 等价的顶点的集合称为a 的传递类 同样的，在由边长相同的正多边形构成的边对边的任一平铺中，如果所 有的点都属于一个传递类，称这样的平铺为u n i f o r m 平铺数学家在找所 有的u n i f o r m 平铺也走过了一条不平坦的路，在现代是s o m m e r v i l l e 7 与 a n d r e i n i 8 分别独立的且不依赖于前人研究的成果给出了共1 1 个u n i f o r m 平铺 非常有意思的是，这1 1 个u n i f o r m 平铺恰好就是a r c h i m e d e a n 平铺， 即对任意一个a r c h i m e d e a n 平铺，它的所有顶点不仅是一个类型，而且都属 于个传递类 同样，对于平铺t ，如果t 所有的顶点关于t 的对称变换集合s ( t ) 的 传递类共有类，称t 为k u n i f o r m 平铺 k r o t e n h e e r d t 进一步研究了在由边长相同的正多边形构成的边对边平铺 中，什么样的平铺既是k u n i f o r m 平铺又是k a r c h i m e d e a n 平铺，即平 铺的点的传递类与类型个数相同对于点的类型与传递类均为k 的平铺，称 为k r o t e n h e e r d t 平铺用k ( k ) 来表示传递类与类型均为k 的k r o t e n h e e r d t 平铺的个数一 k r o t e n h e e r d t 得到这样的结论【9 ，1 0 】。 k ( 1 ) = 1 1 ，k ( 2 ) = 2 0 ，k ( 3 ) = 3 9 ，k ( 4 ) = 3 3 ，k ( 5 ) = 1 5 ，k ( 6 ) = 1 0 ，k ( 7 ) = 7 ，k ( k ) = o ( k 8 ) 这里，我们说明两点s 第一，如果一个平铺是m a r c h i m e d e a n 平铺，且是n u n i f o r m 平 铺，则有m 死换句话说，若两个点类型不同，则它们必属于不同的传递 类，而若这两个点属于不同的传递类，并不能得出它们的类型一定不同，相同 类型的点也可能属于不同的传递类 第二，对于a r c h i m e d e a n ，它意味着任何的两个顶点，它们“看上去很 像。；而对于u n i f o r m ，则暗示着在整个平铺的对称变换下点的等价，具有更 强的性质 第一章引言 4 接下来，我们介绍一下图论中个拓扑指标：w i e n e r 指标w i e n e r 指 标是定义在化合物分子图上基于图中距离的拓扑指标，也是所有拓扑指标中， 最古老、被研究最多的拓扑指标它最早是由美国物理化学家h a r o l dw i e n e r 在1 9 4 7 年提出的，是用来估计化合物链烷的沸点【1 1 】，在【1 1 】中w i e n e r 得 到了个依赖于链烷分子图( 即一棵树) 的值，这就是后来的w i e n e r 指标， 并且给出了与链烷沸点( 功) 之间的一个关系式： b p a w + 8 p + l 这里o l 、p 与7 为经验常数，p 为分子图中距离为3 的顶点对的个数 w i e n e r 随后还证明了与有机化合物的其它物理化学性质，如分子体 积、折射指标、蒸发所需要的热量等性质有关 到了上世纪七十年代，w i e n e r 指标又重新被研究，这一时期，个最显著 的结果就是揭示了w i e n e r 指标与树的拉普拉斯矩阵的特征值相关的m e r r i s - m c k a y 定理【1 2 】由于当时w i e n e r 是在树上定义w i e n e r 指标，在1 9 7 1 年，h o s o y a 将w i e n e r 指标由原来只限在树上的定义推广到有圈情形并给出 了图理论方面的公式【1 3 j ，也就是今天我们运用的w i e n e r 指标的定义t 图 中顶点对间的距离之和 此时，对w i e n e r 指标的研究已经非常广泛了通过进步的研究还发现， w i e n e r 指标在有机与聚合化学、晶体及药物设计等领域也有广泛的运用，此 外，w i e n e r 指标还与计算机网络的个参数一平均距离有关w i e n e r 指 标在数学上的研究及应用可参考【1 4 ，1 5 】从而出现大量的文献关于计算各种 化合物分子图的w i e n e r 指标，伪如【2 7 - 2 9 ，同时，也刺激了基于图中距离 的拓扑指标的发展，例如h y p e r w i e n e r 指标，s c h u l t z 指标等在1 9 8 8 年，h o s o y a 进一步提出了基于图中距离的多项式【1 6 】，称为h o s o y a 多项 式，g u t m a n 等人在【1 7 】认为h o s o y a 多项式比至今任何一个基于图中距离 的拓扑指标所含的信息含量都要多 在对分子图的w i e n e r 指标的研究中，最成熟的是对树和苯系统的研究， 在这两方面已经得到了大量结果t 如树与苯系统的w i e n e r 数计算方法的改 进；在给定最大度且顶点数为n 的树的集合中，寻求w i e n e r 数最小的树的 结构；以及以w i e n e r 指标大小对某些树进行排序；六角链关于w i e n e r 数的 极链等等，可以参见最近的两篇综述【1 8 ，1 9 】 第一章引言 5 其中对w i e n e r 数的计算，一直被人们所关注w i e n e r 在1 9 4 7 年给出 了w i e n e r 指标的定义的同一篇文章中【1 1 】，还得到了对于计算顶点个数为 n 的树的w i e n e r 数的另一个较直观简便的计算公式。 w ( t ) = ：n l ( e ) n 2 ( e ) e e ( t ) 和式取遍丁中所有的边，其中若e 的两个端点为z 和y ， n l ( e ) = i t ，lt ，y ( t ) ，d r ( 秒，z ) 由( 钞，秒) ) i ， 佗2 ( e ) = i 口i 钐y ( t ) ，d r ( 曰，秒) i 在近半个世纪后，1 9 9 5 年，s a n d ik l a v 艺a r 、i v a ng u t m a n 和b o j a n m o h a r 得到了对所有的二进制h a m m i n g 图的w i e n e r 数的计算也有类似的 公式f 2 0 在【2 0 l 中，特别的以苯系统为例，在定义了苯系统的基本割线段基础上， 证明了苯系统为二进制h a m m i n g 图，并通过基本割线段给出了苯系统的一 个二进制h a m m i n g 标号i v a ng u t m a n 和s a n d ik l a v 岩a r 在【2 1 】中以此为 基础进一步给出了一个直观简便的方法来计算苯系统的w i e n e r 数，我们称 这个方法为基本割方法之后，i v a ng u t m a n 等人计算了一系列苯型烯烃类 分子图的w i e n e r 数f 2 二2 4 注意到，苯系统g ( 如图2 ( b ) ) 是一个没有割点的有限平面连通图，它的 每个内部都被边长为1 的正六边形包围由此可见苯系统是由边长均为1 的 正六边形构成的边对边的平铺的子图 因此，本文我们在a r c h i m e d e a n 平铺中找出所有的二进制h a m m i n g 平 铺，并用类似于【2 0 l 中的思路将基本割方法推广到这类二进制h a m m i n g 平 铺及其子图的w i e n e r 数计算上，进而我们计算了这些二进制h a m m i n g 平 铺的一些子图的w i e n e r 数 特别的，由于由边长均为1 的正方形构成的平铺是二进制h a m m i n g 平 铺，所以对于它的一类子图：四角链，我们同样也能用基本割方法来计算它的 w i e n e r 数这个方法对于我们寻找广义四角链关于w i e n e r 数的极链也有很 大的帮助，如果直接寻找极链，本身是比较困难，通过基本割计算方法帮助我 们找到了在长为n 的广义四角链的集合中极链所属的个较小的集合，最后 得以确定广义四角链的关于w i e n e r 数的极链 第二章a r c h i m e d e a n 平铺与二进制h a m m i n g 图 6 第二章a r c h i m e d e a n 平铺与二进制h a m m i n g 图 2 1预备知识 在这一节里，我们首先介绍与本文有关定义和结论，为后面的定理作准 备 定义2 1 1 【1 3 lg 是个连通图，职g ) 表示g 的点集，n ( a ) 表示g 的顶点数，耳g ) 表示g 的边集，那么g 的w i e n e r 数为 w ( c ) = ：d ( u ，v i a ) 缸。v g v ( a ) 这里d ( u ，秽i g ) 表示点u 与点口的距离，和式取遍g 中所有点对 定义2 1 2 1 2 0 为一个有限字符集合， t 0 1 与伽2 由中的字符组成的 等长的字符串，这两个字符串对应位置上的字符或者相同，或者不同把对应 位置上字符不同的这样的位置的个数定义为t t 7 l 与她的h a m m i n g 距离，记 为日( 伽1 ，w 2 ) 定义2 1 3 2 0 | 对于图g ，给g 中每个点口赋予一个等长字符串，即 标签z m ，如果对g 中任意两个点u 与秽，有研，f 俐，f 以w = d m ，砂，其中 d ( u ，v l g ) 为点u 与u 在g 中的距离，那么称g 为h a m m i n g 图特别的， 如果= 0 ，1 ) ，即任意一个点的标签都由o 与1 构成，则称g 为二进制 h a m m i n g 图，同时称z 为g 的个二进制h a m m i n g 标号 定义2 1 4 1 2 0 称g 中的子图日为g 的凸子图，如果日满足：日是连 通的，并且对于日中任意两个点t 、t ，它们在g 中的最短路完全落在日 中 对g 中任意一条边伽，v 0 = 扣l 叫y ( g ) ，d g ，乱) 表示 在g 中与t 点的距离小于与刨点的距离的点的集合 显然，若g 是二部图，有k 够u = v ( a ) 定义2 1 5g 是个a r c h i m e d e a n 平铺中点类型均是偶数构成的平铺 的子图，并满足子图每一个内部的区域都被个边长为1 的正多边形包围 g 的基本割线段是这样的一条线段：它与g 中某些边垂直，连接这些边的中 点，起始于g 的边界终止于g 的边界，只能接触边界两次，并且从g 中删去 与c 相交的边后恰好形成两个连通分支( 见图3 ) 第二章a _ r c h i m e d e a n 平铺与二进制h a m m i n g 图 7 q 图3 苯系统中的一些基本割线段 对g 中任一条边牡移。u t ，必然与g 中一基本割线段c 垂直，且只与这 条基本割线段c 垂直 与这条基本割线段c 相交的边组成的集合称为g 的属于c 一个基本割 集含边删的基本割集记为瓯 由定义可知，每条边属于且仅属于个基本割集，且所有基本割集的边的 并为图g 的边集 单连通四角系统 多连通四角系统 图4 从图论的观点来看，我们可以把a r c h i m e d e a n 平铺理解为个二连通图， 其每个内部都被边长为l 的正多边形包围平面的平铺可以是有限图也可以 是无限图对于平面的平铺的子图，一般都包括带。洞。( 多连通) 的情形， 即允许其内部面被挖空本文只对平面的平铺不带“洞。( 单连通) 的子图进 行讨论( 见图4 ) 2 5 】 下面我们介绍一些对本文非常重要的已知结果 引理2 1 1 由边数为偶数的边长相等的正多边形构成的边对边的平铺是 二部图 第二章a r c h i m e d e a n 平铺与二进制h 龇n m i n g 图8 引理2 1 2 1 2 0 ) g 是个二进制h a m m i n g 图， z ：v ( g ) 一_ o ，1 】口是 g 的长为口的个h a m m i n g 标号，g 的顶点数n ，啦0 = 1 ，2 ，g ) 表示 标号的第i 位为1 的顶点的个数那么g 的w i e n e r 数为 三 w ( g ) = ：啦m m ) i = l 引理2 1 3 1 2 0 图g 是二进制h a m m i n g 图当且仅当g 是二部图，并且 对于g 中任意一条边删，与生成的子图为g 的凸子图 第一章提到的a r c h i m e d e a n 平铺是平铺内所有点都是一个类型的平铺， 这样的平铺有1 1 个，它们分别为： ( 1 ) ( 4 4 4 4 ) ( 2 ) ( 6 6 6 ) ( 3 ) ( 3 3 3 3 3 3 ) ( 4 ) ( 8 8 4 ) ( 5 ) ( 4 3 4 3 3 ) ( 6 ) ( 6 3 6 3 ) ( 7 ) ( 4 6 1 2 ) ( 8 ) ( 1 2 3 1 2 ) ( 9 ) ( 6 4 3 4 ) ( 1 0 ) ( 6 3 3 3 3 ) ( 1 1 ) ( 4 4 3 3 3 ) 由此得出引理2 1 4 引理2 1 4 【3 】在a r c h i m e d e a n 平铺中，由偶数构成的点的类型只有以下 四类。4 4 4 4 、6 6 6 、4 8 8 、4 6 1 2 2 2a r c h i m e d e a n 平铺与二进制h a m m i n g 图 定理2 2 1a r c h i m e d e a n 平铺中所有的二进制h a m m i n g 平铺为( 6 6 6 ) 、 ( 4 4 4 4 ) 、( 4 8 8 ) ，( 4 6 1 2 ) 证明：首先我们断言：对于( 6 6 6 ) ，( 4 4 4 4 ) 、( 4 8 8 ) 、( 4 6 1 2 ) 这四个 平铺的任意子图，选取任意个基本割线段c ，它对应的基本割集为瓯”， 设加为与g 彤中某一条边相关联且与让位于c 同侧的点，则t 点与w 点间 沿着基本割集方向c 路必是u w 间的最短路 我们来分情况讨论一下 1 坩 越 r 图5 c 如图5 ，左边是一个( 4 4 4 4 ) 的子图，为了便于观察，我们把左边的图画 成右边的图从图上可知，删，间的最短路必是u 点与w 点间沿着基本割集 第二章a r c h i m e d e a n 平铺与二进制h a m m i n g 图 9 c 0i r i i t 。 l t i【llil 。：i ： v 图6 ， i ， 图7 c 图8 图9 c 第二章a r c h i m e d e a n 平铺与二进制h a 工n m i n g 图 图l o c 第二章a r c h i m e d e a n 平铺与二进制h a m m i n g 图 1 1 方向g 分路，因为( 如图5 中) 从w 到乱横向必须要走3 步，若不沿着基本 割集方向c 走，则必然要走纵向的路，那么显然比直接横向走距离要长 图6 的左边( 6 6 6 ) 的子图，同样的把左边的图画成右边的图来观察注 意到t 与伽在同一水平位置上，在方形图中，从叫到t ，若不从水平横向 走，则必然要走纵向，这样的路必不是最短路可见原图中沿着基本割集方向 气路必是缸点与t ，点间的最短路 图7 与图8 的左边均为( 4 8 8 ) 的子图，我们也将其画成右边的图来观 察由于边的不同的取向， ( 4 8 8 ) 有两种不同的基本割线段，我们分别在图 7 与图8 中加以讨论在图8 中，我们把正方形上下两点粘在一起，这样做法 并不影响我们通过方形图来分析t 与幻间的最短路显然这两个图都表明t 与w 间的一条最短路必是u 点与t t 7 点间沿着基本割集方向g 口路 对于图9 与图1 0 的上边都是( 4 6 1 2 ) 的子图，我们同样将其画成下边的 图来观察，由于边不同的取向，( 4 6 1 2 ) 有两种不同的基本割线段，分别如图 9 与图1 0 左图所示在下边的两个图中，我们也有这样显然的发现：u 与埘 间的一条最短路必是牡点与叫点间沿着基本割集方向g 口路 这里要说明，沿着基本割集方向c 路必是“叫间的最短路，但不一定是 唯一的最短路 接下来我们证明a r c h i m e d e a n 平铺中所有的二进制h a m m i n g 平铺为 ( 6 6 6 ) 、( 4 4 4 4 ) 、( 4 8 8 ) 、( 4 6 1 2 ) 再由引理2 1 1 与引理2 1 3 ，要证明 结论，我们只需证明对这四个平铺( ( 6 6 6 ) 或( 4 4 4 4 ) 或( 4 8 8 ) 或( 4 6 1 2 ) ) 或其子图，我们用g 来表示，对g 中任意一条边删，说明与生成 的子图为g 的凸子图 对于任意一条边删，它所属的基本割集为瓯暂，g 为两个连通的分支 记为a ( c ) 和g ，( c ) ( 如图1 1 所示) ，不妨设让g ( c ) ，有：k 咿= y ( g ( c ) ) ， 因为若存在一点w y ( g ( c ) ) ，但d ，移) k冰、 口 图1 5 ( 4 8 8 ) 的一个子图及其基本割线段 现在用基本割线段的方法来计算g 的w i e n e r 数在图中，我们给出了g 的所有基本割线段，共有四组基本割线段，横向基本割线段g 0 = l ，2 ，n ) 从上到下编号将横向基本割线段旋转9 0 0 即可得到纵向基本割线段，横向的 基本割线段和纵向的基本割线段对g 的w i e n e r 数的贡献相同；斜向基本割 线段有两组，一组为a u = l ，2 ，2 佗一1 ) 从右上角到左下角编号将这组 基本割线段旋转9 0 0 即可得到另一组基本割线段，这两组斜向基本割线段对 g 的w i e n e r 数的贡献也相同 首先通过观察，容易得到g 的顶点数， n ( g ) = 2 n ( n + 1 ) + 2 ( n + 1 ) n = 4 n 2 + 4 n 对横向的任意个基本割线段g = 1 ，n ) ， 佗( g & ) = 3 n + 1 + ( 4 n + 2 ) ( i 一1 ) 第二章a r c h i m e d e a n 平铺与二进制h a m m i n g 图 1 8 则横向割线段对g 的w i e n e r 数的贡献为 m = 佗( 皑) 佗( 晚) q n - 1 = 【3 佗+ l + ( a n + 2 ) i 4 n 2 + 锄一3 n 一1 一( 4 死+ 2 ) 司 i = 0 n - 1 = 【3 n + l + ( 4 佗+ 2 ) i 4 n 2 + n - l 一( 4 n + 2 ) i 1 i - - - - o t l 一1 = ( 3 n 2 + n ) ( 4 n 2 + 礼一1 ) + 2 n ( 2 n 2 一n 一1 ) ( 2 祝+ 1 ) ( n - 1 ) 一( 1 6 n 2 + 1 6 n + 4 ) i 2 i = o = ( 8 3 ) 死5 + ( 2 0 ：3 ) n + 5 n 3 + ( 4 3 ) n 2 + n 3 接下来考虑斜向基本割线段如o = 1 ，2 ，2 n 一1 ) ，观察到a 两侧的 斜向基本割线段关于a 。对称，这两侧的基本割线段对g 的w i e n e r 数的贡 献也相同对4 ( j = l ，2 ，n 一1 ) ，n ( g ) = 4 ( 1 + 2 + + 歹) = n ( g ) 礼( g k ) 山 n l = 2 4 ( 1 + 2 + + 歹) f 4 舻+ 4 n 一4 ( 1 + 2 + + 歹) 】+ ( 2 n 2 + 2 他) 2 = i n - 1n - 1n - 1 = 8 ( 舻一舻) + ( i o n 2 + 1 6 n - 8 ) 2 8 歹4 1 6 歹3 + ( 甜+ 酣+ 群) = ( 5 6 1 5 ) n 5 + ( 1 6 3 ) n 4 一( 8 3 ) n 3 一( 1 6 3 ) n 2 一( i 6 i 5 ) n + ( 4 n 4 十8 佗3 + 4 n 2 ) 因此图g 的w i e n e r 数为 w ( g ) = 2 鹏+ 2 w 2 = ( 6 4 5 ) n 5 + 3 2 n 4 + ( 6 2 3 ) n 3 一( 2 2 1 5 ) n 。 ( 2 ) 接下来我们再给个( 4 8 8 ) 的个子图，类似于a z t e cd i a m o n d 的 构成方式，它是由个正八边形为核，在其周围逐层地国上正八边形所形成的 g ，如图1 6 与图1 7 很容易观察到图 霸的顶点数乃( 坛) = 8 n 2 地中共有四组基本割线段，横向基本割线段a ( i = 1 ，2 ，2 n 一1 ) ， 由上至下编号将横向基本割线段旋转9 0 0l l p , - - j 得到纵向基本割线段，横向的 基本割线段和纵向的基本割线段对m 。的w i e n e r 数的贡献相同；斜向基本 割线段有两组，一组为如o = 1 ，2 ，n ) 由右上角至左下角编号将这组基 第二章a r c h i m e d e a n 平铺与二进制h a m m j n g 图 1 9 o 图1 6 xx 嫘x kx xx 7 蝶 义 图1 7 ( 4 8 8 ) 的个子图 靠及其基本割线段 第二章a r c h i m e d e a n 平铺与二进制h a m m i n g 图 2 0 本割线段旋转9 0 0 即可得到另一组基本割线段，这两组斜向基本割线段对必。 的w i e n e r 数的贡献也相同 首先考虑横向基本割线段，对任意个横向割线段a ( i = 1 ，2 n 一1 ) 。 观察到g 两侧的横向基本割线段关于g 对称，这两侧的基本割线段对必， 的w i e n e r 数的贡献也相同对a 0 = 1 ，n 一1 ) ， 佗( g ) = 4 ( 1 + 3 + + 2 i 1 ) 设这组横向基本割线段对l 死的w i e n e r 数的贡献为w 1 ，则 啊= n ( 皑) 佗( g & ) g n - - 2 = 2 4 ( 1 + 3 + + 2 i + 1 ) 8 n 2 4 ( 1 + 3 + + 2 i + 1 ) 1 + ( 如f ) 2 i = 0 n - - 1n - - 1 = 6 4 n 2 i 2 3 2 i 4 + 1 6 n 4 i = 1i = 1 = ( 6 4 3 ) n 5 3 2 n 4 + ( 3 2 3 ) n 3 一( 3 2 5 ) n 5 + 1 6 n 4 一( 3 2 3 ) n 3 + ( 1 6 1 5 ) n + 1 6 n 4 对任意组斜向基本割线段，取任意个斜向基本割线段4o = l ，n ) ， n ( 四。) = 4 n y ，设这组斜向基本割线段对 厶的w i e n e r 数的贡献为w ；， 则 2 - - 1 w 2 = n ( 吼) 礼( g 乞) = 4 n j ( s n 2 - 4 n j ) a jj = l 2 n - - 1 = 1 6 n 3 ( 4 n 2 - 2 n ) 一1 6 n 2 歹2 j = x = ( 6 4 3 ) n 5 一( 1 6 3 ) n 3 因此图地的w i e n e r 数为 ( 坛) = 2 w , + 2 = ( 1 0 8 s 1 5 ) n 5 一( 3 2 3 ) n 3 + ( 3 2 1 5 ) n ( 3 ) 最后我们给出( 4 6 1 2 ) 的一个最简单的子图g 的w i e n e r 数，如图 1 8 g 是一线性链，设含有n 个正十二边形很容易算出，n = 1 时，w ( v ) = 2 3 0 4 ；n = 2 时，w ( g ) = 1 1 5 5 6 ；佗= 3 时，w ( g ) = 2 9 0 5 2 ；n = 4 时， w ( v ) = 7 0 0 2 0 下面一般的，我们考虑当n 5 的情况 第二章a r c h i m e d e a a 平铺与二进制h a m m i n g 图 2 1 g 图1 8 ( 4 6 1 2 ) 的一个子图 容易观察到图g 中顶点为6 + 4 ( n 一1 ) 个正六边形的顶点，所以 竹( g ) = 3 6 + 2 4 ( n 一1 ) = 2 4 n + 1 2 c 图g 有四类基本割线段，如图中所示：横向基本割线段c ，他( g 吕) = 1 2 n + 6 ，设其对图g 的w i e n e r 数的贡献为w 1 ；纵向基本割线段h k ( k = 1 ，2 ，2 亿+ 1 ) ，他( g 备。) = 6 + 1 2 k ，设其对图g 的w i e n e r 数的贡献为 w 2 ；斜向基本割线段有两类，一类为4 与a ；0 = 1 ，2 ，n ) ，a ；可由a t 旋转一定角度得到，它们对图g 的w i e n e r 数的贡献相同对于任意的a f ， 钆( g 冀。) = 1 8 + 2 4 j ，设其中一组对图g 的w i e n e r 数的贡献为w 3 ；另一类 斜向基本割线段为g 与qa = 1 ，2 ，扎+ 2 ) ，可由g 旋转一定角度 得到，它们对图g 的w i e n e r 数的贡献相同，设其中一组对图g 的w i e n e r 数的贡献为w 4 由图中观察演算得 w 1 = ( 1 2 n + 6 ) 2 = 1 4 4 n 2 + 1 4 4 n + 3 6 ， w 2 = n ( 嚷) 礼( g k ) 风 2 n = 6 ( 2 4 n + 1 2 - 6 ) + ( 6 + 1 2 k ) ( 2 4 n + 1 2 - 6 - 1 2 k ) k = o = 1 9 2 n s + 2 8 8 n 2 + 1 6 8 n + 3 6 ， 第二章a r c h i m e d e a n 平铺与二进制h a m m i n g 图 2 2 = n ( 吼) 佗( g 乞) 山 n - 1 = = ( 1 8 + 2 4 j ) ( 2 4 n + 1 2 1 8 2 4 j ) j = o ：1 9 2 n s + 2 8 8 n 2 + 1 6 8 n ， w 4 = 佗( 哓) 佗( 眙) g = 1 2 ( 2 4 n + 1 2 6 ) + 4 2 ( 2 4 n + 1 2 2 1 ) + 8 4 ( 2 4 , l + 1 2 4 2 ) n - 4 + ( 4 2 + 2 4 呻锄+ 1 2 - 4 2 2 缸) i = 1 = 9 6 护+ 1 4 4 n 2 + 5 1 6 n 一9 0 所以图g 的w i e n e r 数为 w ( a ) = m + w 2 + 2 w 3 + 2 w 4 = 5 7 6 n a + 1 0 0 8 n 2 + 1 5 1 2 n 一1 0 8 第三章广义四角链关于w i e n e r 数的极链的结论 2 3 第三章广义四角链关于w i e n e r 数的极链的结论 上一章我们知道对所有二进制h a m m i n g 平铺及其子图，我们都 可以用基本割集的方法来计算其w i e n e r 数在先前的文章中【2 6 】， y a n q i uz e n g 和f u j iz h a n g 研究了四角链的关于k - 匹配数和k - 独立集 数的极链在本章中，在这一章里，我们重点研究了广义四角链 由于六角链关于w i e n e r 数的极链的结论【3 2 】很自然的想象认为在广 义四角链中：线性链l n 是w i e n e r 数最大的，而w i e n e r 数最小的广 义螺旋状的，但我们的精确分析表明在n 为偶数时，w i e n e r 数最小 的广义四角链并不完全