Computational techniques for vertex partitioning of graphs.
Computational techniques for vertex partitioning of graphs.
复制标题
图的顶点划分的计算技术。
DOI：
10.1021/ci00067a009
复制
发表时间：
1990
期刊：
影响因子：
--
通讯作者：
Munk,ME
中科院分区：
文献类型：
--
作者：
Liu,XY;Balasubramanian,K;Munk,ME
近年来，图-点-自同构划分问题受到了广泛的关注。1“12由于顶点划分有许多实际应用，因此具有重要的意义。首先，它为计算机感知分子隐藏的拓扑对称性提供了一种解决方案。在我们的团队中，我们一直对建立一个全面的计算机辅助结构阐明系统感兴趣。在这项工作中遇到的一个关键问题是，给定一个分子的邻接表(相当于邻接矩阵)，能否编写一个自动算法和代码来产生它的拓扑对称性。图的顶点划分问题在分子的~(13)C和质子核磁共振信号及其强度模式的计算机生成中也有重要的应用。我们已经在早期的手稿中描述了顶点划分在生成L3C核磁共振谱中的应用。早期的一些生成图的顶点划分的技术是基于Morgan算法的。1“5和主特征向量法。Randic和他的合作者10提出了规范的顶点标记法来生成图的顶点自同构划分。虽然其中许多算法和基于这些算法的代码使用起来很简单，但它们往往会导致收敛问题和振荡行为。赫恩登和他的同事-
The graph-vertex-automorphism partitioning problem has received considerable attention in recent years. 1" 12 The vertex partitioning is of fundamental interest since it has many practical applications. First and foremost of all, it provides a solution for computer perception of the hidden topological symmetry of a molecule. In our group we have been interested in building a comprehensive computer-assisted structure-elucidation system. 11, 12 A critical problem encountered in this work is that given the neighborhood table (equivalently the adjacency matrix) of a molecule, can an automated algorithm and code be written to yield its topological symmetry. The graph-vertex-partitioning problem also finds important application in the computer generation of 13C and protonNMR signals of molecules and their intensity patterns. We have described in an earlier manuscript the application of the vertex partitioning to generate l3C NMR spectra. 24 Some early techniques for generatingvertex partitioning of graphs have been based on the Morgan algorithm. 1" 5 and the principal eigenvector algorithm. Randic and co-workers10 have formulated the canonical vertex-labeling methodto generate the vertex-automorphism partitionings of graphs. Although many of these algorithms and the codes based on these al-gorithms are simple to use, they often leadto convergence problems and oscillatory behaviors. Herndon and co-work-