二分圖最佳匹配

二分圖最佳匹配（Maximum Cardinality Matching）是圖論中的一個重要問題，它的目標是在一個二分圖（即圖的頂點可以分為兩個頂點集，並且每個邊的端點分別屬於不同的頂點集）中找到一組邊，使得這組邊的數量最多，並且不存在任何一對邊，它們共用同一個頂點。

這個問題的應用非常廣泛，例如在勞動力市場中匹配工人和崗位，在學校中匹配學生和導師，在交通網絡中匹配車輛和路線等。

解決二分圖最佳匹配問題的一種有效方法是使用匈牙利算法（Hungarian algorithm）。匈牙利算法可以在時間複雜度為 O(n^3) 的情況下找到一個二分圖的最佳匹配，其中 n 是二分圖的頂點數。這個算法可以通過使用一些優化技巧進一步減少時間複雜度，但是最壞情況下的複雜度仍然是 O(n^3)。

除了匈牙利算法，還有其他一些算法可以用來解決二分圖最佳匹配問題，例如基於增廣路徑的算法（Augmenting path algorithms）和基於流模型的算法（Flow-based algorithms）。這些算法可能在某些情況下比匈牙利算法更有效。