ABC相关指标与图的不变量关系研究

摘要

图论逐渐成为计算机科学、组合优化等学科的基础与支柱.如今,随机图论、代数图论、算法图论等都是图论的分支.这些分支的出现,丰富了图论的研究内容,拓展了图论的研究方法.实际上,在流体动力学、信息、电信、交通中,都在应用图论的相关知识进行着分析和研究的工作.另外,图论的广泛应用背景还体现在化学中．经过一段时间的研究,科学家们发现很多化合物的物理、化学性质与其拓扑性质存在着一定的联系,如：沸点、水溶性、分子体积和表面积、能量水平、电子分布等. 拓扑指标在物理化学领域具有很多好的性质.基于度的指标之间的关系是显然的并且有很多这方面的研究成果.另一方面，考虑基于度和基于距离的指标之间的关系，这是一个有价值的问题.特别地，直径是基于距离的不变量，研究了图的ABC相关指标和直径的关系. 图G的ABC2指标是指ABC2(G)=∑uv∈E(G)√nu+nv-2/nu·nv，其中nu是指V(G)中到顶点u的距离小于到顶点v的距离的顶点个数.首先,本文应用一个新的变换，对文献[1]中的定理作出了更简短的证明；其次，通过相同的变换，得到树的A BC指标的第二大和第二小值. 全文共分为六个部分. 第一部分简单介绍了ABC相关指标的研究背景，定义和现状. 第二部分给出了文章涉及的概念，符号和定理. 第三部分得出了树的ABC2指标的最大、第二大、最小、第二小值，并且给出了相应的最值图. 第四部分讨论了在树和单圈图中，ABC相关指标与直径的关系，得到了指标和直径差值的下界. 第五部分对本文的主要工作进行了总结并展望未来.

目录

声明

第1章 前言

1.1 研究背景与现状

1.2 论文结构及研究的主要内容

第2章 预备知识

2.2 图的ABC指标及ABC2指标

第3章 树的A BC 2指标的最值问题

3.2 树的ABC2指标的最小、第二小值

第4章 ABC相关指标与图的直径的关系

4.1 ABC相关指标与树的直径

4.2 ABC相关指标与单圈图的直径

第5章 结束语

参考文献

攻读硕士期间所发表论文

致谢