[ 图论 ]二分图判定及其匹配、最小点覆盖，最大独立集，（基础+提高）-六虎

在处理断定和匹配使命之前，我想咱们应该先了解什么是二分图

界说

二分图，又称二部图，英文名叫 Bipartite graph。

二分图是什么？节点由两个调集组成，且两个调集内部没有边的图。

换言之，存在一种计划，将节点划分红满意以上性质的两个调集。 $−(OIWiki)-(OI\ Wiki)$

那么首要咱们先看一个一般的图

上图用了 $6$ 个点， $6$ 条边。这样看起来没什么特别的对吧，咱们将他做一下调整。

此图和上边的是等价的，但是咱们将他们分红了两个调集 $A, B$ ，而且每个调集内部都没有边相连，这种图便是二分图。

了解了什么是二分图，我想咱们能够开端咱们要讲的断定了，现在你能够动手画一画，是不是一切的图都是二分图呢？显然这是不或许的，但这其间又有什么联系吗？比如现在我给出这样一个图

你能将他分红二分图吗？

当咱们做这件事的时分，会发现不管怎样分，点 $5$ 必定会和 $0$ 或 $1$ 在一个调会集，为什么？由于图中存在奇数环，这时分咱们得出了榜首个定论： $当图中有奇数环时，他一定不是二分图, 反之没有奇数环的图一定是二分图$

咱们多举一个例子：

图中存在长度为 $4 和 8$ 的环，咱们现在将他变成二分图

这是非常容易办到的（

接下来咱们介绍怎么去断定一个图是不是二分图。我这儿给出的是一个常用的算法 $染色法判断二分图$

原理：咱们能够将两个调会集的点给一个色彩，例如： $A$ 调会集的点咱们都染成赤色， $B$ 调会集的点咱们都染成黑色，咱们开一个 $color[]color[\ ]$ 数组来记录每个点的色彩，起始，咱们遍历每个点，假如没有被染色，咱们就将他染成赤色，然后将与他直接相连的点悉数染成黑色，同理当咱们将这个点染成黑色后，咱们就要将与他直接相连的一切点染成赤色，在这期间假如染色失利，那么就不是二分图，什么时分会呈现染色失利呢？当咱们染完一个点后，在染他的一切相邻的点的时分发现有一个点的色彩和他相同，也便是下面图中的状况.

$1$ 号点发现他的相邻点 $0$ 号点也是赤色，那么这样就不行了对吧，就算咱们把 $1$ 号点染成黑色，那么也会发现他的相邻点 $5$ 也是黑色，这时分就只能宣告：染色失利，图不是二分图

例题：染色法断定二分图

给定一个 $n$ 个点 $m$ 条边的无向图，图中或许存在重边和自环。

请你判别这个图是否是二分图。

输入格局

榜首行包括两个整数 $n$ 和 $m$ 。

接下来 $m$ 行，每行包括两个整数 $u$ 和 $v$ ，表明点 $u$ 和点 $v$ 之间存在一条边。

输出格局

假如给定图是二分图，则输出 $Y e s$ ，否则输出 $N o$ 。

数据规模

$1≤n,m≤10^5$

输入样例：

输出样例：

Yes

这个题是染色算法的板子题,下面给出完好代码：

#include <bits/stdc++.h>
using namespace std;
//------邻接表存边
const int N=1e5+10,M=2*N;
int h[N],e[M],ne[M],idx;
int color[N];
void add(int a,int b)
{
	e[idx]=b;
	ne[idx]=h[a];
	h[a]=idx++;
}
//-------
//-------染色法判别二分图
bool dfs(int u,int c)
{
	color[u]=c;
	for(int i=h[u];i!=-1;i=ne[i])
	{
		int j=e[i];
		if(!color[j])//相邻点没有色彩，就染成不同的色彩
		{
			if(!dfs(j,3-c))return false;
		}else if(color[j]==color[u])return false;//相邻点与自身的色彩相同
	}
	return true;//将相邻点悉数染色成功，只能说明这个点与他的相邻点没有产生对立
}
//--------
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	//----读入无向边
	memset(h,-1,sizeof h);
	int n,m;cin>>n>>m;
	while(m--)
	{
		int a,b;cin>>a>>b;
		add(a,b);add(b,a);
	}
	//-----
	bool f=true;
	for(int i=1;i<=n;i++)//开端染色
	{
		if(!color[i])
		{
			if(!dfs(i,1))f=false;//假如有一个点染色失利，就宣告失利
		}
	}
	if(f)cout<<"Yes";else cout<<"No";
	return 0;
}

到这儿，我相信你现已对怎么断定一个图是不是二分图有所了解了，那么这是远远不够的，由于二分博学多才（

咱们将学习下一个知识点：二分图的最大匹配

这儿咱们不引进所谓的增广路概念，他对我来说比较笼统 $h h$ ，所以咱们直接用文言的意思翻译一下，什么是最大匹配

~~转载知乎@青烟~~

他的最大匹配数便是 $3$ ,由于有三对点完成了匹配,别离是： ${x_1,y_4\},\{x_2,y_2\},\{x_3,y_3\}$

所以最大匹配数便是一个二分图中，从两个调会集各拿出一个点，组成一对的最大对数。

了解了概念，咱们怎么求呢？这儿给咱们介绍一种算法：匈牙利算法

咱们用一个例题来说明：二分图的最大匹配

给定一个二分图，其间左半部包括 $n_1$ 个点（编号 $1∼n_1$ ），右半部包括 $n_2$ 个点（编号 $1∼n_2$ ），二分图共包括 $m$ 条边。

数据确保恣意一条边的两个端点都不或许在同一部分中。

请你求出二分图的最大匹配数。

二分图的匹配：给定一个二分图 $G$ ，在 $G$ 的一个子图 $M$ 中， $M$ 的边集 ${E\}$ 中的恣意两条边都不依附于同一个极点，则称 $M$ 是一个匹配。

二分图的最大匹配：一切匹配中包括边数最多的一组匹配被称为二分图的最大匹配，其边数即为最大匹配数。

输入格局

榜首行包括三个整数 $n_1、 n_2 和 m$ 。

接下来 $m$ 行，每行包括两个整数 $u$ 和 $v$ ，表明左半部点会集的点 $u$ 和右半部点会集的点 $v$ 之间存在一条边。

输出格局

输出一个整数，表明二分图的最大匹配数。

数据规模

$1≤n_1,n_2≤500$ $1 \leq u \leq n 1,$ $1 \leq v \leq n 2,$ $1≤m≤10^5$

输入样例：

输出样例：

#include <bits/stdc++.h>
using namespace std;
//-------读入边
const int N=510,M=1e5+10;
int h[N],e[M],ne[M],idx;
void add(int a,int b)
{
	e[idx]=b;
	ne[idx]=h[a];
	h[a]=idx++;
}
//---------
//--------匈牙利算法
bool st[N];
int match[N];
bool find(int u)
{
	for(int i=h[u];i!=-1;i=ne[i])
	{
		int j=e[i];
		if(st[j])continue;
		st[j]=true;//咱们现占下这个匹配者
		if(!match[j]||find(match[j]))
		//假如右边的点 j 还没有匹配,或许他的匹配者能够换一个（
		{
			match[j]=u;
			return true;
		}
	}
	return false;
}
//--------
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	//---读边
	memset(h,-1,sizeof h);
	int n1,n2,m;cin>>n1>>n2>>m;
	while(m--)
	{
		int a,b;cin>>a>>b;
		add(a,b);
	}
	//----
	int num=0;
	for(int i=1;i<=n1;i++)//从左面调集开端匹配右边
	{
		memset(st,0,sizeof st);
		if(find(i))num++;
	}
	cout<<num;//输出匹配数量
	return 0;
}

到此，咱们二分图最根底的两个操作现已介绍完了，接下来咱们来进行提高部分，我会用标题来进行一些知识点的介绍。

1、染色法+二分关押罪犯

$S$ 城现有两座监狱，一共关押着 $N$ 名罪犯，编号别离为 $1 \sim N$ 。

他们之间的联系天然也极不调和。

许多罪犯之间乃至积怨已久，假如客观条件具有则随时或许爆发抵触。

咱们用“怨气值”（一个正整数值）来表明某两名罪犯之间的仇视程度，怨气值越大，则这两名罪犯之间的积怨越多。

假如两名怨气值为 $c$ 的罪犯被关押在同一监狱，他们俩之间会产生抵触，并形成影响力为 $c$ 的抵触事情。

每年年末，警察局会将本年内监狱中的一切抵触事情按影响力从大到小排成一个列表，然后上签到 $S$ 城 $Z$ 市长那里。

公事繁忙的 $Z$ 市长只会去看列表中的榜首个事情的影响力，假如影响很坏，他就会考虑撤换警察局长。

在具体调查了 $N$ 名罪犯间的对立联系后，警察局长觉得压力巨大。

他准备将罪犯们在两座监狱内重新分配，以求产生的抵触事情影响力都较小，从而保住自己的乌纱帽。

假定只需处于同一监狱内的某两个罪犯间有仇视，那么他们必定会在每年的某个时分产生抵触。

那么，应怎么分配罪犯，才能使 $Z$ 市长看到的那个抵触事情的影响力最小？这个最小值是多少？

输入格局

榜首行为两个正整数 $N$ 和 $M$ ，别离表明罪犯的数目以及存在仇视的罪犯对数。

接下来的 $M$ 行每行为三个正整数 $a_j，b_j，c_j$ ，表明 $a_j$ 号和 $b_j$ 号罪犯之间存在仇视，其怨气值为 $c_j$ 。

数据确保 $1≤a_j<b_j<N,0<c_j≤10^9$ 且每对罪犯组合只呈现一次。

输出格局

输出共 $1$ 行，为 $Z$ 市长看到的那个抵触事情的影响力。

假如本年内监狱中未产生任何抵触事情，请输出 $0$ 。

数据规模

$N \leq 20000, M \leq 100000$

输入样例：

输出样例：

时刻复杂度： $O ((N + M) l o g C)$ 将罪犯当做点，罪犯之间的仇视联系当做点与点之间的无向边，边的权重是罪犯之间的仇视值。那么原问题变成：将一切点分红两组，使得各组内边的权重的最大值尽或许小。

咱们在 $0,10^9]$ 之间枚举最大边权 $l i m i t$ ，当 $l i m i t$ 固定之后，剩余的问题便是：

判别能否将一切点分红两组，使得一切权值大于 $l i m i t$ 的边都在组间，而不在组内。也便是判别由一切点以及一切权值大于 $l i m i t$ 的边构成的新图是否是二分图。判别二分图能够用染色法，时刻复杂度是 $O (N + M)$ ，其间 $N$ 是点数， $M$ 是边数 — yxc

#include <bits/stdc++.h>
using namespace std;
//-------读边
const int N=2e4+10,M=2e5+10;
int h[N],e[M],ne[M],w[M],idx;
int n,m;
void add(int a,int b,int c)
{
	e[idx]=b;
	w[idx]=c;
	ne[idx]=h[a];
	h[a]=idx++;
}
//-------
//-------染色法判别二分图
int color[N];
bool dfs(int u,int c,int mid)
{
	color[u]=c;
	for(int i=h[u];i!=-1;i=ne[i])
	{
		int j=e[i];
		if(w[i]<=mid)continue;
		if(!color[j])
		{
			if(!dfs(j,3-c,mid))return false;
		}else if(color[j]==color[u])return false;
	}
	return true;
}
bool check(int mid)//二分断定
{
	memset(color,0,sizeof color);
	for(int i=1;i<=n;i++)
	{
		if(!color[i])
		{
			if(!dfs(i,1,mid))return false;
		}
	}
	return true;
}
//------------
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	//--------读边
	memset(h,-1,sizeof h);
	cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		int a,b,c;cin>>a>>b>>c;
		add(a,b,c);add(b,a,c);
	}
	//-----------
	//-------二分满意条件的最小值
	int l=0,r=1e9;
	while(l<r)
	{
		int mid=l+r>>1;
		if(check(mid))r=mid;
		else l=mid+1;
	}
	cout<<r;
	//--------
	return 0;
}

2、最大匹配数棋盘掩盖

给定一个 $N$ 行 $N$ 列的棋盘，已知某些格子制止放置。

求最多能往棋盘上放多少块的长度为 $2$ 、宽度为 $1$ 的骨牌，骨牌的鸿沟与格线重合（骨牌占用两个格子），而且恣意两张骨牌都不重叠。

输入格局

榜首行包括两个整数 $N$ 和 $t$ ，其间 $t$ 为制止放置的格子的数量。

接下来 $t$ 行每行包括两个整数 $x$ 和 $y$ ，表明位于第 $x$ 行第 $y$ 列的格子制止放置，行列数从 $1$ 开端。

输出格局

输出一个整数，表明成果。

数据规模

$1 \leq N \leq 100$ , $0 \leq t \leq 100$

输入样例：

8 0

输出样例：

咱们怎么将他与二分图的最大匹配联系起来呢？

首要我先对每一个格子染上色彩：

咱们发现假如咱们要在一个黑色的格子上放古碑，由于他是 $12$ 的长方形，所以它必定会占用他相邻 $4$ 个白色格子中的一个。所以求解的问题就呈现了：将黑色格子划分到调集 $A$ ,白色格子划分到调集 $B$ ,那么问题便是求二分图的最大匹配数。咱们还能够发现黑色格子的横纵坐标加起来为奇数，白色格子的横纵坐标加起来为偶数，所以咱们随意枚举一个色彩的格子进行匹配即可。

完好代码:

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
//---
const int N=110;
bool g[N][N];//表明每个格子是否被制止
int n,t,ne[][2]={1,0,-1,0,0,1,0,-1};
pii match[N][N];
bool st[N][N];
bool find(int x,int y)
{
	for(int k=0;k<4;k++)//枚举相邻白色方格进行匹配
	{
		int tx=x+ne[k][0];
		int ty=y+ne[k][1];
		if(tx<1||tx>n||ty<1||ty>n||g[tx][ty]||st[tx][ty])continue;
		//越界,制止,现已被占用都是不符合的,直接continue
		st[tx][ty]=true;
		auto t=match[tx][ty];
		if(t.first==0||find(t.first,t.second))
		{
			match[tx][ty]={x,y};
			return true;
		}
	}
	return false;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>n>>t;
	while(t--)
	{
		int x,y;cin>>x>>y;
		g[x][y]=true;//读入制止方格
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(!g[i][j]&&(i+j)%2)//为没有制止的,且坐标和为奇数的方格匹配
			{
				memset(st,0,sizeof st);
				if(find(i,j))ans++;//匹配成功答案+1
			}
		}
	}
	cout<<ans;
	return 0;
}

3、最小点掩盖（Knig 定理）

最小点掩盖：选最少的点，满意每条边至少有一个端点被选。

咱们上边这个二分图 $(他的匹配数是 3)$ 来看：

咱们只挑选了 $3$ 个点，就确保了每一条边的两个端点至少一个在调会集。

定论：二分图中，最小点掩盖 = 最大匹配数。（这儿不给予证明）

例题：机器使命

有两台机器 $A ， B$ 以及 $K$ 个使命。

机器 $A$ 有 $N$ 种不同的形式（形式 $0 \sim N - 1$ ），机器 $B$ 有 $M$ 种不同的形式（形式 $0 \sim M - 1$ ）。

两台机器最开端都处于形式 $0$ 。

每个使命既能够在 $A$ 上履行，也能够在 $B$ 上履行。

关于每个使命 $i$ ，给定两个整数 $a [i]$ 和 $b [i]$ ，表明假如该使命在 $A$ 上履行，需求设置形式为 $a [i]$ ，假如在 $B$ 上履行，需求形式为 $b [i]$ 。

使命能够以恣意次序被履行，但每台机器转换一次形式就要重启一次。

求怎样分配使命并合理安排次序，能使机器重启次数最少。

输入格局

输入包括多组测试数据。

每组数据榜首行包括三个整数 $N, M, K$ 。

接下来 $K$ 行，每行三个整数 $i, a [i], 和 b [i]$ ， $i$ 为使命编号，从 $0$ 开端。

当输入一行为 $0$ 时，表明输入停止。

输出格局

每组数据输出一个整数，表明所需的机器最少重启次数，每个成果占一行。

数据规模

$N, M < 100, K < 1000$ $0 \leq a [i] < N$ $0 \leq b [i] < M$

输入样例：

输出样例：

首要咱们将每一个使命当成一条边，那么咱们想要完成使命 $i$ ，必须要从 $a [i] 和 b [i]$ 选一个,那么标题的要求就会变成：

选出一个调集，里边放的是机器的形式，使得每个使命（边）的至少一个端点在调会集，那么所求调集的点的数量便是答案。

很明显这是一道 最小点掩盖 的标题，而且图为二分图，所以咱们只需求出最大匹配数即可。

完好代码：

#include <bits/stdc++.h>
using namespace std;
//-----建边
const int N=1010,M=1010;
int h[N],e[M],ne[M],idx;
void add(int a,int b)
{
	e[idx]=b;
	ne[idx]=h[a];
	h[a]=idx++;
}
//--------
//-------匈牙利算法
int match[N];bool st[N];
int find(int u)
{
	for(int i=h[u];i!=-1;i=ne[i])
	{
		int j=e[i];
		if(st[j])continue;st[j]=true;
		if(!match[j]||find(match[j]))
		{
			match[j]=u;
			return true;
		}
	}
	return false;
}
//------------------
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	//----------读入建边
	int n,m,k;
	while(cin>>n,n)
	{
		cin>>m>>k;
		memset(h,-1,sizeof h);
		memset(match,0,sizeof match);
		idx=0;
		while(k--)
		{
			int t,a,b;cin>>t>>a>>b;
			if(a==0||b==0)continue;//初始状况为0,所以能够用0处理的就不必求了
			add(a,b);
		}
		//---------------
		int ans=0;
		for(int i=1;i<=n;i++)//开端匹配
		{
			memset(st,0,sizeof st);
			if(find(i))ans++;//匹配成功
		}
		cout<<ans<<endl;//最小点掩盖 = 最大匹配数
		}
	return 0;
}

4、最大独立集

最大独立集：选最多的点，满意两两之间没有边相连。

由于在最小点掩盖中，恣意一条边都被至少选了一个极点，所以关于其点集的补集，恣意一条边都被至多选了一个极点，所以不存在边衔接两个点会集的点，且该点集最大。因此二分图中，最大独立集 = $n$ – 最小点掩盖。

例题：骑士放置

给定一个 $N M$ 的棋盘，有一些格子制止放棋子。

问棋盘上最多能放多少个不能互相进犯的骑士（国际象棋的“骑士”，类似于中国象棋的“马”，依照“日”字进犯，但没有中国象棋“别马腿”的规矩）。

输入格局

榜首行包括三个整数 $N, M, T$ ,其间 $T$ 表明制止放置的格子的数量。

接下来 $T$ 行每行包括两个整数 $x$ 和 $y$ ，表明位于第 $x$ 行第 $y$ 列的格子制止放置，行列数从 $1$ 开端。

输出格局

输出一个整数表明成果。

数据规模

$1 \leq N, M \leq 100$

输入样例：

2 3 0

输出样例：

咱们假定每一个点与扩展的8个方向的点都连一条边。

那么题意是问咱们在棋盘上能够选出多少点，他们两两之间没有边相连 = > 最大独立集问题

此时咱们不能判别是不是二分图问题，现在咱们画图研究一下。

咱们能够看到，每一个白色点能够进犯到的点必定是黑色点，那么咱们就能够当成二分图来做了

黑白格点别离当作二分图的左面点和右边点。

所以答案便是： $n$ -最大匹配数 $(n 为总合法点的数量)$ ,匹配数的求法和上边的棋盘掩盖相同，改一下 $n e []$ 数组即可。

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
const int N=110;
bool g[N][N],st[N][N];
pii match[N][N];
int n,m,t,ne[][2]={-2,-1,-2,1,-1,-2,-1,2,1,-2,1,2,2,-1,2,1};
//--------------匈牙利算法匹配
bool find(int x,int y)
{
	for(int k=0;k<8;k++)
	{
		int tx=x+ne[k][0];
		int ty=y+ne[k][1];
		if(tx<1||tx>n||ty<1||ty>m||g[tx][ty]||st[tx][ty])continue;
		st[tx][ty]=true;
		auto t=match[tx][ty];
		if(t.first==0||find(t.first,t.second))
		{
			match[tx][ty]={x,y};
			return true;
		}
	}
	return false;
}
//----------------------
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>n>>m>>t;
	for(int i=0;i<t;i++)//读入制止点
	{
		int x,y;cin>>x>>y;
		g[x][y]=true;//制止放置
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(!g[i][j]&&(i+j)%2)//只枚举白色点
			{
				memset(st,0,sizeof st);
				if(find(i,j))ans++;
			}
		}
	}
	cout<<n*m-t-ans;//最大独立集 = 有效点数 - 最大匹配数
	return 0;
}

[ 图 论 ]二分图判定及其匹配、最小点覆盖，最大独立集，（基础+提高）

在处理断定和匹配使命之前，我想咱们应该先了解什么是二分图

界说

那么首要咱们先看一个一般的图

上图用了666个点，666条边。这样看起来没什么特别的对吧，咱们将他做一下调整。

此图和上边的是等价的，但是咱们将他们分红了两个调集A,BA,BA,B，而且每个调集内部都没有边相连，这种图便是二分图。

了解了什么是二分图，我想咱们能够开端咱们要讲的断定了，现在你能够动手画一画，是不是一切的图都是二分图呢？显然这是不或许的，但这其间又有什么联系吗？比如现在我给出这样一个图

你能将他分红二分图吗？

例题：染色法断定二分图

输入格局

输出格局

数据规模

输入样例：

输出样例：

所以最大匹配数便是一个二分图中，从两个调会集各拿出一个点，组成一对的最大对数。

咱们用一个例题来说明：二分图的最大匹配

输入格局

输出格局

数据规模

输入样例：

输出样例：

1、染色法+二分 关押罪犯

输入格局

输出格局

数据规模

输入样例：

输出样例：

2、最大匹配数 棋盘掩盖

输入格局

输出格局

数据规模

输入样例：

输出样例：

3、最小点掩盖（Knig 定理）

最小点掩盖：选最少的点，满意每条边至少有一个端点被选。

咱们只挑选了333个点，就确保了每一条边的两个端点至少一个在调会集。

定论：二分图中，最小点掩盖 = 最大匹配数。（这儿不给予证明）

例题： 机器使命

输入格局

输出格局

数据规模

输入样例：

输出样例：

完好代码：

4、最大独立集

最大独立集：选最多的点，满意两两之间没有边相连。

由于在最小点掩盖中，恣意一条边都被至少选了一个极点，所以关于其点集的补集，恣意一条边都被至多选了一个极点，所以不存在边衔接两个点会集的点，且该点集最大。因此二分图中，最大独立集 = nnn – 最小点掩盖。

例题：骑士放置

输入格局

输出格局

数据规模

输入样例：

输出样例：

咱们假定每一个点与扩展的8个方向的点都连一条边。

那么题意是问咱们在棋盘上能够选出多少点，他们两两之间没有边相连 = > 最大独立集问题

此时咱们不能判别是不是二分图问题，现在咱们画图研究一下。

咱们能够看到，每一个白色点能够进犯到的点必定是黑色点，那么咱们就能够当成二分图来做了

黑白格点别离当作二分图的左面点和右边点。

所以答案便是： nnn-最大匹配数(n为总合法点的数量)(n为总合法点的数量)(n为总合法点的数量),匹配数的求法和上边的棋盘掩盖相同，改一下ne[]ne[]ne[]数组即可。

相关文章

微软深夜革命，GPT-4 Office全家桶登场

以 100GB SSB 性能测试为例，通过 ByteHouse 云数仓开启你的数据分析之路

实力爆表，日日新成为AI领航者

2018至2023我的开源项目分享

作者信息

[ 图论 ]二分图判定及其匹配、最小点覆盖，最大独立集，（基础+提高）

上图用了 $6$ 个点， $6$ 条边。这样看起来没什么特别的对吧，咱们将他做一下调整。

此图和上边的是等价的，但是咱们将他们分红了两个调集 $A, B$ ，而且每个调集内部都没有边相连，这种图便是二分图。

1、染色法+二分关押罪犯

2、最大匹配数棋盘掩盖

咱们只挑选了 $3$ 个点，就确保了每一条边的两个端点至少一个在调会集。

例题：机器使命

由于在最小点掩盖中，恣意一条边都被至少选了一个极点，所以关于其点集的补集，恣意一条边都被至多选了一个极点，所以不存在边衔接两个点会集的点，且该点集最大。因此二分图中，最大独立集 = $n$ – 最小点掩盖。

所以答案便是： $n$ -最大匹配数 $(n 为总合法点的数量)$ ,匹配数的求法和上边的棋盘掩盖相同，改一下 $n e []$ 数组即可。