第五章匹配与因子分解 主要内容 一、偶图的匹配问题 二、 图的因子分解 三、匈牙利算法与最优匹配算法 教学时数 安排6学时讲授本章内容
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 1 第五章 匹配与因子分解 主要内容 一、偶图的匹配问题 二、图的因子分解 三、匈牙利算法与最优匹配算法 教学时数 安排6学时讲授本章内容
本次课主要内容 偶图的匹配问题 (一)、图的匹配与贝尔热定理 (二)、偶图的匹配与覆盖 (三)、托特定理
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 2 本次课主要内容 (一)、图的匹配与贝尔热定理 (二)、偶图的匹配与覆盖 (三)、托特定理 偶图的匹配问题
(一)、 图的匹配与贝尔热定理 1、图的匹配相关概念 (1)、匹配M-如果M是图G的边子集（不含环），且 M中的任意两条边没有共同顶点，则称M是G的一个匹 配或对集或边独立集。 如果G中顶点V是G的匹配M中某条边的端点，称它 为M饱和点，否则为M非饱和点。 M={VGV7} M2={VGV7,VIV8 M3={VGV7,VIV8,V3V4} M1,M2,M等都是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 3 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的匹配
(2)、最大匹配M-如果M是图G的包含边数最多的 匹配，称M是G的一个最大匹配。特别是，若最大匹配 饱和了G的所有顶点，称它为G的一个完美匹配。 G的一个完美匹配 G的一个最大匹配 注：一个图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 4 (2)、最大匹配M- 如果M是图G的包含边数最多的 匹配，称M是G的一个最大匹配。特别是，若最大匹配 饱和了G的所有顶点，称它为G的一个完美匹配。 G的一个 最大匹配 G的一个完美匹配 注：一个图G不一定存在完美匹配
(3)、M交错路-如果M是图G的匹配，G中一条由M 中的边和非M中的边交错形成的路，称为G中的一条M 交错路。特别地，若M交错路的起点与终点是M非饱和 点，称这种M交错路为M可扩路。 在下图中： 设M=(vVs,vY4},则： 路voV7VgV3Y4与vV7VgY2都是M交错路。其中后者是M 可扩路
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 5 (3)、M交错路- 如果M是图G的匹配，G中一条由M 中的边和非M中的边交错形成的路，称为G中的一条M 交错路。特别地，若M交错路的起点与终点是M非饱和 点，称这种M交错路为M可扩路。 在下图中： v1 v7 v6 G v8 v2 v3 v5 v4 设M=｛v7v8 , v3v4｝，则： 路v6v7v8v3v4与v1v7v8v2都是M交错路。其中后者是M 可扩路