首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >以多面体图为键的映射

问以多面体图为键的映射
EN

Stack Overflow用户
提问于 2012-11-11 19:20:04
回答 2查看 127关注 0票数 2

我想要一个数据结构,其中键是多面体(无向3连通平面图;在我的例子中,它们很可能是<30个顶点),查找这样的等式是同构的。是否有一种有效的方法来实现此映射?

我已经做了一些研究和思考,但没有想出一个解决方案。似乎解决方案很可能是

  • 使用图形本身查找数据的自定义数据结构。
  • 二进制搜索树(或其他类似的树),它需要一个定义良好的排序。(我怀疑这样的命令是否存在)
  • 一个哈希表,它需要一个很好的散列。我不能立即想出一个比“顶点数目”或类似的更好的办法。

我怎样才能得到有效的查找?

EN

回答 2

Stack Overflow用户

回答已采纳

发布于 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中的算法。

票数 5
EN

Stack Overflow用户

发布于 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顶点是无用的)。

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

票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/13334516

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档