第14章二分图的匹配问题

14.1 基本概念

二分图、互补顶点子集：设是无向图。若可以将分成两个非空子集和，并且使得同一子集中的任何两个顶点都互不邻接，则称为二分图。并称和为的互补顶点子集。即二分图的每条边都连接着中的一个顶点和中的一个顶点。或者说任何一条边的两个端点，必然一个在中，一个在中。
若非平凡图的每个连通分支都是二分图或平凡图，则是二分图。
二分图中必没有三角形的圈。
完全二分图：设和是二分图的互补顶点子集，若 中每个顶点都与中每个顶点相邻，则称为完全二分图。互补顶点子集分别有个顶点和个顶点的完全二分图记为。
左图是，右图是。
若无向图中有长度为奇数的闭合链，则在中有长度为奇数的圈。
定理14.1：非平凡无向图是二分图当且仅当的每个圈的长度都是偶数。

判断是不是二分图：构造两个点的集合，证明二者互补

匹配（二分图左边的点和右边的点相连，每个点最多连一条线）：设是二分图，。若中任何两条边都不相邻，则称为的匹配。
中的边一定把中的一些顶点和Y中的相同数目的一些顶点一一配成对。
中不一定把中的顶点都包括了。

最大匹配：在二分图的所有匹配中，边数最多的匹配称为最大匹配。
交错链：设是二分图的匹配，是中的基本链。若中任何相邻的两条边中恰有一条属于，则称为关于的交错链，或简称为交错链。（即交错链中属于M的边和不属于M的边是交替出现的）
饱和顶点/非饱和顶点：设是二分图的匹配，称与中的边关联的顶点为的饱和顶点，称不与中任何边关联的顶点为的非饱和顶点。
可扩充链：两个端点都是匹配的非饱和顶点的交错链称为关于的可扩充链。
可扩充链长度一定是奇数
不在匹配中的边比在匹配中的边多一条
可扩充链的两个非饱和端点，一定一个属于X，一个属于Y
若将可扩充链中原来属于匹配的边从匹配中去掉，而将原来不属于匹配的边加入匹配中，则可得到多一条边的新匹配。
定理14.2：二分图的匹配是最大匹配当且仅当中不存在关于的可扩充链

从X到Y的匹配：设和是二分图的互补顶点子集，是的匹配。若中每个顶点都是的饱和顶点，即是中某条边的端点，则称为从到的匹配。
显然，若存在从到的匹配，则。
若是从到的匹配，则是最大匹配。
的邻域 ：设，所有与中顶点相邻的顶点组成的集合称为的邻域，记为。显然，。
定理14.3 从X到Y的匹配的充要条件：设和是二分图的互补顶点子集。中存在从到的匹配当且仅当满足以下相异性条件：对于的任意子集，。
从X到Y的匹配的算法：
1. 先任意找G中一个匹配M作为初始匹配.
2. 如果M还不是从X到Y的匹配, 即有x0\in X为非饱和顶点.
3. 根据相异性条件, 设x0有邻接顶点{y01, y02,…,y0k}:
  - 若有某个y0i为非饱和顶点, 则可扩充(x0 , y0i)进M;
  - 若这k个邻接顶点都是饱和顶点,
    1. 则可构造k条以x0为起点的交替链,
    2. 并基于相异性条件, 必可找到一条可扩充链.
定理14.4 t条件从X到Y的匹配的充分条件：设和是二分图的互补顶点子集。若存在正整数，使得中每个顶点的次数，而中每个顶点的次数，则中存在从到的匹配。

判断二分图是否存在从到的条件