(一)、 图的匹配与贝尔热定理 1、图的匹配相关概念 (1)、匹配M-如果M是图G的边子集（不含环），且 M中的任意两条边没有共同顶点，则称M是G的一个匹 配或对集或边独立集。 如果G中顶点v是G的匹配M中某条边的端点，称它 为M饱和点，否则为M非饱和点。 M={vov-} M=VoV7,VIVs} M3={VGV7,VIVs,V3V4} M1,M2,M3等都是G的匹配。0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 7 1、图的匹配相关概念 (1)、匹配 M--- 如果M是图G的边子集(不含环），且 M中的任意两条边没有共同顶点，则称M是G的一个匹 配或对集或边独立集。 (一)、图的匹配与贝尔热定理 如果G中顶点v是G的匹配 M中某条边的端点，称它 为M饱和点，否则为M非饱和点。 v1 v7 v6 G v8 v2 v3 v5 v4 M1=｛v6v7｝ M2=｛v6v7, v1v8｝ M3=｛v6v7, v1v8, v3v4｝ M1,M2,M3等都是G的匹配