Ste*_*ini 14
这是一个问题的地狱.
一般来说,基本思想是将图形简化为规范形式,然后执行规范形式的比较.使用此目标生成生成树,但生成树不是唯一的,因此您需要使用规范方法来创建它们.
在规范形式之后,您可以轻松地执行同构比较(相对),但这只是一个开始,因为非同构图可以具有相同的生成树.(例如,考虑一个生成树T和一个边缘的单独添加来创建T'.这两个图不是同构,但它们具有相同的生成树).
其他技术涉及比较描述符(例如,节点数,边数),其通常可以产生误报.
我建议你从关于图同构问题的维基页面开始.我还有一本书建议:"图论及其应用".这是一本书,但值得每一页.
从你的推论出发,给定图的顶点的每个可能的空间分布都是同构的.因此,两个同构图具有相同的拓扑结构,从拓扑的角度来看,它们最终是相同的图形.另一个问题是,例如,找到那些享有特定属性的同构结构(例如,如果存在非交叉边缘),这取决于您想要的属性.
寻找图同构的最佳算法之一是VF2.
我已经写了一篇应用于化学的VF2的高级概述 - 它被广泛使用.该帖子涉及VF2和Ullmann之间的差异.还有一个用Java编写的VF2的从头开始实现可能会有所帮助.
| 归档时间： |
|
| 查看次数： |
6947 次 |
| 最近记录： |