to_vertex_cover

to_vertex_cover(G, matching, top_nodes=None)

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

参数

G网络X图表

无向二部图

matching词典

中以顶点为关键字的字典 G ，并且其值是构成最大匹配的不同邻居 G ，例如，如由 maximum_matching() 。这本词典 must 表示最大匹配度。

top_nodes集装箱

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

返回

vertex_cover设置

中的最小顶点覆盖 G 。

加薪

AmbiguousSolution

如果输入二部图是断开连接的，并且没有提供包含一个二部集中所有节点的容器时引发。当确定每个二部集合中的节点时，如果输入图断开连接，则可能有多个有效解。

笔记

此功能是使用以下程序实现的： Konig's theorem 证明了二部图中最大匹配与最小覆盖的等价性。

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

>>> 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]

见 bipartite documentation 有关如何在NetworkX中处理二部图的详细信息。