树和若干多环化合物分子图的子树数与BC子树数的广义计算及拓扑特性研究

The subtree number and block cut-vertex (BC) subtree number of graphs are two very important structural topological indices, which have great significance for the discovery, screening and synthesis of lead compounds, since the existing computing methods cannot establish generalized correlation with the distance based indices, which makes the multi-dimensional cross correlation analysis of topological properties become a difficult issue. This project will study the generalized computing and topological properties of the subtree and BC subtree number of tree and various molecular graphs of polycyclic compounds (especially important carcinogenic aromatic hydrocarbons in PM2.5 and related cata-condensed and peri-condensed structures) : 1) constructing the generalized computing algorithms of these two indices of tree through introducing combinatorial matrix theory, and then comprehensively investigating the relationship between these two indices and the distance based indices by means of employing matrix as the bridge; 2) studying the extremal values and structures of tree with respect to the BC subtree number under restricted parameters of: fixed number of vertices, and degree sequence, maximal degree, leaf number, independent set number, matching number, respectively, based on transfer and recombination of substructures; 3) Taking advantage of the characteristic graph, we study the generalized computing algorithms of these two indices of the above mentioned various molecular graphs of polycyclic compounds, and the relationship among kink transformation, parity segments, and these two indices of general cata-condensed aromatic compounds. The above research results will provide a new perspective for the prediction and inference of the multi-dimensional structural properties of the polycyclic compounds, especially the polycyclic carcinogenic aromatic hydrocarbons.

图的子树数和块割点（BC）子树数是两项重要的结构型拓扑指标，对先导化合物的发现、筛选与合成等有重要的意义，由于其现有的计算方法无法与距离型指标间建立广义关联，这使得对图拓扑特性的多维交叉分析成为一个难题。本项目拟对树和若干多环化合物（尤其是PM2.5中的重要致癌芳烃类及相关渺位和迫位缩合结构）分子图的子树数与BC子树数的广义计算及拓扑特性进行研究：1)引入组合矩阵论构造树的这两项指标的广义计算算法，以矩阵为桥梁融合研究这两项指标与距离型指标的关系；2)基于子结构迁移组合，研究固定顶点数且度序列、最大度、叶子数、独立集数和匹配数等参数下树的BC子树数指标的极值和极图结构；3)基于特征图构造若干多环化合物分子图的这两项指标的广义计算算法，研究渺位缩合芳环分子图的扭结变换、奇偶片段同这两项指标间的关系。上述研究成果将为预测和推理多环化合物特别是多环芳烃类致癌物分子的多维结构特性提供新角度解析。

通过项目组成员的共同努力，基本完成本项目的研究任务。首先，利用矩阵论、图论和代数理论，设计出了对应于树的子树数、辅助子树数和BC子树数计算的矩阵变换，实现了树的对应子树信息的无丢失“传递”，构造出了基于矩阵运算的树的子树数与BC子树数的广义计算算法。进一步地，搭建起结构型的子树数与BC子树数指标同距离型指标（如，Wiener 指标）间的关联桥梁。其次，构造并证明了引起子树数指标、BC子树数指标规则增减的子结构迁移重组变换规则，推导出了若干图类在若干限定参数下关于子树数指标、BC子树数指标及相关联的ABC指标的极值和极图结构。接着，利用生成函数和结构分析，给出了随机六元素螺链图、聚苯六角链图、六角形链图和亚苯基链图的含概率变量的平均子树数的递归公式，推导出了对应的随机链图的子树数指标及相关特性，同时将对应的六环推广到了n圈。最后，为了研究若干多环化合物分子图的子树数与BC子树数指标的广义计算算法，通过构造辅助结构以及带权路径收缩的方法，我们前期研究与其结构相关的三圈图的子树数的计数算法。更进一步地，通过推广叶子间距离的约束，提出新的图的“多叶距粒度”结构型α-子树（至少含α+1个顶点，且任意两片叶子间的距离均为α(≤d)的整数倍，d为图的最长路径的距离）的概念。通过定义并构造新的基于叶距的正则α-子树的α+1元生成函数及辅助子树的α类多叶距权重，同时构造叶子向其父亲节点传递α类多叶距权重的规则，从而保证了基于叶距的正则α-子树信息的无丢失传递，解决了树的基于叶距的正则α-子树的枚举计算问题。在此基础上，再利用带权路径收缩的方法，给出了单圈图和双圈图（与化合物接近的圈图）的α-子树的计数算法。上述研究成果从一个全新的结构型拓扑度量预测和推理了树网及多环化合物特别是多环芳烃类致癌物分子的结构特性。