-
M交錯路
鎖定
一條M交錯路（M-alternating Path）是指這樣一條路徑，其中的每一條邊交替地屬於或不屬於匹配M。比如説，第一、三、五條邊屬於M，而第二、四、六條不屬於M，等等。
- 中文名
-
M交錯路
- 外文名
-
M-alternating path
M交錯路定義
若M是圖G的一個匹配，若從G中一個頂點到另一個頂點存在一條道路，此路徑由屬於M和不屬於M的邊交替出現組成的，則稱此路徑為稱M交錯路。
M交錯路(M-alternating path)圖論術語.是伴隨一個對集的路(參見“對集”).設M是圖G-(V,E)的一個對集，G的一條M交錯路是指其邊在M和E\M中交錯出現的路.
[1]
M交錯路相關定義
增廣路：對於一條M交錯路，若它的起始頂點與終點都不在匹配M中，則稱它為M增廣路。同時存在充要條件：M為G的最大匹配⇔G中不存在M增廣路。
[2]
- 參考資料
-
-
1.
數學辭海
-
2.
Douglas B.West．Introduction to Graph Theory：PEARSON INDIA，2015
