二分图

二分图的判定：不存在边数为奇数的环，我们用反正法来证明，已知二分图的每一条边都是横跨两个顶点集合的，因为最终会形成环，所以从A集合走到B集合，必然会有一条边从B集合走到A集合中的点，知道最后走回到A集合中的原点。有偶数条边

染色法判断是否为二分图

第一种是BFS,我们每层之间的点颜色不一样

 1 #include<iostream>
 2 #include<queue>
 3 #include<cstring>
 4 using namespace std;
 5 int head[MAX_],cnt=0;
 6 struct Edge{
 7     int from,to,next;
 8 }; 
 9 void AddEdge(int f,int t){
10     e[++cnt].from=f;
11     e[cnt].to=t;
12     e[cnt].next=head[f];
13     head[f]=cnt;
14 }
15 int co[MAX_];
16 bool BFS(int s)
17 {
18     memset(co,0,sizeof(co));
19     co[s]=1;
20     queue<int> Q;
21     Q.push(s);
22     while(!Q.empty()){
23         int x=Q.front() ;Q.pop();
24         for(int i=head[x];i;i=e[i].next){
25             if(!co[e[i].to]){
26                 co[e[i].to]=3-co[x];
27                 Q.push(e[i].to); 
28             }
29             else if(co[e[i].to]+co[x]==3) continue;
30             else return false;
31         }
32     } 
33     return true;
34 }

第二种方法是DFS,遍历每一条路，确保都是满足交叉染色条件的，我们记录染色块的颜色，用记忆化搜索来降低复杂度

 1 bool DFS(int s,int c){
 2     co[s]=c;
 3     for(int i=head[s];i;i=e[i].next){
 4         int v=e[i].to;
 5         if(!co[v]&&DFS(v,3-c))
 6             continue;
 7         else if(co[v]+c==3) continue;
 8         else return false;
 9     }
10     return true;
11 }

概念：

　　二分图的最小覆盖顶点

最小覆盖顶点指的是要求用最少的顶点，使得每一条边都至少和其中的一个顶点关联；

Knoig定理：二分图的最小覆盖顶点数等于二分图的最大匹配数。

证明：首先容易知道不存在一条边与已知的增广路完全没有没有相关点，如果存在，匹配数必然可以再次增加1。每一条边都与已知的增广路存在一个或者两个相关点，所以会存在这样两种情况AB两个集合，一种是1对多，则会存在一个匹配，所有边的覆盖点选择为起点这条增广路的起点，如果是多对一而形成的一条增广路，所以边的覆盖点选择这条增广路的会点。

最大匹配数=最大流=最小割=最小点集覆盖

DAG图最小路径覆盖

用尽量少的不相交的简单路径覆盖有向无环图G的所有顶点，这就是DAG图的最小路径覆盖问题。

结论：DAGt图的最小路径覆盖数=节点数(s)-最大匹配数（m）

证明：这里的证明需要证明上一个定理的结论，在证明了其他所有边都和增广路共用一个起点或者终点的时候，m个匹配路径可以覆盖2m个点，而且不存在另外的边能覆盖两个点，如果题目有解，剩下的每一个顶点都用要一条新的边覆盖。

二分图的最大独立集

最大独立集问题：在N个点的图G中，使这m个点两两之间没有边，求m的最大值；

结论：二分图的最大独立集数=节点数-最大匹配数（根据前两歌证明中的结论，自行推导）

匈牙利算法：

增广路定理，我们把边分为两类：一类是匹配边，一类是非匹配边，一条完整的增广路应该是，非匹配边，匹配边，非匹配边，匹配边...交叉进行，而且最后一条一定是非匹配变，所以非匹配边会大1，这个就类似，一群男生一群女生配对，每个男生有多个选择，首先第一个选择，当第一个选择已经被人匹配时，我们考虑一下他的原配能不能换一个女生。我们很容易发现，每个男生是依次去匹配能够匹配的女生，所以不会回头再去访问。

#include<iostream>
#include<cstring>
using namespace std;
struct Edge{
    int to,next;
}e[maxn];
bool vis[maxn];
const int MAX_=;
int link[MAX_];
int head[maxn],cnt;
int n,m;
void AddEdge(int f,int t){
    e[++cnt].to=t;
    e[cnt].next=head[f];
    head[f]=cnt;
}
bool DFS(int s)
{
    for(int i=head[s];i;i=e[i].next){
        if(vis[i]) continue;
        vis[i]=true; //已经考虑过这个女生
        int v=e[i].to;
        if(match[v]==-1||DFS(match[v]))
        {
            match[v]=s;
            return true;
        }
    }
    return false;
}
int hungary(){
    int ans=0;
    for(int i=0;i<MAX_;i++) match[i]=-1;
    memset(vis,0,sizeof(vis));
    for(int i=0;i<n;i++)
        if(DFS(i))
            ans++;
    return ans;
}

匈牙利算法

 1 struct  XYL{
 2     int n,m;
 3     int map[110][110],linker[110];
 4     bool vis[110];
 5     
 6     XYL(int n,int m){
 7         this->n=n;this->m=m;
 8         memset(map,0,sizeof(map));
 9         for(int i=0;i<110;i++) linker[i]=-1;
10     }
11     
12     void Addedge(int f,int t){
13         map[f][t]=1;
14     }
15     
16     bool DFS(int u){
17         int v;
18         for(int v=1;v<m;v++){
19             if(map[u][v]&&!vis[v]){
20                 vis[v]=true;
21                 if(linker[v]==-1||DFS(linker[v])){
22                     linker[v]=u;
23                     return true;
24                 }
25             }
26         }
27         return false;
28     }
29     
30     int hungary(){
31         int u,ans=0;
32         for(u=1;u<n;u++){
33             memset(vis,false,sizeof(vis));
34             if(DFS(u)) ans++; 
35         }
36         return ans;
37     }
38     
39 };