我已经连续两到三天在互联网上搜索这个了,但是到目前为止还没有什么好运气。
我知道在野外有很多关于子图同构的库和实现,但它们都适用于未加权图。例如,最流行的两种算法是VF2算法和Uleman算法。在这里,我的问题是:有没有给出一个图(g)和一个查询图(G)的方法,你能发现g是否是G的一个子图(和同构的)吗?(请注意,下面是图的边列表表示形式。)
G
1 2 c
1 3 d
1 4 c
2 3 a
...
g
1 3 d
2 3 a
在这种情况下,G是一个子图,并且与G同构,但是如果我们有这样的东西:
g
1 3 t
2 3 a
现在g不再是G的子图,不再是同构的。
更新:这两个图都是无向的。