图的结构与子结构理论

The substructure theory of graphs is an important research branch of graph structure theory. It synthetically uses algebra, algorithm, probability and statistics. The substructure theory of graphs is mainly to study the intrinsic relation between the substructure (for example, subtrees, support trees, forests etc) and the topological structure parameters (including diameter, degree sequence, connected number, matching, independent number etc ) of graphs itself. The main contents of this project are three aspects: 1. The number of subtrees (local or global) in a graph and the depiction of extreme graphs, then the distribution of the number of subtrees in a graph with order; 2. The intrinsic qualitative relationship between the average vertex number and density of subtrees in a graph and the structure of a graph is described quantitatively, and the structure of the extremal graph is further characterized. 3. The generation functions of substructure parameters are derived by Tutte polynomial、matrix and structure analysis. The structure and algorithm of extreme graphs are determined. The research results of this project include substructure theory of graph and extreme value graph theory. The new ideas and methods will develop and perfect the mathematical theory foundation and graph theory research mathematical method, which will be helpful to the estimation and prediction of network performance and the construction of network model in practical problems.

图的子结构理论是图结构理论的一个重要研究分支，它是综合采用代数、算法、概率、统计、图论和组合等方法和技巧进行研究的交叉领域。图的子结构理论主要研究子结构(子树、支撑树、生成森林等)与图自身的拓扑结构参数（直径、度序列、连通度、匹配数、独立数、染色数等）之间的内在关联。本项目主要研究三个方面的内容：1.图中子树（局部或整体）的个数及极值图刻画，进而研究图中子树个数随阶数的变化其分布规律；2.图中子树平均顶点数和密度与图的结构之间的内在定性关系并进行定量刻画，进一步刻画其极值图结构；3.用Tutte多项式、矩阵以及结构分析等方法推导子结构参数的生成函数，确定极值图结构和算法。本项目的研究成果包括图的子结构理论与极值图理论，提出的研究新思路和新方法将发展和完善数学理论基础和图论研究的数学方法，对实际问题中的网络性能的估算与预测以及网络模型构造具有启示和借鉴作用。

对图中子树（局部或整体）的个数及极值图刻画，进而研究图的子结构与结构的关系。其中包括若干限定参数下树的关于子树数指标、BC 子树数指标，引入随机概率变量并利用结构分析的方法给出随机六元素螺链图、聚苯六角链图、六角形链图和亚苯基链图的平均子树数的递归公式，推导出对应的随机链图的子树数指标，及其指标间的关系，它们各自的子树数指标的平均值。通过研究图的 Wiener指标、Steiner Wiener指标等图的不变量的极值问题，进一步探索图的不变量与图的结构之间的密切关系。另外图的不同的谱参数与包含禁入子图的图类的拓扑结构性质之间的关系，并推广到超图的不同的谱参数与超图的结构、性质之间的关系开展研究。图中子树平均顶点数和密度与图的结构之间的内在定性关系并进行定量刻画，进一步刻画其极值图结构，利用结构分析等方法推导子结构参数的生成函数，确定极值图结构和算法。对图的Ramse图和Wenger图研究，得到极值情形并推广已有结果。