图论 —— 二分图

　

二分图

【概述】

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

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

其充要条件是：图 G 中至少存在两个点，且图中所有回路的长度均为偶数。

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

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

【基本概念】

1.匹配

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

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

如图，红边就是一个匹配

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

2.最大匹配

给定二分图 G 中的所有匹配，所含匹配边数最多的匹配，称为这个图的最大匹配，选择最大匹配的问题即为图的最大匹配问题

如图，红边就是一个最大匹配

3.完全匹配

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

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

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

4.完美匹配

对于一个二分图，左点集与右点集的点数相同，若存在一个匹配，包含左点集、右点集的所有顶点，则称为完美匹配。

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

如下图，红线所连接的匹配，不仅是一个完全匹配，还是一个完美匹配

5.最大匹配问题

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

6.最优匹配

带权二分图的权值最大的完全匹配称为最佳匹配，要注意的是，二分图的最优匹配不一定是二分图的最大权匹配。

实质上最优匹配问题就是求边权和最大的最大匹配问题。

求解技巧：可以添加一些权值为 0 的边，使得最优匹配和最大权匹配统一起来。 

【相关算法】

• 二分图判定：点击这里
• 匈牙利算法：点击这里
• KM 算法：点击这里

其中，匈牙利算法常用于求最大匹配数、最小点覆盖数、最大独立集、最小路径覆盖数等；KM 算法常用于求最优匹配、边权和最小的完全匹配、最小有向环覆盖权值和、优先用原匹配边构建的最优匹配等。

【例题】

1.二分图判定

1. Catch（HDU-3478）(二分图判定)：点击这里
2. The Accomodation of Students（HDU-2444 ）(二分图判定+最大匹配)：点击这里
3. Arbiter（HDU-3118）(二分图充要条件删边构图+二进制状态枚举)：点击这里

2.匈牙利算法

1）最大匹配

1. COURSES（POJ-1469）：点击这里
2. The Perfect Stall（POJ-1274）：点击这里
3. Selecting Courses（POJ-2239）：点击这里
4. Gopher II（POJ-2536 ）：点击这里
5. 过山车（HDU-2063）：点击这里
6. Ollivanders: Makers of Fine Wands since（HDU-1179）：点击这里
7. Factors and Multiples（LightOJ-1149）：点击这里
8. Fire Net（HDU-1045）(行列缩点建图)：点击这里
9. BATtle ships（HDU-5093）(行列缩点建图)：点击这里
10. Card Game Cheater（HDU-1528）(最大匹配+贪心)：点击这里
11. 棋盘游戏（HDU-1281）(最大匹配+关键边)：点击这里
12. Jimmy’s assignment（HDU 1845）(三正则图+二分匹配)：点击这里
13. Uncle Tom's Inherited Land（HDU-1507）(4个方向查找匹配)：点击这里

2）最大独立集

1. Kindergarten（POJ-3692）：点击这里
2. guardian of Decency（POJ-2771）：点击这里
3. Cat VS Dog（HDU-3829）：点击这里

   同题：Cat vs. Dog（HDU-2768）：点击这里

4. Girls and Boys（POJ-1466）(最大独立集+翻倍图)：点击这里

   同题：Girls and Boys（HDU1068）：点击这里

3）最小点覆盖数

1. Asteroids（POJ-3041）：点击这里
2. Machine Schedule（POJ-1325）：点击这里

   同题：Machine Schedule（HDU-1150）：点击这里

3. Strategic Game（HDU-1054）(最小点覆盖数+翻倍图)：点击这里
4. 50 years, 50 colors（HDU-1498）(最小点覆盖数+桶排)：点击这里

4）最小路径覆盖

1. Dolls（HDU-4160）：点击这里
2. robots（POJ-1548）：点击这里
3. air Raid（POJ-1422）：点击这里
4. Matrix（HDU-2119）：点击这里
5. Taxi Cab Scheme（POJ-2060）：点击这里
6. Repairing Company（POJ-3216）(最小路径覆盖+Floyd)：点击这里
7. Harry Potter and the Present II（HDU-3991）(最小路径覆盖+Floyd)：点击这里

3.KM 算法

1. 奔小康赚大钱（HDU-2255）：点击这里
2. Interesting Housing Problem（HDU-2426）：点击这里
3. Special Fish（HDU-3395）：点击这里
4. Going Home（POJ-2195）(边权和最小的完全匹配)：点击这里
5. Chocolate（HDU-2282）(环的边权和最小的完全匹配)：点击这里
6. Mining Station on the Sea（HDU-2448）(Floyd+边权和最小的完全匹配)：点击这里
7. Cyclic Tour（HDU-1853）(有向环覆盖+边权和最小的完全匹配)：点击这里
8. A new Graph Game（ HDU-3435）(有向环覆盖+边权和最小的完全匹配)：点击这里
9. Assignment（HDU-2853）(优先使用原边构建优先匹配)：点击这里
10. My Brute（HDU-3315）(优先使用原边构建优先匹配)：点击这里

相关阅读

二分图详解----匈牙利算法+km算法+ Gale-Shapley---婚

先介绍一下基本概念 以下基本概念转自其他的博客，不是原创 二分图：简单来说，如果图中点可以被分为两组，并且使得所有边都跨越组的边