to_vertex_cover

to_vertex_cover(G, matching, top_nodes=None)

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

Parameters:

GNetworkX 图

无向二分图

matching字典

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

top_nodes容器

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

Returns:

vertex_coverset

G 中的最小顶点覆盖。

Raises:

AmbiguousSolution

如果输入的二分图是不连通的，并且没有提供包含一个二分集所有节点的容器，则会引发此异常。在确定每个二分集中的节点时，如果输入图是不连通的，可能存在多个有效解决方案。

Notes

此函数使用 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 中如何处理二分图的更多详细信息，请参阅 bipartite 文档 。