二分图简介

二分图又称作偶图，是图论中的一种特殊模型。

设 G=(V,E) 是无向图，如果根据顶点 V 可分割为两个互不相交的子集 (A,B)，且图中的每条边（i,j）所关联的两个顶点 i 和 j 分属这两个不同的顶点集 (i $\in$ A,j $\in$ B)，则图 G 就是一个二分图。

简单来说，就是顶点集 V 可分割为两个互不相交的子集，且图中每条边依附的两个顶点都分属于这两个互不相交的子集，两个子集内的顶点不相邻。

当图中的顶点分为两个集合，使得第一个集合中的所有顶点都与第二个集合中的所有顶点相连时，此时是一特殊的二分图，称为完全二分图。

二分图的概念

在给定一个二分图 G，在 G 的一个子图 M 中，若 M 的边集中的任意两条边都不依附于同一个顶点，则称 M 是一个匹配。

简单来说，匹配就是一个二分图中边的集合，其中任意两条边都没有公共顶点。

如图，红边就是一个匹配

二分图
匹配点、匹配边、未匹配点、非匹配边，它们的含义非常显然。例如上图中 1、4、5、7 为匹配点，其他顶点为未匹配点；1-5、4-7为匹配边，其他边为非匹配边。

给定二分图 G 中的所有匹配，所含匹配边数最多的匹配，称为这个图的最大匹配。

如图，这些红边就是最大匹配

二分图

一个匹配中，图中每个顶点都与图中某条边相关联，则称此匹配为完全匹配，即一个图的某个匹配中，所有的顶点都是匹配点，就是一个完全匹配。

显然，由于完全匹配的任何一个点都已经匹配，添加一条新的匹配边一定会与已有的匹配边冲突，因此完全匹配一定是最大匹配。但要注意的是，并非每个图都存在完全匹配。

简单来说，对于一个二分图，左点集中的每一个点都与右点集的一个点匹配，或者右点集中的每一个点都与左点集的一个点匹配。

（详情请见啊哈磊作《啊哈！算法》第8章，第5节）

举例来说，如下图所示，若存在某一对男孩和女孩之间存在相连的边，就意味着他们彼此喜欢。是否可能让所有男孩和女孩两两配对，使得每对儿都互相喜欢？这就是完全匹配问题。而最多有多少互相喜欢的男孩/女孩可以配对？这就是最大匹配问题。

二分图

好了，我今天讲的内容结束了。您有什么问题可以来问我，我的blog有问题您也可以来提醒我改正