2

我想要一个数据结构，其中键是多面体（无向 3 连通平面图；在我的情况下，它们可能主要是 <30 个顶点），查找使得相等是同构的。有没有一种有效的方法来实现这个映射？

我已经研究并反映了一点，但没有提出解决方案。似乎解决方案很可能是其中之一

  • 使用图形本身来查找数据的自定义数据结构

  • 二叉搜索树（或其他类似的树），需要明确的排序。（我怀疑是否存在这样的顺序）

  • 一个哈希表，需要一个好的哈希。我不能立即想出一个比“顶点数”或类似的更好的方法。

如何获得有效的查找？

4

2 回答 2

5

每个多面体图都是平面的。平面图的同构问题是多项式时间。它没有一般图同构问题的未知但被认为很大的复杂性。尽管效率很高，但这些算法并不简单，并且依赖于一些相当深的数学来进行分析。

原始论文（据我所知）是 Hopcroft 1971 年的论文An N log N Algorithm for Isomorphism of Planar Triple Connected Graphs，可从斯坦福获得扫描副本。在这个问题上有相当多的工作。最近的一篇论文是Algorithm and Experiments in Testing Planar Graphs for Isomorphism，它引用了许多现有算法以及它们之间的运行时间比较。本文提出了一种算法，它为每个图分配一个唯一的代码，顺便说一下，它还生成了一个定义良好的排序。他们在那篇论文中关于小图的最佳结果是 Brendan McKay 在Practical Graph Isomorphism中的算法。

于 2012-11-27T14:10:52.493 回答
2

由于图同构不是那么容易检查的，我建议尽量减少同构检查的数量。您的哈希表似乎是一个好的开始。您需要一把好钥匙来最大化分辨率

假设您使用[V,out_1,in_1,out_2,in_2,...] 具有V=nr 个顶点、out_i=ith 最高出度、in_1=indegree 的具有最高出度的节点的数组（首先对出度排序，然后对入度进行排序）。这会比你的 nr 顶点更有效（但你可能已经想到了类似的东西）。

上面是一个相当粗略的示例，您实际上可以使用任何（组合）图形不变量作为表的键。根据您拥有的图的数量及其相似性，您应该选择给您最大差异/分辨率能力的一个（如果您的所有图都具有相同数量的顶点，则使用 nr 顶点是无用的）。

使用不变量，您可以构造一棵树，也可以使用它们来创建您需要的排序。可以使用上面的数组示例，因为它定义了一个完整的顺序，但您可以再次使用任何不变量

于 2012-11-22T14:50:31.433 回答