文档介绍：第6章图与网络分析
67最大匹配问题
20188/11
最大对集(匹配)问题
●二分图的对集,基本概念,主要定理
二分图的最大匹配算法
二分图的带权重的最大匹配分派问题及算法
20188/11
山东大学软件学院
基本概念
●图G=(V,E)的对集M:M是E的子集,且M中任意两条边
均不相邻(都不共享顶点)。
M饱和点:VM中的顶点(i∈VM),匹配的点)
●M非饱和点i:VM之外的顶点(gVM),没有匹配的点)。
●极大对集M:不存在另外一个对集M’,使得McM′。
最大对集M:不存在另外一个对集M',使得M1>M
●完美对集M:对集M,匹配了G上所有的点。
20188/11
山东大学软件学院
3
例子
U)
20188/11
山东大学软件学院
顶点覆盖
20188/11
山东大学软件学院

定理681( Berge,1957)图G中的一个匹配M是最大匹配当且
仅当G不包含M-增广路
(说明:G是一般图,不要求是二分图。)
●证:(→)。G上若有M-增广路,则可以使用这条路更新M得
到基数更大(多1)的一个匹配,与M是最大匹配矛盾。
●(←)。假设M是一个匹配,图G上不含有M增广路,而M不
是最大匹配。
●于是,存在G上另外一个匹配M,有M>M
20188/11
山东大学软件学院