-
增廣路
鎖定
若P是圖G中一條連通兩個未匹配頂點的路徑，並且屬於M的邊和不屬於M的邊(即已匹配和待匹配的邊)在P上交替出現，則稱P為相對於M的一條增廣路徑（舉例來説，有A、B集合，增廣路由A中一個點通向B中一個點，再由B中這個點通向A中一個點……交替進行）。
- 中文名
- 增廣路
- 外文名
- Augmenting Path
- 概 述
- 若P是圖G中一條交替聯通兩個集合的路徑
- 結 論
- P的路徑長度必定為奇數
增廣路主要性質
1－P的路徑長度必定為奇數，第一條邊和最後一條邊都不屬於M，不匹配的邊比匹配的邊多一。
證明：
根據增廣路的定義，P連通兩個未匹配頂點，可知P的第一條和最後一條邊都不屬於M。
我們設
，且
.
由於P中的邊交替出現，即
.
我們可以令
，即
由於
,可知
.
可知 n-1=2k, 所以n=2k+1，且匹配的邊比不匹配的邊多1.
2－不斷尋找增廣路可以得到一個更大的匹配M’，直到找不到更多的增廣路。
證明：
我們可以構造一條另外的路徑
取代
，從而找到一個更大的匹配
。
由性質1，在P中不匹配的邊比匹配的邊多1，那麼在P'中，匹配的邊比不匹配的邊多1.
所以
。
3－M為G的最大匹配當且僅當不存在M的增廣路徑。
引理1： 對於圖G的任意兩個匹配M和M'，它們的對稱差
的連通分支是
一條路徑或者一個長度為偶數的圓。
證明：
, e要麼是M中的一條邊，要麼是M'中的一條邊，但不能同時出現於M和M'中。且對於e的
鄰邊e'，e和e‘必然來自兩個不同的匹配，因為一個頂點只能出現於一個匹配中。所以對於e的任意一個頂點u,
d(u)=1（沒有通過頂點u與e相鄰的邊）或者d(u)=2 （e有一條公用頂點u的鄰邊）。
對於其中的圓，由於圓中的每一條邊，其鄰邊必然來自不同的匹配中，所以圓的長度必然為偶數。
必要性：
假設M為G的最大匹配且存在M的增廣路徑P，由性質2，我們可以通過P來構建路徑P'從而找到比M更大的匹配。
所以一定不存在M的增廣路徑。
充分性：
即如果不存在M的增廣路徑，那麼M為G的最大匹配。
我們找到它的逆否命題：如果M不是G的最大匹配，那麼一定存在M的增廣路徑。
要證明這個等價的逆否命題，我們必須利用引理1.
我們設M'是比M更大的一個G的匹配。我們找到它們的對稱差
，可知其連通分支為路徑或圓。由於圓的
長度為偶數，所以必然有同樣多的邊來自M和M'。由於
，存在至少一條路徑
，其中有k條邊
來自於M，剩餘的k+1條邊來自M'。該條路徑
就是一條M的增廣路徑，所以我們必然可以找到一條M的增
廣路徑，該命題成立，所以充分性成立。
增廣路應用
- 增廣路用於證明最大匹配問題。
