精选优质文档-倾情为你奉上第四章 匹配问题及其应用一、匹配理论概念及基本性质（1）定义：1、设M是图G的边子集，称M是G中的一个匹配，若M中任二边在G中不相邻；M中的每条边的两个端点称为在M中相配；M中每边的端点称为被M许配；称M为G的一个完全匹配，若G中每个顶点皆被M许配；称G的最大匹配，若对任意的G的匹配，均有。2、权数：对于匹配M，它的权数为。3、称M为最优匹配，若M为所有匹配中权数最大的匹配。4、称P为关于匹配M的可扩路：设M是图G的一个匹配，若路P的边在M中交替出现，且P的两个端点是M不饱和的。5、称B是G的一个覆盖集：设，若G的每条边皆与B中的顶相关联。6、称B是G的极小覆盖：设，若B是G的一个覆盖集，但，不再是G的覆盖集。7、称B为G的最小覆盖：设，若B是G的顶数最小的覆盖集。8、G的覆盖数：最小覆盖中顶的数目，记作。9、A B为A与B的对称差：A B=，其中A、B为集合，有时也写成。（2）基本性质：1、M是图G中的一个最大匹配当且仅当G中无M的可扩路。2、设G是二分图，顶
