二分图总结

前言
二分图总结
- 二分图基本概念
- - 什么是二分图？
  - 二分图图的性质
  - 染色法判断是否有奇环
- 二分图匹配算法
- - 匹配概念
  - 匈牙利算法
  - 二分图最小点覆盖
  - - 2，3号边
    - 1，4号边
    - 小结
  - 二分图最小边覆盖
  - 二分图最小路径覆盖
  - 二分图最大独立集

前言

这篇文章是作者在学完二分图的总结，由于作者比较弱，可能只总结了一些皮毛，如果有错误，请大佬指正

二分图总结

二分图基本概念

什么是二分图？

二分图就像名字说的那样，将一幅图二分了，分成两个点集(U,V)，并且每一条边都连接着UV**（重！！！：二分图任意点集的点不能连向此点集的点，如U点集的**

点不能连接U点集的点）。

二分图图的性质

二分图有一个性质：二分图没有奇环。

在一幅图中不能含有奇环，有就说明此图不是二分图。

为什么呢？若含有奇环，那么以相邻两条边表示这两个点属于不同的点集，但是若跑完整个奇

环后，就会出现两个属于相同的点集的两个点，这样的话不就不符合相同点集的点不能相连
了嘛。

染色法判断是否有奇环

染色法其实就是将一个图，分成UVUVUV…这样子，相当于将图分成两个不同的点集，也就是

相邻点不属于同一点集，并进行编号，若冲突表示相邻点的点集相同了则不是二分图。

举个例子：

在这里插入图片描述

1和2相邻，故不同，标称U，V。2和3 相邻，不同，但2已经是V，所以3是U。1和3相邻，故不同，但实际上1和3是相同的，矛盾，不是二分图。

那么代码可以怎么写呢？

我们采用奇偶染色(染色法），就是121212…变换就可以直接用3去减相邻的，比如3-1=2，3-2=1，相当于直接改变了，且改变了奇偶性，所以叫奇偶染色。

bool dfs(int u, int f)
{for (int i = head[u]; i != -1; i = nxt[i]){int v = to[i];if (v != f){if (!belong[v]){belong[v] = 3 - belong[u];if (!dfs(v, u)) return false;}else if (belong[v] == belong[u]) return false;}}return true;
}

二分图样貌展示：

在这里插入图片描述

二分图匹配算法

匹配概念

匹配是指一些边的集合，称作匹配，而这些边指的是二分图两边的点集相连的边（注意：匹配的任意两个边的没有公共点！！！）。

一个匹配中的边的集合中的边，都叫匹配边，如果不在次集合内的边叫非匹配边；而匹配边的两头的点的集合叫做匹配点，也叫盖点，没有在此点集内的，叫未盖点（非匹配点）。

若有一种匹配，它是所有匹配中边的数量最多的，那么我们称其为最大匹配。

二分图中还有一个种匹配，叫完美匹配：二分图中的某个匹配，使得所有点都成了盖点，那么此时就是完美匹配。

在这里插入图片描述

匈牙利算法

匈牙利算法本质是一个找增广路的一个算法，因为若出现一条增广路，当前匹配A，肯定会到达匹配B，且B的匹配边的个数是匹配A加1，换句话说，出现增广路，那么我们记录的最大匹配的个数加1。

那什么是增广路呢？

首先增广路肯定是条路径对吧，增广路就是指从左边任意一点到右边任
意一点的路径（注：增广路的以右边未盖点结尾），如这样（U为左点集，V为右点集）：

U-V-U-V…-U-V的交错路径。

为什么找到增广路最大匹配的个数就加1呢？

一旦出现增广路，路径上的点就会更新新的左或
右的点（换句话说就是更换一下另一半的匹配点），而当更换完成另一半后，自然会空出一个位置，而又因为它是一条路径，自然是相通的，所以那个位置就可以给上面的一个点去匹配，那么因为最后的点是未盖点，所以此时这条路径上的匹配就会增加。

举个例子子：如下图是一个增广路，如果没有下面一条边，只能匹配一条边，如果加上了呢？你会发现无论上面的匹配边是哪条，在加上最下面的边之后总会增加匹配（最上面的一条是匹配边得话，左边的第二个点可直接匹配右下角的点，匹配边是第二条的话，也能更换成最下面的匹配边，然后上面又能匹配了）

那么代码该如何写呢？

我们可以采用dfs搜索的写法，每一次枚举左边点集，然后看看右边点集是否构成增广路，不断执行下去。

#define mem(a,b) memset(a,b,sizeof(a))
int vis[N];
int px[N], py[N];
void add(int a, int b)
{to[++E] = b;nxt[E] = head[a];head[a] = E;
}
bool dfs(int x)
{for (int i = head[x]; ~i; i = nxt[i]){int v = to[i];if(!vis[v]){vis[v] = 1;if(py[v] == -1 || dfs(py[v])) //如果到尽头或下面找到尽头了，更新{py[v] = x;px[x] = v;return true;}}return false;
}
void work(int n)
{mem(px, -1);mem(py, -1);for (int i = 1; i <= n; ++i){	mem(vis, 0);if(dfs(i)) ++ret;}
}