Networkx python模块函数GraphMatcher.subgraph_is_isomorphic()用法

Question

isomatcher = nx.isomorphism.GraphMatcher(G, H)
isomatcher.subgraph_is_isomorphic()

根据我的理解，如果 G 的子图与 H 同构，则该函数返回 True。 然而，当我按如下方式运行此代码时：

import networkx as nx

G = nx.Graph()
G.add_nodes_from([0,1,2,3])
G.add_edges_from([(0, 2), (0, 3), (1, 2), (1, 3), (2, 3)])

H = nx.Graph()
H.add_nodes_from([0,1,2,3,4,5])
H.add_edges_from([(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)])
isomatcher = nx.isomorphism.GraphMatcher(H, G)
print(isomatcher.subgraph_is_isomorphic())

输出为 false，尽管显然 G 与 H 的某个子图同构，因为 H 是 6 个顶点的完整图。

我尝试将顶点索引更改为不同的数字，但没有帮助。 我相信我对这个功能的理解不正确。 有人可以给我解释一下吗？

Answer 1

networkx 中的术语“子图”实际上指的是“节点引发的子图”。也就是说，如果您选择一组节点，则导出的子图包括这些节点之间的所有边。 A

单态

是子图的更灵活的版本。在这种情况下，您可以拥有节点子集和边子集，但这些节点之间的边不必全部可能（如在节点诱导的子图中）。 那么，

import networkx as nx

G = nx.Graph()
G.add_nodes_from([0,1,2,3])
G.add_edges_from([(0, 2), (0, 3), (1, 2), (1, 3), (2, 3)])

H = nx.Graph()
H.add_nodes_from([0,1,2,3,4,5])
H.add_edges_from([(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)])

isomatcher = nx.algorithms.isomorphism.GraphMatcher(H, G)
print(isomatcher.subgraph_is_monomorphic()) # TRUE

您可以查阅

文档

。