二分图的基本概念+二分图的最大匹配问题（匈牙利算法）

时间：2021-12-04 05:55:16

       今天学了二分图的最大匹配，其中的匈牙利算法。。哦不，其实远不止这个，还有后面的一系列KM、开花树啊什么的算法。反正又是一个异常懵逼的一天。。。

我觉得应该是上课前没有稍微预习一下这个算法是什么，了解个大概，导致上课总是老师讲到后面了，我却还在纠结前面的内容。。可以当作经验教训。

       明天他们要去杭电打团体赛。。也不知道怎么的，当时明明跟老师说了，却没报上名。。。这样也好，最近太累了需要多休息，明天还可以把今天讲的几个算法。自己好好深入研究下。编程嘛，无它，唯手熟尔二分图的基本概念+二分图的最大匹配问题（匈牙利算法）下面就一步步来，先把最基础的二分图的最大匹配问题搞懂。。

       我先把二分图的基本概念放这儿，改天深入剖析一下二分图，再把概念挪过去

      

           1.二分图又称作二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。由定义可知，二分图没有自回路；零图，平凡图可以看成是特殊的二分图。

二分图的基本概念+二分图的最大匹配问题（匈牙利算法）


2.定义：在二分图G=<V1,E,V2>中，若V1中的每个结点与V2中的每个结点都有且仅有一条边相关联，则称二分图G为完全二分图，记为Ki,j，其中i=|V1|,j=|V2|.

           

3.判断是否为二分图的方法：①定义法，②定理：无向图G=<V,E>为二分图的充要条件是G的所有回路的长度均为偶数。

下面进入今天的正题的一些基本概念

1 最大匹配
    在G的一个子图M中，M的边集中的任意两条边都不依附于同一个顶点，则称M是一个匹配。选择这样的边数最大的子集称为图的最大匹配问题,最大匹配的边数称为最大匹配数.如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。如果在左右两边加上源汇点后，图G等价于一个网络流，二分图的基本概念+二分图的最大匹配问题（匈牙利算法）最大匹配问题可以转为最大流的问题。解决此问的匈牙利算法的本质就是寻找最大流的增广路径。上图中的最大匹配如下图红边所示：

                                                   二分图的基本概念+二分图的最大匹配问题（匈牙利算法）

2 最优匹配

最优匹配又称为带权最大匹配，是指在带有权值边的二分图中，求一个匹配使得匹配边上的权值和最大。一般X和Y集合顶点个数相同，最优匹配也是一个完备匹配，即每个顶点都被匹配。如果个数不相等，可以通过补点加0边实现转化。一般使用KM算法解决该问题。

 

3 最小覆盖

二分图的最小覆盖分为最小顶点覆盖和最小路径覆盖：

①最小顶点覆盖是指最少的顶点数使得二分图G中的每条边都至少与其中一个点相关联，二分图的最小顶点覆盖数=二分图的最大匹配数；

②最小路径覆盖也称为最小边覆盖，是指用尽量少的不相交简单路径覆盖二分图中的所有顶点。二分图的最小路径覆盖数=|V|-二分图的最大匹配数；


4 最大独立集

    最大独立集是指寻找一个点集，使得其中任意两点在图中无对应边。对于一般图来说，最大独立集是一个NP完全问题，对于二分图来说最大独立集=|V|-二分图的最大匹配数。如下图中黑色点即为一个最大独立集：

                                                    二分图的基本概念+二分图的最大匹配问题（匈牙利算法）


下面来进行匈牙利算法


初始时最大匹配为空
while 找得到增广路径
    do 把增广路径加入到最大匹配中去

可见和最大流算法是一样的。但是这里的增广路径就有它一定的特殊性，下面我来分析一下。
（注：匈牙利算法虽然根本上是最大流算法，但是它不需要建网络模型，所以图中不再需要源点和汇点，仅仅是一个二分图。每条边也不需要有方向。）

二分图的基本概念+二分图的最大匹配问题（匈牙利算法）

图1是我给出的二分图中的一个匹配：［1，5］和［2，6］。图2就是在这个匹配的基础上找到的一条增广路径：3->6->2->5->1->4。我们借由它来描述一下二分图中的增广路径的性质：

(1)有奇数条边。
(2)起点在二分图的左半边，终点在右半边。
(3)路径上的点一定是一个在左半边，一个在右半边，交替出现。（其实二分图的性质就决定了这一点，因为二分图同一边的点之间没有边相连，不要忘记哦。）
(4)整条路径上没有重复的点。
(5)起点和终点都是目前还没有配对的点，而其它所有点都是已经配好对的。（如图1、图2所示，［1，5］和［2，6］在图1中是两对已经配好对的点；而起点3和终点4目前还没有与其它点配对。）
(6)路径上的所有第奇数条边都不在原匹配中，所有第偶数条边都出现在原匹配中。（如图1、图2所示，原有的匹配是［1，5］和［2，6］，这两条配匹的边在图2给出的增广路径中分边是第2和第4条边。而增广路径的第1、3、5条边都没有出现在图1给出的匹配中。）
(7)最后，也是最重要的一条，把增广路径上的所有第奇数条边加入到原匹配中去，并把增广路径中的所有第偶数条边从原匹配中删除（这个操作称为增广路径的取反），则新的匹配数就比原匹配数增加了1个。（如图2所示，新的匹配就是所有蓝色的边，而所有红色的边则从原匹配中删除。则新的匹配数为3。）

不难想通，在最初始时，还没有任何匹配时，图1中的两条灰色的边本身也是增广路径。因此在这张二分图中寻找最大配匹的过程可能如下：

(1)找到增广路径1->5，把它取反，则匹配数增加到1。
(2)找到增广路径2->6，把它取反，则匹配数增加到2。
(3)找到增广路径3->6->2->5->1->4，把它取反，则匹配数增加到3。
(4)再也找不到增广路径，结束。

当然，这只是一种可能的流程。也可能有别的找增广路径的顺序，或者找到不同的增广路径，最终的匹配方案也可能不一样。但是最大匹配数一定都是相同的。

对于增广路径还可以用一个递归的方法来描述。这个描述不一定最准确，但是它揭示了寻找增广路径的一般方法：
“从点A出发的增广路径”一定首先连向一个在原匹配中没有与点A配对的点B。如果点B在原匹配中没有与任何点配对，则它就是这条增广路径的终点；反之，如果点B已与点C配对，那么这条增广路径就是从A到B，再从B到C，再加上“从点C出发的增广路径”。并且，这条从C出发的增广路径中不能与前半部分的增广路径有重复的点。
比如图2中，我们要寻找一条从3出发的增广路径，要做以下3步：
(1)首先从3出发，它能连到的点只有6，而6在图1中已经与2配对，所以目前的增广路径就是3->6->2再加上从2出发的增广路径。
(2)从2出发，它能连到的不与前半部分路径重复的点只有5，而且5确实在原匹配中没有与2配对。所以从2连到5。但5在图1中已经与1配对，所以目前的增广路径为3->6->2->5->1再加上从1出发的增广路径。
(3)从1出发，能连到的不与自已配对并且不与前半部分路径重复的点只有4。因为4在图1中没有与任何点配对，所以它就是终点。所以最终的增广路径是3->6->2->5->1->4。

但是严格地说，以上过程中从2出发的增广路径（2->5->1->4）和从1出发的增广路径（1->4）并不是真正的增广路径。因为它们不符合前面讲过的增广路径的第5条性质，它们的起点都是已经配过对的点。我们在这里称它们为“增广路径”只是为了方便说明整个搜寻的过程。而这两条路径本身只能算是两个不为外界所知的子过程的返回结果。
显然，从上面的例子可以看出，搜寻增广路径的方法就是DFS，可以写成一个递归函数。当然，用BFS也完全可以实现。

至此，理论基础部份讲完了。但是要完成匈牙利算法，还需要一个重要的定理：

如果从一个点A出发，没有找到增广路径，那么无论再从别的点出发找到多少增广路径来改变现在的匹配，从A出发都永远找不到增广路径。

要用文字来证明这个定理很繁，话很难说，要么我还得多画一张图，我在此就省了。其实你自己画几个图，试图举两个反例，这个定理不难想通的。（给个提示。如果你试图举个反例来说明在找到了别的增广路径并改变了现有的匹配后，从A出发就能找到增广路径。那么，在这种情况下，肯定在找到别的增广路径之前，就能从A出发找到增广路径。这就与假设矛盾了。）
有了这个定理，匈牙利算法就成形了。如下：

初始时最大匹配为空
for 二分图左半边的每个点i
    do 从点i出发寻找增广路径。如果找到，则把它取反（即增加了总了匹配数）。
如果二分图的左半边一共有n个点，那么最多找n条增广路径。如果图*有m条边，那么每找一条增广路径（DFS或BFS）时最多把所有边遍历一遍，所花时间也就是m。所以总的时间大概就是O（n * m）。


代码实现

还是用向来擅长的STL实现了 

#include <cstdio>
#include <string.h>
#include <vector>
using namespace std;
int const MAX = 10000;
vector<int> G[MAX];
int vis[MAX];
int link[MAX];//代表当前状态Y中与X相连的点（即d[y] = x）
int n, m;//n为X集合点数，m为Y集合点数（这里默认点的序号为X到Y依次递增）

int can(int t)//这一个t保证它是X中的点
{
    for(int i = 0; i < G[t].size(); i++){//从Y中的每一点开始找
        int tmp = G[t][i];
        if(!vis[tmp]){//如果这点没有被前面几次找过
            vis[tmp] = 1;
            if(link[tmp] == -1 || can(link[tmp])){//这里寻找增广路径的结束条件就是找到Y中未被配对过的点，如果这点被配对过，那么就从这点配对的X中的点进行新一轮的can()
               link[tmp] = t;
               return 1;
            }
        }
    }
    return 0;
}

int maxmatch()
{
    int num = 0;
    for(int i = 1; i <= n; i++){
        memset(vis, 0, sizeof(vis));
        if(can(i)){
            num++;
        }
    }
    return num;
}

int main()
{
    while(scanf("%d %d", &n, &m) != EOF){
        for(int i = 1; i <= n; i++)
            G[i].clear();
        memset(link, -1, sizeof(link));
        int s;
        scanf("%d", &s);
        while(s--){
            int a, b;//表示X中的a与Y中的b相连
            scanf("%d %d", &a, &b);//假设输入的点X和Y分开输入（都是从1开始）
            G[a].push_back(b+n);
            G[b+n].push_back(a);//由于是无向图
        }
        printf("%d\n", maxmatch());
    }
    return 0;
}


接下来是一些比较水，一看就知道用最大匹配或者是它的一些小变种来解决的题目把


第一题。。是直接找最大匹配数目的题目。。。找到最大匹配数目，然后与n相比较，如果一样，输出YES，otherwise，输出NO


COURSES

Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 20759   Accepted: 8191

Description

Consider a group of N students and P courses. Each student visits zero, one or more than one courses. Your task is to determine whether it is possible to form a committee of exactly P students that satisfies simultaneously the conditions:

  • every student in the committee represents a different course (a student can represent a course if he/she visits that course)
  • each course has a representative in the committee

Input

Your program should read sets of data from the std input. The first line of the input contains the number of the data sets. Each data set is presented in the following format:

P N
Count1 Student 1 1 Student 1 2 ... Student 1 Count1
Count2 Student 2 1 Student 2 2 ... Student 2 Count2
...
CountP Student P 1 Student P 2 ... Student P CountP

The first line in each data set contains two positive integers separated by one blank: P (1 <= P <= 100) - the number of courses and N (1 <= N <= 300) - the number of students. The next P lines describe in sequence of the courses �from course 1 to course P, each line describing a course. The description of course i is a line that starts with an integer Count i (0 <= Count i <= N) representing the number of students visiting course i. Next, after a blank, you抣l find the Count i students, visiting the course, each two consecutive separated by one blank. Students are numbered with the positive integers from 1 to N.
There are no blank lines between consecutive sets of data. Input data are correct.

Output

The result of the program is on the standard output. For each input data set the program prints on a single line "YES" if it is possible to form a committee and "NO" otherwise. There should not be any leading blanks at the start of the line.

Sample Input

2
3 3
3 1 2 3
2 1 2
1 1
3 3
2 1 3
2 1 3
1 1

Sample Output

YES
NO

代码

#include<cstdio>
#include <string.h>
using namespace std;
int mp[500][500];
int n, m;//n表示课程数，m表示学生数
int link[400];//记录当前与y节点相连的x的节点
int vis[400];
int can(int t)
{
    int i;
    for(i = n + 1; i <= n + m; i++){
        if(!vis[i] && mp[t][i]){
            vis[i] = 1;
            if(link[i] == -1 || can(link[i])){
                link[i] = t;
                return 1;
            }
        }
    }
    return 0;
}
int maxmartch()
{
    int num = 0;
    memset(link, 0xff, sizeof(link));
    for(int i = 1; i <= n; i++){
        memset(vis, 0, sizeof(vis));
        if(can(i))
            num++;
    }
    return num;
}
int main()
{
    int cases;
    scanf("%d", &cases);
    while(cases--){
        memset(mp, 0, sizeof(mp));
        scanf("%d %d", &n, &m);
        for(int i = 1; i <= n; i++){
            int s;
            scanf("%d", &s);
            while(s--){
                int k;
                scanf("%d", &k);
                mp[i][k+n] = mp[k+n][i] = 1;
            }
        }
        if(maxmartch() == n)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

未完待续。。。


标签：

相关文章