完美匹配(圖論概念)

完美匹配，是圖論中的重要概念，一種覆蓋圖中所有點的特殊匹配。

基本介紹

• 中文名：完美匹配
• 外文名：Perfect Matching
• 所屬學科：圖論、組合數學

定義

若圖中的一個匹配，包括了圖中的所有點，則稱這個匹配為完美匹配。完美匹配使圖中所有點都為匹配點。

紅色路徑即一完美匹配

定理

𝐾_2𝑛, 𝐶_2𝑛, 𝑃_2n含完美匹配。

塔特定理：圖 G=(V,E) 有完美匹配若且唯若滿足 ∀U⊆V,o(G−U)≤|U|,o(X) 表示 X 子圖的奇連通塊數。

Peterson定理：每一個無橋的、3-正則圖都含有一個完美匹配。

若一個含2n個點的圖G滿足最小度δ（G）≥n，則G含一個完美匹配。