计算子图实例
假设我有一个大的（几千个节点）有向图G和一个小得多的（3-5个节点）有向图g。我想计算G中有多少个g同构。换句话说，我想知道G中有多少个唯一的节点集与g匹配。我意识到这是子图同构问题的一个实例，因此是 NP 完全的。但是，考虑到您可能假设 g 很小，是否有任何相当有效的算法可以做到这一点？
Let's say I have a large (several thousand node) directed graph G and a much smaller (3-5 node) directed graph g. I want to count how many isomorphisms of g are in G. In other words, I want to know how many unique sets of nodes in G match g. I realize that this is an instance of the subgraph isomorphism problem and is therefore NP-complete. However, given that you may assume that g is small, is there any reasonably efficient algorithm for doing this?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
尽管图同构通常是 NP 完全的，但在现实世界中遇到的问题通常非常简单。一个简单的暴力破解就足够了：设
M_i为从 g 的前 i 个节点到 G 的节点的一组映射。从包含空映射的m_0开始并扩展一次一个节点，当且仅当m(x)->m(y)时，丢弃任何违反约束x->y的映射。您需要对 g 中的节点进行排序，以便尽早进行大量修剪。假设你的图非常稀疏，你会想要一个尽早完成尽可能多的边的顺序，也许是来自最高度节点的 dfs。
Although graph isomorphism is NP-complete in general, problems you come across in the real world are often pretty easy. A simple brute-force should suffice: Let
M_ibe a set of maps from the first i nodes of g to nodes of G. Start withm_0containing the empty map and extend it one node at a time, discarding any maps which violate the constraintx->yiffm(x)->m(y).You'll want to order the nodes in g so that lots of pruning happens early. Assuming your graphs are pretty sparse, you'll want an order that completes as many edges as early as possible, maybe a dfs from the highest degree node.