algorithm - 是否可以开发一种算法来解决图同构问题？

Question

或者我是否需要为每个独特的图开发一个算法？为用户提供一种图形，然后他们应该使用该界面将节点和边添加到初始图形。然后他们提交图形，算法应该确认用户的图形是否与给定的图形匹配。

该算法不仅需要确认每个节点的邻居，还需要确认每个节点和每条边都具有正确的值。初始图总是有一个根节点，这是算法可以开始的地方。

我想知道我是否可以在一般意义上为这种算法开发逻辑，或者我是否需要为每个独特的图实际编写一个独特的算法。如果是后一种情况，这没什么大不了的，因为我只有大约 20 个独特的图表。

谢谢。我希望我说得很清楚。

Answer 1

Graph isomorphism problem可能不难。但是很难证明这个问题不难。

这个问题存在三种可能。
1、图同构问题为NP-hard .
2. 图同构问题有多项式时间解。
3. 图同构问题既不是NP-hard也不是P。

如果两个图是同构的，那么这个同构存在一个排列。以此排列为证，可以证明这两个图在多项式时间内是同构的。因此，图同构存在于 NP 集的范围内。然而，30多年来，没有人能够证明这个问题是NP难还是P难。因此，尽管问题描述简单，但本质上是困难的。