如何从给定的同构图中找到双射？

Question

假设给定的两个多图是同构的.

如何才能在他们之间找到一个双射体呢？

我知道很难找到同构图，因为它是一个NP问题。

但是如果它们已经是同构图呢？

互联网上许多解决同构问题的资源都建议先找到最短路径，然后再寻找规范形式。在我的测试实现之后，证明这些图是同构的似乎是不必要的和低效的。但是，没有这些函数，我就找不到任何其他的解来分离双射和同构。

注意：

1. 参考资料：http://www.dharwadker.org/tevet/isomorphism/
2. 多图允许自循环和多边缘.

Answer 1

假设两个图之间已经存在同构关系，这可能不能帮助您更快地找到双射。

用矛盾来证明:假设你可以。然后，给定任意两个图，假设它们是同构的(即使它们不是)，并运行您的算法来找到一个双射。然后检查你是否得到了一个良好的双射(这是线性时间)。如果是的话，那么这些图是同构的，如果不是，那么它们就不是，这样就解决了图同构问题，即NP。

这不是一个100%正确的证明，因为算法可能以某种微妙的方式依赖于两个图是同构的，如果它们不是同构的，就会产生无限循环。所以我不会说这是不可能的，但我觉得这个论点很有说服力。一般来说，假设存在一个解决方案，通常不会帮助您找到它。