如何验证两个彩色平面图是同构的？

Question

推断两个有色平面图是否同构的算法是什么？我知道，对于一般的图来说，同构是一个很难解决的问题，然而，根据维基百科的说法，如果图是平面的，就有可能解决。

这个算法的应用将是推断两个平面分子，用一些基于图的数据结构表示，是否相同(同构)。因为节点代表原子，所以图的颜色只是原子的类型(氢、碳、氮等)。

Answer 1

我断言一个图中的一个节点只能通过一个图的同构映射到另一个图中的一个节点，如果这两个节点具有相同的度。

通过将节点放在中心，放置节点以构成其周围的度数，并在中心节点和所有其他节点之间创建链接，可以创建具有任何所需度数的节点的小平面图。通过将它缩小到您想要的小，您可以安排将其作为子图添加到给定平面图的任何节点，而不会使其成为非平面。

给定一个带有彩色节点的平面图，找出其中任何节点的最大度，并创建高于此度的小型子图作为颜色标记:为每种颜色赋予其自己的度，并将该度的一个单独的小型子图链接到该颜色的每个节点。

现在求解这个增广图上的平面图同构，您就有了原始图的解决方案。类似地，原始图的任何解决方案都可以很容易地转换为增广图的解决方案。

Answer 2

试用NetworkX库

您没有提到您对哪种编程语言感兴趣，但是python的NetworkX library有多种查找同构的方法。您可能希望查看他们的implementation of the VF2 algorithm，其中包括子类化和定义“语义”评估的能力，该评估将解决您问题中的原子元素匹配问题。语义计算已经存在于算法中，但是具有总是返回true的占位符函数，因此，如果您将占位符函数替换为计算原子元素的占位符函数，则算法类可能适用于您，否则无需修改。

或者，您可以运行算法来匹配形状，然后查看GM.mapping参数(请参阅实现链接)，并比较每个同构中等价节点上的元素是否具有元素等价性。

如果你正在寻找通用算法而不是编程库，试试这篇文章(PDF here，没有付费墙)：

L. P. Cordella，P. Foggia，C. Sansone，M. Vento，“一种改进的匹配大图的算法”，第三届IAPR-TC15模式识别中基于图形表示的研讨会，Cuen，第149-159页，2001年

更新2015年11月:显然，一位教授已经想出了如何在次NP时间内做到这一点！他还没有发表，但是here's a starter link对于那些进入纯数学的人来说。

Answer 3

This paper (我在citeseer上找到)似乎很有用，因为它既包括算法的(大纲)，也包括一些可能有用的基准测试与其他算法的比较，它还提供了参考书目。然而，我怀疑您正在研究的问题的规模不会出现在Kukluk等人的简介中。图形映射器胜过其他算法。

通用平面图同构算法甚至不会尝试利用节点的“颜色”(我会说标签，因为我通常认为颜色应用于边，但这并不是真的很重要)，你可以通过使用额外的信息来做得更好。但可以肯定的是，如果不存在未着色/未标记同构，则不可能存在着色/标记同构。不幸的是，能够构造单个同构并不足以决定是否存在具有颜色/标签的同构；您需要尝试所有可能的同构。我认为分解留下了足够的信息来简化这个搜索，但我不确定；这似乎是一个有趣的问题。

我知道你头脑中有一个特殊的编程问题，这确实(也应该)偏向于你寻找解决方案。因此，可以忽略以下几点:着色/标记同构在理论上不可能比一般同构更容易，因为它对所有节点都具有相同的颜色/标签是有效的。(我认为这与你的环境完全无关，因为你的目标分子不会由单一的元素组成，对吧？)