scipy.sparse.csgraph.

maximum_bipartite_matching#

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

傳回二分圖的配對，其基數至少與該圖的任何給定配對相同。

參數:

graph稀疏陣列或矩陣: 輸入 CSR 格式的稀疏矩陣，其列表示圖的一個分割，其行表示另一個分割。兩個頂點之間的邊由矩陣中存在的相應條目以稀疏表示法表示。
perm_typestr, {‘row’, ‘column’}: 要傳回哪個分割的配對：如果 'row'，則此函數產生一個陣列，其長度是輸入中的行數，且其第 \(j\) 個元素是與第 \(j\) 行匹配的列。相反地，如果 perm_type 是 'column'，則這會傳回與每一列匹配的行。

傳回值:

permndarray: 其中一個分割中頂點的配對。未配對的頂點在結果中以 -1 表示。

註解

此函數實作 Hopcroft-Karp 演算法 [1]。其時間複雜度為 \(O(\lvert E \rvert \sqrt{\lvert V \rvert})\)，且其空間複雜度在列數中是線性的。實際上，列與行之間的不對稱性表示，如果輸入包含的列多於行，則轉置輸入可能更有效率。

根據 Konig 定理，配對的基數也是圖的最小頂點覆蓋中出現的頂點數。

請注意，如果稀疏表示包含明確的零，這些仍會被視為邊。

實作已在 SciPy 1.4.0 中變更，以允許一般二分圖的配對，先前的版本會假設存在完美配對。因此，針對 1.4.0 撰寫的程式碼不一定適用於較舊的版本。

如果有多個有效的解決方案，則輸出可能會因 SciPy 和 Python 版本而異。

參考文獻

[1]

John E. Hopcroft 和 Richard M. Karp。“二分圖中最大配對的 n^{5 / 2} 演算法” 於：SIAM Journal of Computing 2.4 (1973)，pp. 225–231。 DOI:10.1137/0202019

範例

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

作為一個簡單的範例，考慮一個二分圖，其中分割分別包含 2 個和 3 個元素。假設一個分割包含標記為 0 和 1 的頂點，而另一個分割包含標記為 A、B 和 C 的頂點。假設有邊連接 0 和 C、1 和 A 以及 1 和 B。則此圖將由以下稀疏陣列表示

>>> graph = csr_array([[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_array((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_array((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_array(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]]