厦门大学硕士学位论文有相同距离分布的图姓名：邱秀亮申请学位级别：硕士专业：应用数学指导教师：郭晓峰20070501有相同距离分布的图摘要本文研究了图的Ｗｉｅｎｅｒ指数Ⅳ，超．Ｗｉｅｎｅｒ指数 ⅣⅣ，Ｗｉｅｎｅｒ向量ｗｙ，超．Ｗｉｅｎｅｒ向量日Ⅳｙ，Ｗｉｅｎｅｒ多项式日，超．Ｗｉｅｎｅｒ多项式日日和距离分布ＤＤ之间的关系．对于任两个连通图Ｇ和Ｇ．，证明了如下五个命题等价：（１）ＤＤ（Ｇ）＝ＤＤ（Ｇ＋）（２）ＷＶ（Ｇ）＝ＷＶ（Ｏ‘）（３）ＨＷＶ（Ｇ）＝ＨＷＶ（Ｇ’） （４）Ｈ（Ｇ）＝Ｈ（Ｇ＋）（５）ＨＨ（Ｇ）＝ＨＨ（Ｇ‘）． 如果Ｇ和Ｇ．有相同的距离分布，那么它们有相同的Ｗｉｅｎｅｒ数矽和超．Ｗｉｅｎｅｒ数ｗⅣ，反之则不然．进而，我们研究了具有相同距离分布的图，给出了这类图的几种构造方法，并证明了对于具有ｎ个顶点和仇条边的任两个图，如果（仃ｉ１）＜ｍ＜（；），则它们具有相同的距离分布．我们也给出了最小的具有相同距离分布的图．关键词：距离分布；距离矩阵；Ｗｉｅｎｅｒ向量；超．Ｗｉｅｎｅｒ向量．有相同距离分布的图ＡｂｓｔｒａｃｔＩｎ ｔｈｅ ｐｒｅｓｅｎｔ ｐａｐｅｒ ｗｅ ｉｎｖｅｓｔｉｇａｔｅ ｔｈｅ ｒｅｌａｔｉｏｎｓｈｉｐ ｂｅｔｗｅｅｎＷｉｅｎｅｒ ｎｕｍ－琏ｂｅｒＷ，ｈｙｐｅｒ－Ｗｉｅｎｅｒ ｍｕｎｂｅｒⅣⅣ，Ｗｉｅｎｅｒ ｖｅｃｔｏｒｓⅣｙ，ｈｙｐｅｒ－ＷｉｅｎｅｒｖｅｃｔｏｒｓＨｗｖＩＷｉｅｎｅｒｐｏｌｙｎｏｍｉａｌ ＨＩｈｙｐｅｒ－Ｗｉｅｎｅｒ ｐｏｌｙｎｏｍｉａｌＨＨ ａｎｄｄｉｓｔａｎｃｅ ｄｉｓｔｒｉｂｕｔｉｏｎ ＤＤ．Ｉｔ ｉｓ ｓｈｏｗｅｄ ｔｈａｔ，ｆｏｒ ｃｏｎｎｅｃｔｅｄ ｇｒａｐｈｓ Ｇ ａｎｄＧ。
ｔｈｅｆｏｌｌｏｗｉｎｇ ｃｏｎｃｌｕｓｉｏｎｓａｒｅｅｑｕｉｖａｌｅｎｔ：（１）ＤＤ（Ｇ）＝ＤＤ（Ｇ’）（２）ＷＶ（Ｇ）＝ＷＶ（Ｇ３）ＨＷＶ（Ｇ）＝ＨＷＶ（Ｇ＋）（４）Ｈ（Ｇ）＝Ｈ（Ｇ＋）（５）ＨＨ（Ｇ）＝日日（伊）．ａｎｄ ｉｆ Ｇ ａｎｄ Ｇ４ ｈａｖｅｓａｌｎｅｄｉｓｔａｎｃｅ ｄｉｓｔｒｉｂｕｔｉｏｎ ＤＤ，ｔｈｅｎ ｔｈｅｙ ｈａｖｅｓａｉｎｅＷ ａｎｄ ＷⅣ．Ｔｈｅｒｅｆｏｒｅ，ｗｅｃｏｎｓｉｄｅｒ ｔｈｅＦ印ｈｓｗｉｔｈｓａｌｎ ｅｄｉｓｔａｎｃｅｄｉｓｔｒｉｂｕｔｉｏｎ．Ｓｅｖｅｒａｌ ｃｏｎｓｔｒｕｃｔｉｏｎ ｍｅｔｈｏｄｓ ｆｏｒ ｆｉｎｄｉｎｇａｃｌａｓｓ ｏｆ ｇｒａｐｈｓｗｉｔｈｓａｌｎｅｄｉｓｔａｎｃｅ ｄｉｓｔｒｉｂｕｔｉｏｎａｒｅｇｉｖｅｎ．Ｆｕｒｔｈｅｒｍｏｒｅ，ｉｔ ｉｓ ｐｒｏｖｅｄ ｔｈａｔ，ｆｏｒａｌｌｃｏｎｎｅｃｔｅｄ ｇｒａｐｈｓ ｗｉｔｈｎｖｅｒｔｉｃｅｓａｎｄ １７１ｅｄｇｅｓ，ｉｆ（ｎｉｌ）＜ｍ＜（；），ｔｈｅｎｔｈｅｙ ｈａｖｅ ｔｈｅｓａｉｎｅｄｉｓｔａｎｃｅ ｄｉｓｔｒｉｂｕｔｉｏｎ．Ｗｅ ａｌｓｏ ｇｉｖｅ ｔｈｅ ｓｍａｌｌｅｓｔ ｇｒａｐｈｓｗｉｔｈｓａｎｌｅｄｉｓｔａｎｃｅ ｄｉｓｔｒｉｂｕｔｉｏｎ．Ｋｅｙｗｏｒｄｓ：Ｄｉｓｔａｎｃｅｄｉｓｔｒｉｂｕｔｉｏｎ；ｄｉｓｔａｎｃｅ ｍａｔｒｉｘ；Ｗｉｅｎｅｒ ｖｅｃｔｏｒ；ｈｙｐｅｒ－Ｗｉｅｎｅｒｖｅｃｔｏｒ．歼奄 象厦门大学学位论文原创性声明兹呈交的学位论文，是本人在导师指导下独立完成的研究成果．本人在论文写作中参考的其它个人或集体的研究成果，均在文中以明确方式标明．本人依法享有和承担由此论文而产生的权利和责任．伽他 镰獬名年人名 月引，一导师 辚夥影三厦门大学学位论文著作权使用声明本人完全了解厦门大学有关保留、使用学位论文的规定．厦门大学有权保留并向国家主管部门或其指定机构送交论文的纸质版和电子版，有权将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆被查阅，有权将学位论文的内容编入有关数据库进行检索，有权将学位论文的标题和摘要汇编出版．保密的学位论文在解密后适用本规定．篡签名奄豳彳嗍２车歹移罗日有相同距离分布的图第一章引言图论的产生和发展经历了二百多年的历史．著名数学家Ｌ．Ｅｕｌｅｒ在１７３６年发表了“哥尼斯堡七桥问题竹的论文以来，图论研究从早期的迷宫问题、游戏问题、博弈问题、棋盘上马的行走线路问题等发展到著名的四色问题（１８５２年）和Ｈａｍｉｌｔｏｎ环游世界问题（１８５６年）， 同时也出现了以图论为工具去解决其它领域的问题的成果．１８４７年德国的克希霍夫（Ｇ．Ｒ．Ｋｉｒｃｈｏｆｆ）将树的概念和理论应用于工程技术的电网络方程组的研究．１８５７年英国的凯莱（Ａ．Ｃａｙｌｅｙ）也独立地提出了树的概念，并应用于有机化合物的同分异构物计数的研究中．二十世纪三十年代以来，由于生产管理、军事、交通运输、计算机和通讯网络、化学、物理、分子生物学、经济管理等领域的实际需要产生了大量的与图论有关的问题，大大促进了图论的发展．目前图论在统计物理、理论化学和量子化学，分子生物学、运筹学、计算机科学、电子学，信息论，控制论、网络理论、社会科学及经济管理等几乎所有学科领域都有广泛应用．二十世纪化学家们为了研究分子结构与其化学性质（如稳定性。
沸点等）之间的关系，纷纷引入了许多与分子的拓扑结构密切相关的分子拓扑指数，其中最重要的、应用最广的就是Ｗｉｅｎｅｒ指数ｗ【ｌ】、Ｈｏｓｏｙａｔｏｐｏｌｏｇｉｃａｌ指数Ｚ【２】２和Ｃｏｎｎｅｃｔｉｖｉｔｙ指数ｘ【３】．Ｗｉｅｎｅｒ指数最初是由Ｈａｒｏｌｄ Ｗｉｅｎｅｒ［１１在１９４７年为了确定烷烃的沸点而引入的—个分子拓扑指数．设Ｇ是—个图，则Ｇ的Ｗｉｅｎｅｒ指数定义如下；・，’ ‘ｗ＝渺（Ｇ）＝∑地ｔ『），｛＂，ｔ，）∈ｙ（Ｇ）其中ｄ（让，ｔ，）表示图Ｇ中顶点ｔＩ和”之间的距离．在…１中，ＨａｒｏｌｄＷｉｅｎｅｒ指出高阶烷烃的沸点（Ｂ．Ｐ．）与Ｗｉｅｎｅｒ数之间存在着线性关系：Ｂ．Ｐ．≈ａＷ＋ｂｗｓ＋ｃ舻姒∽２白丽丽’有相同距离分布的图其中，口，ｂ，ｃ为实验常数，ｗ为分子图的Ｗｉｅｎｅｒ数，蚴是分子图中所含的只（长为３的路）的数目．Ｈａｒｏｌｄ Ｗｉｅｎｅｒ最初给Ⅳ所下的定义是无圈烷烃中各对碳原子（顶点）之间的键数（边数）之和．在１９７１年，Ｈｏｓｏｙａ【２】证明了ｗ等于分子图的距离矩阵的各元素之和的一半．这样，Ｗｉｅｎｅｒ数的定义就自然地被推广到了含圈图的情形．２Ｈｏｓｏｙａｔｏｐｏｌｏｇｉｃａｌ指数ｚ是日本化学家Ｈｏｓｏｙａ于１９７１年提出，定义如下：ｚ＝ｚ（Ｇ）＝∑Ｐ（ａ，后），ｋ＝０这里Ｐ（Ｇ，七）表示图Ｇ的不同ｋ匹配的数目．Ｈｏｓｏｙａ ｔｏｐｏｌｏｇｉｃａｌ指数不仅在化学上，而且在物理学及数学上都得到了广泛的应用与研究．文献【４，５】包含了关于Ｈｏｓｏｙａ指数的一些极值问题的结论．Ｃｏｎｎｅｃｔｉｖｉｔｙ指数ｘ是Ｒａｎｄｉｅ于１９７５年提出的，定义如下：，一、弋—、Ｕ．廿 Ｙ。
， 、 ，１一这里ｄ（ｕ）表示图Ｇ中顶点ｕ的度，和式指对所有图Ｇ中所有相邻的顶点对取和．人们对这三个指数有着相当多的研究，其中有着最重要和最广泛应用的就是Ｗｉｅｎｅｒ指数Ｗ，Ｗｉｅｎｅｒ指数可度量碳原子骨架图的分支的扩展，而且常常用来测定分子的体积／表面积之比．在非平面分子结构（特别是碳水化合物）的情况下，Ｗｉｅｎｅｒ指数与分子内吸引力直接相关．那些依赖于分子的体积／表面积之比和（或者）碳原子骨架的分支的内容的物理和化学性质常常与Ｗｉｅｎｅｒ指数密切相关．其中有；液体的密度和克分子体积、汽化热、分子的原子化热和生成热、结构热、原子热、同分异构、蒸发性、密度、沸点、临界压、克分子折射率和分子极化率、水分解度、表面张力、粘度指数、声速、色谱保留时间、高温超导体的临界温度等．Ｗｉｅｎｅｒ指数近几年的一些应用是有关氯苯衍生物的电解原理【６】，正辛醇和水的分配系数【７】，同分异构系【８】，以及分子的构效关系【９】．Ｗｉｅｎｅｒ指有相同距离分布的图数ｗ在化学上的意义是分子中所有碳原子之间的总距离，而在计算 时我们常用公式 Ｗ＝∑Ⅳ（ｅ）ｅ 来表示，这里ｅ是指所有连接碳原子的键，Ｗ（ｅ）是指ｅ两边碳原子个数的乘积．显然，这个总距离越小，分子的紧密度就越大，因此ｗ总是与分子的大小密切相关的量．Ｍｏｔｏｃ和Ｂａｌａｂａｕ在【１０】中证明了ｗ的值９０％反映了分子的大小．Ｈｏｓｏｙａ指数ｚ是计算图中所有匹配的数目．Ｈｏｓｏｙａ［１１】发现 了计 算ｚ的一个递归方法，它可以表示成３．Ｚ（Ｇ）＝Ｚ（Ｇ—ｅ）＋ｚ（ａ—ｅｅ）这里Ｇ－ｅ是指图Ｇ中删去一条边ｅ所得的图，Ｇ．ｅｅ是指Ｇ中删去 边ｅ以及和它所有相连的边所得的图，这个递归方法可以把一个很大的分子分解成很多小的部分．设ｅ是树Ｔ的一条边．我们用ｋ（ｅ）表示Ｔ—ｅ时每一部分顶点 个数的乘积，用ｂ【ｅ】表示Ｔ—ｕ，ｕ后各部分顶点个数的乘积，这里钍，ｔ，是边ｅ的两个端点．对任意的树Ｔ，Ｍ．Ｒａｎｄｉｃ引入了一个新的拓扑指数一Ｗｉｅｎｅｒ－Ｈｏｓｏｙａ指数（Ｗ一日）【ｌ２】，它可以定义为Ｗ—Ｈ（Ｔ）＝∑旧（ｅ）＋ｂ【ｅ】），拢Ｅ（Ｔ）如果ｅ是悬挂边，那么ｈｉｅ］定义为０．正如Ｒａｎｄｉｃ他自己指出的那 样，Ｗｉｅｎｅｒ－Ｈｏｓｏｙａ指数能够用上面的递归方法来计算，Ⅳ一Ｈ（Ｇ）＝ｗ（ａ—ｅ）＋ｗ（ａ—ｅｅ）．这样我们可以用Ｗｉｅｎｅｒ指数ｗ去计算Ｗｉｅｎｅｒ．Ｈｏｓｏｙａ指数ｗ一 日． Ｗｉｅｎｅｒ－Ｈｏｓｏｙａ指数比很多简单的拓扑指数能更准确地描述庚烷、辛烷和癸烷等的同分异构体的性质特征【１３】．自Ｗｉｅｎｅｒ提出第一个拓扑指数Ｗｉｅｎｅｒ数ｗ以来，现已引入了约４００个分子拓扑指数，它们在分子结构的量子结构性质关系／量子结构活性关系（ＱＳＰＲ／ＱＳＡＲ）研究中发挥了重要作用．一有相同距离分布的图４Ｒａｎｄｉｅｆ１４１对树的Ｗｉｅｎｅｒ数进行了推广，引入了超一Ｗｉｅｎｅｒ数．超一Ｗｉｅｎｅｒ数现已成为许多研究者深入研究的拓扑指数之一【１５－２０］．在【２１，２２】中Ｒａｎｄｉｅ和郭晓峰等人进一步引入了树的高阶Ｗｉｅｎｅｒ数和Ｗｉｅｎｅｒ矩阵不变量等概念，而Ｋｌｅｉｎ等人【１５】则把超．Ｗｉｅｎｅｒ数推广到了所有的连通图，他们定义连通图的超．Ｗｉｅｎｅｒ数为：ＷＷ＝ＷＷ（Ｇ）＝去∑（ｄ ２（ｔ‘，可）＋ｄ（ｔ‘，ｔ，））． 。
Ｉ口，付｝互ｙ（Ｇ）进而，Ｋｌｅｉｎ和Ｇｕｔｍａｎ等人【２３，２４】给出了Ｗｉｅｎｅｒ数和 超．Ｗｉｅｎｅｒ 数之间的关系：ＷＷ（Ｇ）＝去Ⅳ（Ｇ）＋去％（Ｇ），其中ｗ（Ｇ）＝∑㈣｝￡ｙ（Ｇ）ｄ（ｕ，ｔ，），％（Ｇ）＝∑脚｝Ｃｙ（Ｇ）ｄ ２（ｔ‘，钉）．而对 于树Ｔ而言，有更具体的关系式：ＷＷ（Ｔ）＝≥ｗ（Ｔ）一三∑【Ⅳ（丑（ｅ））＋Ⅳ（正（ｅ））】， Ｃ这里绍为Ｔ的顶点数，ｅ为Ｔ的边，Ｔｌ（ｅ）和Ｔ２（ｅ）是ｒ删去ｅ后所 得的两个分支．图的距离分布（ｄ（ａ，１），ｄ（Ｇ，２），…，ｄ（ａ，Ｄ））是由Ｂｕｃｋｌｅｙ和ＳｕｐｅｒｖｉＵｅ于１９８１年提出的【２５】．这里ｄ（Ｇ，ｋ）表示图Ｇ中距离为ｋ的顶点对的数目．在１９８８年，Ｈｏｓｏｙａ【２６】引入了图的Ｗｉｅｎｅｒ多项式，定义如下ｄ Ｈ＝Ｈ（Ｇ，＝∑ｄ（Ｇ，七）矿ｋ＝ｌ这里ｄ表示图Ｇ的直径，ｄ（Ｇ，ｋ）表示图Ｇ中距离为ｋ的顶点对的 数目．在【２７】中，Ｃａｓｈ引入了一个新的超．Ｗｉｅｎｅｒ多项式的概念：‘日Ｈ＝ＨＨ（Ｇ，ｚ）：∑Ｄ掣ｄ（Ｇ，七）扩，ｋ＝０这里ｋ，Ｄ，ｄ（Ｇ，ｋ）和上面Ｈ（Ｇ，ｚ）定义中表示的意思一样．在这篇文章里，Ｃａｓｈ还给出了Ｗｉｅｎｅｒ多项式和超一Ｗｉｅｎｅｒ多项式及超一Ｗｉｅｎｅｒ有相同距离分布的图数和超一Ｗｉｅｎｅｒ多项式之间的关系：ｗｗ（ｃ，）＝ＨＨ７（Ｇ，１）ＨＨ（Ｇ，加／（趴Ｇ，卅扣，，（Ｇ，ｚ））如Ｗｉｅｎｅｒ数和Ｗｉｅｎｅｒ多项式之间的关系由Ｇｕｔｍａｎ等人【２８】给出：Ｗ（Ｇ）＝Ｈ’（Ｇ，１）最近，郭晓峰等人把高阶Ｗｉｅｎｅｒ数的概念推广到了所有的 连通图ｆ２９】，同时引入了图的Ｗｉｅｎｅｒ向量，超．Ｗｉｅｎｅｒ向量，Ｗｉｅｎｅｒ矩阵序列，超一Ｗｉｅｎｅｒ矩阵，Ｗｉｅｎｅｒ多项式序列和赋权的超．Ｗｉｅｎｅｒ多项。