algorithm - 您将如何验证两个图是否相同？

Question

假设我们想用图表示分子，其中每个节点都是一个原子，每条边是原子之间的连接。什么是确定两个图(代表分子)是否等效的算法。由于要表示分子，因此每个节点都需要一个属性来定义它是哪个分子(碳、氮、氧等)。

为简化起见，假设每个图都从同一个根原子 Nitrogen 分支出来，我们可以将其用作算法的起始节点。

例如。 N-X、N-Y、N-Z。其中 N 是根 Nitrogen 节点，X、Y、Z 是图形的其余部分。

Answer 1

那是 Graph Isomorphism Problem ;

The graph isomorphism problem is one of few standard problems in computational complexity theory belonging to NP, but not known to belong to either of its well-known (and, if P ≠ NP, disjoint) subsets: P and NP-complete. It is one of only two, out of 12 total, problems listed in Garey & Johnson (1979) whose complexity remains unresolved, the other being integer factorization.

换句话说，在一般情况下解决它是困难。