不连通图的networkx子图同构

Question

为什么networkx认为下面两个图不是同构的？

from networkx import nx
g1 = nx.empty_graph(2)   #just two unconnected nodes
g2 = nx.complete_graph(3)
GM = nx.algorithms.isomorphism.GraphMatcher(g2,g1)
print(str(GM.subgraph_is_isomorphic()))

Answer 1

被匹配的子图是一个节点诱导的子图，它也包括匹配边。

所以

from networkx import nx
g1 = nx.empty_graph(2)   #just two unconnected nodes                                                                                     
g2 = nx.complete_graph(3)
GM = nx.algorithms.isomorphism.GraphMatcher(g2,g1)
print(GM.subgraph_is_isomorphic()) # False
g3 = g2.subgraph(g1)
GM = nx.algorithms.isomorphism.GraphMatcher(g2,g3)
print(GM.subgraph_is_isomorphic()) # True, includes edge (0,1)

Answer 2

简而言之:要使用的正确函数是subgraph_is_monomorphic()，而不是subgraph_is_isomorphic()。

根据documentation的说法

最后，术语“子图”可以有多种含义。在这种情况下，“子图”总是指“节点导出子图”。不直接支持边诱导的子图同构，但应该能够通过使用nx.line_graph()来执行检查。对于没有被诱导的子图，术语“单态”比“同构”更受欢迎。

如果G‘=(N’，E‘)是节点导出子图，则:N’是N的子集，E‘是E中与N’中的节点相关的边的子集.

如果G‘=(N’，E‘)是单态，则:N’是N的子集，E‘是E中与N’中的节点相关的边集的子集.

因此，networkx中的术语子图实际上是指节点诱导的子图。OP寻找的子图同构实际上是networkx中的子图单态。

因此，

import networkx as nx
g1 = nx.empty_graph(2)   #just two unconnected nodes
g2 = nx.complete_graph(3)
GM = nx.algorithms.isomorphism.GraphMatcher(g2, g1)
print(GM.subgraph_is_monomorphic())  # True