增廣路

若P是圖G中一條連通兩個未匹配頂點的路徑，並且屬於M的邊和不屬於M的邊(即已匹配和待匹配的邊)在P上交替出現，則稱P為相對於M的一條增廣路徑（舉例來說，有A、B集合，增廣路由A中一個點通向B中一個點，再由B中這個點通向A中一個點……交替進行）。

基本介紹

• 中文名：增廣路
• 概述：若P是圖G中一條連通兩個
• 結論：P的路徑長度必定為奇數

由增廣路的定義可以推出下述五個結論：

1－P的路徑長度必定為奇數，第一條邊和最後一條邊都不屬於M。

2－不斷尋找增廣路可以得到一個更大的匹配M’，直到找不到更多的增廣路。

3－M為G的最大匹配若且唯若不存在M的增廣路徑。

4－最大匹配數M+最大獨立數N=總的結點數

5 -- 二分圖的最小路徑覆蓋數 = 原圖點數 - 最大匹配數

增廣路主要套用於匈牙利算法中，用於求二分圖最大匹配。