圖最大匹配

圖最大匹配（Maximum Matching）是圖論中的一個重要概念，指的是在一幅圖中找到一組邊，使得這些邊互不交錯，並且邊數盡可能多。在許多情況下，最大匹配也被稱為最大獨立邊集。

在無向圖中，最大匹配的定義是這樣的：對於圖G = (V, E)，一個匹配M是E的一個子集，其中沒有兩條邊共享同一個頂點。最大匹配M*是所有可能的匹配中邊數最多的匹配。

在有向圖中，最大匹配的定義略有不同。一個匹配M是E的一個子集，其中每對起點和終點只出現一次。最大匹配M*是所有可能的匹配中邊數最多的匹配。

最大匹配問題在許多領域都有應用，例如在電子商務中，最大匹配可以用來幫助配對買家和賣家，以最大化交易量；在輿論分析中，最大匹配可以用來識別意見領袖和普通用戶之間的關係；在生物學中，最大匹配可以用來分析基因表達數據，以發現基因之間的相互作用。

最大匹配問題可以通過許多算法來解決，例如匈牙利算法、增廣路徑算法、配對起點算法等。這些算法可以在線性時間內解決無向圖的最大匹配問題，對於有向圖，則可以在多項式時間內解決。