二分圖相關概念與定理

概念

• 最大比對數：最大比對的比對邊的數目
• 最小點覆寫數：選取最少的點，使任意一條邊至少有一個端點被選擇
• 最大獨立數：選取最多的點，使任意所選兩點均不相連
• 最小路徑覆寫數：對于一個 DAG（有向無環圖），選取最少條路徑，使得每個頂點屬于且僅屬于一條路徑。路徑長可以為 0（即單個點）。

定理

• 定理1：最大比對數 = 最小點覆寫數（這是 Konig 定理）
• 定理2：最大比對數 = 最大獨立數
• 定理3：最小路徑覆寫數 = 頂點數 - 最大比對數

​