我想要一个数据结构,其中键是多面体(无向3连通平面图;在我的例子中,它们很可能是<30个顶点),查找这样的等式是同构的。是否有一种有效的方法来实现此映射?
我已经做了一些研究和思考,但没有想出一个解决方案。似乎解决方案很可能是
我怎样才能得到有效的查找?
发布于 2012-11-27 14:10:52
每个多面体图都是平面的。平面图的同构问题是多项式时间。它没有一般的图同构问题的复杂程度。虽然算法是有效的,但算法并不简单,而是依赖于一些比较深入的数学来进行分析。
最初的论文(据我所知)是Hopcroft 1971年的论文,一种平面三连通图同构的N log算法,可从斯坦福大学获得为扫描拷贝。在这个问题上有很多工作要做。最近的一篇论文是http://www.emis.de/journals/JGAA/accepted/2004/KuklukHolderCook2004.8.3.pdf,它的优点是引用了现有的算法,并对它们之间的运行时间进行了比较。本文提出了一种为每个图分配唯一代码的算法,该算法还生成了一个定义良好的排序。本文对小图的最佳结果是Brendan McKay在http://cs.anu.edu.au/~bdm/papers/pgi.pdf中的算法。
发布于 2012-11-22 14:50:31
由于图同构不是那么容易检查,所以我建议尽量减少同构检查的次数。你的哈希表似乎是个好开始。你需要一把好钥匙才能最大限度地提高分辨率。
假设使用具有[V,out_1,in_1,out_2,in_2,...] =nr顶点的数组V=nr顶点,out_i=ith最高输出度,in_1=索引树具有最大输出度的节点(首先对输出度排序,然后在索引树上排序)。这样做的效率会略高一些(但您可能已经想到了类似的事情),而不是nr顶点。
以上是一个相当粗糙的例子,您实际上可以使用任何(组合) 图不变量作为表的键。根据您拥有的图的数量和它们的相似性,您应该选择给您提供最大差异/分辨率的图(如果您的所有图都有相同的顶点数,则使用nr顶点是无用的)。
使用不变量,可以构造树,也可以使用不变量创建所需的排序。上面的数组示例可以使用,因为它定义了一个完整的顺序,但是您可以再次使用任何不变量。
https://stackoverflow.com/questions/13334516
复制相似问题