to_vertex_cover

to_vertex_cover(G, matching, top_nodes=None)

返回与给定二分图 G 的最大匹配相对应的最小点覆盖。

参数:

GNetworkX 图

无向二分图

matching字典

一个字典，其键是图 G 中的顶点，其值是构成图 G 最大匹配的唯一邻居，例如由 maximum_matching() 函数返回。该字典必须表示最大匹配。

top_nodes容器

包含一个二分节点集中的所有节点的容器。如果未提供，将进行计算。但如果存在多个解，将引发异常。

返回:

vertex_coverset

图 G 中的最小点覆盖。

抛出异常:

AmbiguousSolution

当输入的二分图不连通且未提供包含一个二分集中所有节点的容器时抛出。当确定每个二分集中的节点时，如果输入图不连通，可能存在多个有效解。

注意

此函数使用 Konig 定理保证的过程实现，该定理证明了二分图中的最大匹配与最小点覆盖是等价的。

由于最小点覆盖是任何图的最大独立集的补集，因此可以通过这种方式计算二分图的最大独立集

>>> G = nx.complete_bipartite_graph(2, 3)
>>> matching = nx.bipartite.maximum_matching(G)
>>> vertex_cover = nx.bipartite.to_vertex_cover(G, matching)
>>> independent_set = set(G) - vertex_cover
>>> print(list(independent_set))
[2, 3, 4]

有关 NetworkX 中如何处理二分图的更多详细信息，请参阅 二分图文档。