scipy.sparse.csgraph.

最大二分匹配

scipy.sparse.csgraph.maximum_bipartite_matching(graph, perm_type='row')

返回一个二分图的匹配，其基数至少与图中任何给定匹配的基数相同。

参数:

图稀疏矩阵

输入的CSR格式稀疏矩阵，其行表示图的一个分区，列表示另一个分区。两个顶点之间的边由矩阵稀疏表示中对应的条目指示。

perm_typestr, {‘row’, ‘column’}

返回匹配的分区类型：如果 'row'，该函数生成一个数组，其长度为输入中的列数，并且其第 \(j\) 个元素是与第 \(j\) 列匹配的行。相反，如果 perm_type 是 'column'，则返回与每一行匹配的列。

返回:

权限ndarray

两个分区中一个分区的顶点的匹配。未匹配的顶点在结果中用 -1 表示。

注释

该函数实现了Hopcroft–Karp算法 [1]。其时间复杂度为 \(O(\lvert E \rvert \sqrt{\lvert V \rvert})\)，空间复杂度与行数成线性关系。在实际应用中，这种行与列之间的不对称性意味着，如果输入包含的列数多于行数，转置输入可能会更高效。

根据Kőnig定理，匹配的基数也是图中出现在最小顶点覆盖中的顶点数。

请注意，如果稀疏表示包含显式零，这些仍被视为边。

在 SciPy 1.4.0 中，实现被修改以允许匹配一般二分图，而之前的版本会假设存在一个完美匹配。因此，针对 1.4.0 编写的代码不一定能在旧版本上运行。

如果存在多个有效解决方案，输出可能会因 SciPy 和 Python 版本的不同而有所变化。

参考文献

[1]

John E. Hopcroft 和 Richard M. Karp. “一种用于二分图最大匹配的 n^{5 / 2} 算法” 载于: SIAM 计算杂志 2.4 (1973), 页码 225–231. DOI:10.1137/0202019

示例

Try it in your browser!

>>> from scipy.sparse import csr_matrix
>>> from scipy.sparse.csgraph import maximum_bipartite_matching

作为一个简单的例子，考虑一个二分图，其中分区分别包含2和3个元素。假设一个分区包含标记为0和1的顶点，另一个分区包含标记为A、B和C的顶点。假设有边连接0和C，1和A，以及1和B。这个图将由以下稀疏矩阵表示：

>>> graph = csr_matrix([[0, 0, 1], [1, 1, 0]])

在这里，1 可以是任何东西，只要它们最终作为稀疏矩阵中的元素存储。我们现在可以如下计算最大匹配：

>>> print(maximum_bipartite_matching(graph, perm_type='column'))
[2 0]
>>> print(maximum_bipartite_matching(graph, perm_type='row'))
[ 1 -1  0]

第一个输出告诉我们1和2分别与C和A匹配，第二个输出告诉我们A、B和C分别与1、无和0匹配。

请注意，显式零仍然会被转换为边。这意味着可以通过直接使用CSR结构来表示上述图，如下所示：

>>> data = [0, 0, 0]
>>> indices = [2, 0, 1]
>>> indptr = [0, 1, 3]
>>> graph = csr_matrix((data, indices, indptr))
>>> print(maximum_bipartite_matching(graph, perm_type='column'))
[2 0]
>>> print(maximum_bipartite_matching(graph, perm_type='row'))
[ 1 -1  0]

当一个或两个分区为空时，匹配也为空：

>>> graph = csr_matrix((2, 0))
>>> print(maximum_bipartite_matching(graph, perm_type='column'))
[-1 -1]
>>> print(maximum_bipartite_matching(graph, perm_type='row'))
[]

当输入矩阵是方阵，并且已知图允许完美匹配，即图中每个顶点都属于匹配中的某条边时，那么可以将输出视为行（或列）的排列，使得输入矩阵变为所有对角元素均非空的矩阵：

>>> a = [[0, 1, 2, 0], [1, 0, 0, 1], [2, 0, 0, 3], [0, 1, 3, 0]]
>>> graph = csr_matrix(a)
>>> perm = maximum_bipartite_matching(graph, perm_type='row')
>>> print(graph[perm].toarray())
[[1 0 0 1]
 [0 1 2 0]
 [0 1 3 0]
 [2 0 0 3]]

Go BackOpen In Tab