0

推断两个彩色平面图是否同构的算法是什么？我知道同构对于一般的图来说是一个难题，但是，根据维基百科，如果图是平面的，则可以解决。

该算法的应用将是推断用一些基于图形的数据结构表示的两个平面分子是否相同（同构）。由于节点代表原子，因此图表的颜色只是原子的类型（氢、碳、氮等）。

4

3 回答 3

2

我声称如果两个节点具有相同的度数，则一个图中的节点只能通过图同构映射到另一个图中的节点。

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

给定一个带有彩色节点的平面图，找到其中任何节点的最大度数，并在其上方创建小度数子图作为颜色标记：为每种颜色赋予其自己的度数并将该度数的单独小子图链接到每个节点那个颜色的。

现在解决这个增强图上的平面图同构问题，您就有了原始图的解决方案。类似地，原始图的任何解决方案都可以轻松地转换为增强图的解决方案。

于 2012-10-11T17:59:21.390 回答
1

尝试 NetworkX 库

您还没有提到您对哪种编程语言感兴趣，但是 Python 的NetworkX 库有多种查找同构的方法。您可能想查看他们对 VF2 算法的实现，其中包括子类化和定义“语义”评估的能力，该评估将解决您的问题中的原子元素匹配问题。语义评估已经在算法中，但具有始终返回 true 的占位符函数，因此如果您将占位符函数替换为评估原子元素的占位符函数，则算法类可能会为您工作，否则未经修改。

或者，您可以运行算法以匹配形状，然后查看GM.mapping参数（请参阅实现链接）并比较每个同构中等效节点处的元素以实现元素等效。

如果您正在寻找通用算法而不是编程库，请尝试本文（此处为 PDF，无付费专区）：

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

2015 年 11 月更新：显然一位教授已经想出了如何在子 NP 时间内做到这一点！他还没有发表，但这里有一个入门链接，供那些进入纯数学的人使用。

于 2012-10-25T18:19:00.097 回答
0

这篇论文（我在 citeseer 上找到的）似乎很有用，因为它包括算法的（大纲）和与其他算法的一些可能有用的基准比较，它还提供了参考书目。但是，我怀疑您正在查看的问题的规模不会出现在 Kukluk 等人的配置文件中。图形映射器胜过其他算法。

通用平面图同构算法甚至不尝试利用节点“颜色”（我会说标签，因为我通常认为颜色应用于边缘，但这并不是很重要），你很可能能够使用附加信息做得更好。但可以肯定的是，如果没有未着色/未标记的同构，那么就不可能有着色/标记的同构。不幸的是，能够构建单个同构不足以决定是否存在带有颜色/标签的同构；你需要尝试所有可能的同构。我认为分解留下的信息足以简化此搜索，但我不确定；这似乎是一个有趣的问题。

我了解您有一个特定的编程问题，并且确实（并且应该）偏向您对解决方案的搜索。所以请随意忽略以下一点：着色/标记同构在理论上不可能比一般同构更容易，因为所有节点都具有相同的颜色/标签是有效的。（我认为这与您的环境完全无关，因为您的目标分子都不会由单一元素组成，对吧？）

于 2012-10-11T04:28:36.480 回答