与匹配相关的概念 定义6.假设M为图G中一个匹配, 若(vvy)eM,则称v与v被M所匹配即v)为匹配边;否 则为非匹配边 对Wv∈v(G),若存在边e∈M,使e与v关联,则称v为M-饱和 点;否则,称v为M非饱和点; 若G中每个顶点都是M饱和点,则称M为G中的完美匹配; 称在M和E(G)M中交替取边的路径为M的交错路径,起点 和终点都是M-非饱和点的交错路径称为可增广的交错路径 称在M和E(G-M中交替取边的圈为交错圈 1010 与匹配相关的概念 定义6. 假设M为图G中一个匹配, ¾ 若(vi, vj)∈M, 则称vi与vj被M所匹配,即(vi, vj)为匹配边;否 则为非匹配边; ¾ 对∀v∈V(G), 若存在边e∈M, 使e与v关联, 则称v为M-饱和 点; 否则, 称v为M-非饱和点; ¾ 若G中每个顶点都是M-饱和点, 则称M为G中的完美匹配; ¾ 称在M和E(G)-M中交替取边的路径为M的交错路径, 起点 和终点都是M-非饱和点的交错路径称为可增广的交错路径; ¾ 称在M和E(G)-M中交替取边的圈为交错圈