映射与多面体图作为键

Question

我想要一个数据结构,其中键是多面体(无向3个连接的平面图;在我的情况下,它们可能大多数是<30个顶点),查找等式是同构.有没有一种有效的方法来实现这种映射？

我已经研究和反思了一些但没有提出解决方案.似乎解决方案可能是其中之一

• 一种自定义数据结构,使用图表本身来查找数据

• 二叉搜索树(或其他类似树),需要明确定义的排序.(我怀疑存在这样的排序)

• 哈希表,需要良好的哈希值.我不能立即想出一个比"顶点数"或类似更好的一个.

我怎样才能获得有效的查找？

Answer 1

每个多面体图都是平面的.平面图的同构问题是多项式时间.它没有一般图同构问题的未知但思想很大的复杂性.虽然效率很高,但算法并不简单,依赖于一些相当深入的数学来进行分析.

原始论文(据我所知)是霍普克罗夫特1971年发表的一篇关于平面三次连通图同构的An N log N算法,可从斯坦福大学获得,作为扫描副本.关于这个问题有相当多的工作.最近的一篇论文是" 测试同构平面图中的算法和实验",它具有许多对现有算法的参考和它们之间的运行时间比较的优点.本文提出了一种算法,为每个图形分配一个唯一的代码,顺便提一下,它也生成一个明确定义的顺序.他们在小图中的最佳结果是Brendan McKay在Practical Graph Isomorphism中的算法.