图论讲义91
需积分: 0 186 浏览量
2022-08-03
20:49:23
上传
评论
收藏 450KB PDF 举报
第六章 对集（匹配）
§6.1 对集
对集：设 它的元素是 G 中的连杆，并且这些连杆中任意两个
在 G 中均不相邻，则 M 称为 G 的对集(或匹配)；M 中一条边的两个
端点称为在 M 下是配对的。若对集 M 的某条边与顶点 v 关联，则称
M 饱和 v，并称 v 是 M 饱和的，否则称 v 是 M 非饱和的。
完美对集：若 M 是对集，且 G 的每个顶点都是 M 饱和的，则称 M
为 G 的完美对集。
最大对集：若 M 是对集，且 G 没有另外的对集，使得
则称 M 是 G 的最大对集。
*显然，每个完美对集都是最大对集，反之则不一定。
例子：（见图 6.1）
M-交错路：设 M 是 G 的对集，G 的 M-交错路是指其边在 和 中
交错出现的路。
例子：图 6.1 中
是一条 M-交错路。
M-可扩路：是指其起点和终点都是 M 非饱和顶点的 M-交错路。
定理 6.1(Berge)：G 的对集 M 是最大对集当且仅当 G 不包含 M-可扩
路。
证：设 M 是 G 的对集，并假设 G 包含 M-可扩路
，定义
为:
令径上的对集边和对集边交换，可以得到个M的对集
评论0