二分圖的最大匹配數是什麼

二分圖的最大匹配數（Maximum Matching）是指在一個二分圖中可以找到的最大數量的邊，這些邊互不交錯，即每條邊的兩個端點分別來自二分圖的兩個分類。在圖論中，這通常被簡稱為最大匹配。

例如，考慮以下這個二分圖：

A -- B
 |   |
C -- D

這個二分圖的最大匹配數是2，因為我們可以找到兩條不交錯的邊：A-B和C-D。如果我們再嘗試添加一條邊，比如E-F：

A -- B
 |   |
C -- D
   \  /
    E - F

那麼新的二分圖的最大匹配數仍然是2，因為我們不能在不交錯的條件下再添加一條邊。

在圖論中，有時會研究二分圖的另一個概念，即完美匹配（Perfect Matching），這是指當二分圖的每個頂點都是某條匹配邊的一部分時。在上面給出的例子中，如果我們有6個頂點，那麼找到一個完美的匹配是不可能的，因為6不是2的倍數。然而，如果我們有4個頂點，那麼一個完美的匹配是可能的，例如：

A -- B
 |   |
C -- D

在這個例子中，A-B和C-D就是一個完美的匹配。

總結一下，最大匹配數是指在一個二分圖中可以找到的最大數量的不交錯邊，而完美匹配是指當二分圖的每個頂點都是某條匹配邊的一部分時的匹配。