【Python, networkx】max_weight_matchingの裏側

はじめに

以下の記事で用いた "max_weight_matching()" について、ザッとまとめた。
upura.hatenablog.com

max_weight_matching() について

Documentation

networkx.algorithms.matching.max_weight_matching — NetworkX 2.1 documentation

どういう関数？

• どのノードも一度以上エッジの端点にならないようなマッチングのパターンの中で、全てのエッジの重みの合計が最も大きい組み合わせを返す関数
• 計算量は (number of nodes ** 3)

アルゴリズムの詳細

Efficient Algorithms for Finding Maximum Matching in Graphs”, Zvi Galil, ACM Computing Surveys, 1986.
http://www.cs.kent.edu/~dragan/GraphAn/p23-galil.pdf

bipartite.maximum_matching() について

Documentation

Bipartite — NetworkX 2.1 documentation

どういう関数？

• 二部グラフ向けの似たような関数に見えるが、こちらはエッジの数が最大になる組み合わせを返す
• 米Wikiには、以下のような記述がある*1

A maximum matching (also known as maximum-cardinality matching[1]) is a matching that contains the largest possible number of edges.

グラフ理論のマッチングアルゴリズムの紹介スライド

以下の資料がよくまとまっていた

Maximum Matching in General Graphs from Ahmad Khayyat

*1:Matching (graph theory) - Wikipedia, 2018.06.01 available.