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

Question

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

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

Answer 1

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

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

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

现在求解这个增广图上的平面图同构，你就有了原始图的解。类似地，原始图的任何解都可以很容易地转化为扩充图的解。