Networkx中GraphMatcher.subgraph_is_isomorphic()功能误解及问题咨询

问题描述 #

原本以为Networkx的GraphMatcher.subgraph_is_isomorphic()函数会在第一个图的某个子图与第二个图同构时返回True，但运行以下代码时输出为False：

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())

H是6顶点完全图，直觉上G应该和H的某个子图同构，但结果不符合预期，修改顶点索引也没用，显然是对函数功能的理解有误。

问题分析与解答 #

1. 函数参数与功能的核心误解 #

GraphMatcher(G1, G2).subgraph_is_isomorphic()的实际功能是：判断G1是否与G2的某个子图同构，而非G1包含G2的子图同构。你初始化时传入的是GraphMatcher(H, G)，相当于在检查「6顶点完全图H是否是4顶点图G的子图同构」，这显然不可能，这是第一个错误。

2. 诱导子图的默认行为 #

更关键的是，subgraph_is_isomorphic()默认检查的是诱导子图同构——也就是子图必须包含原图中该顶点子集的所有边。你的G并非4顶点完全图：G中顶点0和1之间没有边，而H是完全图，它的任意4顶点诱导子图都是完整的K4（所有顶点间都有边），自然和G不同构，这才是返回False的根本原因。

3. 正确用法示例 #

场景1：检查G是否是H的非诱导子图同构

如果不需要严格的诱导子图（即允许子图只包含原图中顶点子集的部分边），可以设置induced=False参数，同时调整GraphMatcher的参数顺序为(G, H)：

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.complete_graph(6)
isomatcher = nx.isomorphism.GraphMatcher(G, H)
print(isomatcher.subgraph_is_isomorphic(induced=False))  # 输出True

场景2：检查诱导子图同构

如果要验证诱导子图同构，需要把G改为4顶点完全图，此时就能匹配到H中的4顶点诱导子图：

import networkx as nx

G = nx.complete_graph(4)
H = nx.complete_graph(6)
isomatcher = nx.isomorphism.GraphMatcher(G, H)
print(isomatcher.subgraph_is_isomorphic())  # 输出True

内容的提问来源于stack exchange，提问作者Will Chang