Azam Naveed Ahmed, Shurbevski Aleksandar, Nagamochi Hiroshi
Department of Applied Mathematics and Physics, Kyoto University, Kyoto 606-850, Japan.
Entropy (Basel). 2020 Nov 13;22(11):1295. doi: 10.3390/e22111295.
Cycle rank is an important notion that is widely used to classify, understand, and discover new chemical compounds. We propose a method to enumerate all non-isomorphic tree-like graphs of a given cycle rank with self-loops and no multiple edges. To achieve this, we develop an algorithm to enumerate all non-isomorphic rooted graphs with the required constraints. The idea of our method is to define a canonical representation of rooted graphs and enumerate all non-isomorphic graphs by generating the canonical representation of rooted graphs. An important feature of our method is that for an integer n≥1, it generates all required graphs with vertices in O(n) time per graph and O(n) space in total, without generating invalid intermediate structures. We performed some experiments to enumerate graphs with a given cycle rank from which it is evident that our method is efficient. As an application of our method, we can generate tree-like polymer topologies of a given cycle rank with self-loops and no multiple edges.
圈秩是一个重要概念，被广泛用于对新的化合物进行分类、理解和发现。我们提出了一种方法，用于枚举具有给定圈秩且带有自环且无多重边的所有非同构树状图。为实现这一目标，我们开发了一种算法来枚举具有所需约束的所有非同构有根图。我们方法的思路是定义有根图的规范表示，并通过生成有根图的规范表示来枚举所有非同构图。我们方法的一个重要特点是，对于整数n≥1，它能以每个图O(n)的时间和总共O(n)的空间生成所有具有n个顶点的所需图，而无需生成无效的中间结构。我们进行了一些实验来枚举具有给定圈秩的图，从中可以明显看出我们的方法是高效的。作为我们方法的一个应用，我们可以生成具有给定圈秩且带有自环且无多重边的树状聚合物拓扑结构。
