检查一个networkx图是否是另一个图的子图

Question

我有一个叫做 G 的 networkx 图，我想检查另一个 networkx 图 H 是否可以嵌入到这个图里。简单的例子包括：

• 检查 G 中是否有三角形（可以通过 networkx.triangles 来实现）
• 检查 G 中是否有长度为 k 的路径或循环
• 检查 G 中是否有一个有 k 个叶子的星形结构（可以通过度序列来实现）

等等。

我知道这个问题通常是 NP完全 的，但我想看看是否有比简单的方法更好的解决方案，或者你有没有关于如何写这样一个方法的建议。

Answer 1

我最近在用Python做图形相关的工作，想告诉大家一个小建议：对于比较大的问题，不建议使用networkx这个库。这个库是用纯Python写的，适合处理小型图形和便于移植，但在处理较大的子图同构问题时，我发现graph-tool效果很好。

在graph-tool中，你需要找的函数在拓扑部分：

graph_tool.topology.subgraph_isomorphism