假设给定的两个多重图是同构的。
如何找到它们之间的双射？
我知道很难找到同构图，因为它是一个 NP 问题。
但是如果它们已经是同构图呢？
来自互联网的许多解决同构问题的资源建议先找到最短路径，然后再找到规范形式。在我实施测试之后，证明图是同构的似乎没有必要且效率低下。但是如果没有这些功能，我找不到任何其他解决方案来分离双射和同构。
笔记：
- 参考：http ://www.dharwadker.org/tevet/isomorphism/
- 多图允许自循环和多边。
问问题
885 次
1 回答
0
假设两个图之间已经存在同构可能不会帮助您更快地找到双射。
矛盾证明：假设你可以。然后，给定任意两个图，假设它们是同构的（即使它们不是同构的）并运行您的算法以找到双射。然后检查你是否真的得到了一个格式良好的双射（即线性时间）。如果你这样做了，那么这些图是同构的；如果不是，那么他们不是。因此，您已经解决了图同构问题，即 NP。
这不是一个 100% 正确的证明，因为算法可能以某种微妙的方式依赖于同构的两个图，如果它们不是同构的，这将使其成为无限循环。所以我不会说这是不可能的，但我确实觉得这个论点很有说服力。通常，假设存在解决方案通常不会帮助您找到它。
于 2016-01-02T23:53:29.860 回答