二分圖最大匹配

二分圖最大匹配（Maximum Matchings in Bipartite Graphs）是圖論中的一個重要概念，特別是在組合優化問題中。一個二分圖是由兩個頂點集 U 和 V 組成的圖，其中每個邊都連接著一個 U 中的頂點和一個 V 中的頂點。換句話說，二分圖的頂點可以被分為兩個不相交的集合，並且每個邊都跨越這兩個集合。

最大匹配是指二分圖中的一組邊，其中沒有任何兩條邊共享同一個頂點，並且這組邊的數量盡可能大。在許多情況下，最大匹配的邊數等於二分圖的兩個頂點集中最小的頂點數。

最大匹配問題在許多實際應用中都很重要，例如在電子商務中匹配買家和賣家，在諮詢行業中匹配顧問和客戶，以及在生物學中匹配蛋白質結構等。

最大匹配問題可以用許多方法來解決，包括動態規劃、貪心算法和圖著色算法等。其中最著名的是匈牙利算法（Hungarian algorithm），它可以確保找到一個最大匹配，並且在最壞情況下的時間複雜度為 O(n^3)，其中 n 是二分圖的頂點數。

此外，最大匹配問題與許多其他的組合優化問題有關，例如最小橫列問題（minimum-cost flow problem）和最大流問題（maximum flow problem）等。這些問題之間的聯繫使得它們可以相互轉化，並且可以用類似的算法來解決。