图同构判定的新方法

A New Method for Determining the Isomorphism between Two Graphs

图的同构问题由来已久,并且它的应用十分广泛。例如:确定一个图的自同构群的构造的问题和它有紧密联系;在有机化学上我们可以利用图的同构判定方法来确定同分异构物。因此,寻求图同构的判定方法是一项引人入胜的工作。提出了一个新的判定方法(定理1)可以方便的确定两个图是否同构。此外,还得到了某一类图的同构判定的一个较强的条件(定理2)。

The problem of the isomorphism proving two graphs has a long history, and it has many applications——for example, determining the automorphism group of a graph, which is one of the focus problems in algebraic graph theory, is closely related to this, on the other hand, chemists can tabulate all molecules in a certain class by this theory. For this,looking for the way to decide whether two graphs are isomorphic is a nontrivial task. In this paper,we provide a new way as theory 1 to solve the above problem. Furthermore,we also obtain a stronger condition,as theory 2 ,to decide the isomorphism of a class graphs.