定义：
首先，什么是二分图？
百度百科上的定义是：“设是一个无向图，如果顶点可分割为两个互不相交的子集，并且图中的每条边所关联的两个顶点和分别属于这两个不同的顶点集，则称图G为一个二分图。”
通俗点说，如果一个无向图所有的点可以分成两个部分，每个部分内部都没有边相连。
什么意思呢？举个例子吧。
.png?table=block&id=18e91f2d-cd09-4d8e-86dd-04389b684c72&cache=v2)
.png?table=block&id=80dd71a8-fe99-410c-8b38-8363fbe0d4ba&cache=v2)
上图就是一个典型的二分图，图可以分成两个部分，一个是，另一个是。这两个部分内部都没有边相连，不连通，不连通，不连通，右半部分同理。
再举一个例子：
这就不是一个二分图，大家可以自行枚举，至于它为什么不是二分图，马上就讲。
定理：
一个无向图是二分图的充分必要条件就是该图内的每一个环的长度都是偶数。
先证明必要性。假设有一个环长度为，包含s个节点。可以将这个环单独剖离出来，看做一个待判定的图（若一个图子图不是二分图，则该图也一定不是二分图）。可以采用摇摆法，不妨设该环可以分为和（注意大小写）两个内部互不相交的点集，。则必然。归纳一下，得到：
由此可以发现，若该环是二分图，则一定是奇数，一定是偶数，因此定理中的必要性得证。
可以采用摇摆法加反证法。为了简化原问题并不影响结果，我们可以假设图是一个连通图。假设该图内每一个环的长度都是偶数，因此我们可以定义该图的两个子集分别为和，对于任意的，同理。为了证明内部没有边相连接，就可以采用反证法。假设，且存在一条边。由前面的假设可知，与之间的距离为偶数，与之间的距离也为偶数，而与之间的距离为，因此，有，和构成的环的长度就是奇数，与所给条件不符，因此假设不成立，因此必要性得证。
有了这个定理，再看看上面的那个图，会发现由构成的环的长度为奇数，因此，那不是一个二分图。
好了，上面讲了这个定理，证明了这么久，有什么用吗？很抱歉地告诉你，并没有，但是你可以跟朋友秀一下“不打草稿肉眼判定二分图”，相信只会染色法的你的朋友一定会大吃一惊的。
实现：
刚刚提到了染色法，染色法是什么？
举个例子吧，可以自己体会一下。还是刚刚那个图：
从一号节点开始，染上红色
遍历所有与相邻的节点，染上另一种颜色。
在遍历，染色时发现出现了相邻的边染上了同种颜色的情况，因此判定它不是二分图。
由此，可知一个无向图是二分图的充要条件就是可二着色（可以用两种颜色染出来）。
还可以推广一下：一个无向图是分图的充要条件就是可着色（可以用种颜色染出来）。
UVA上有一道模板题：
下面直接附上代码吧，就是深搜染色：
//
// Created by admin on 2020/7/21.
//
#include <bits/stdc++.h>
using namespace std;
int n,m,color[300];
vector<int> no[300];
bool h;
bool dfs(int x,int c)
{
color[x]=c;
for(int i=0;i<no[x].size();i++)
{
int y=no[x][i];
if(color[y]==c)//相邻边染上了同种颜色
return false;
if(color[y]==0&&!(dfs(y,-c)))//只要有一个点无法染色，全部返回false
return false;
}
return true;
}
int main()
{
while (true)
{
h=false;
memset(no,0,sizeof(no));
memset(color,0,sizeof(color));
cin>>n;
if(n==0)
break;
cin>>m;
int x,y;
for(int i=1;i<=m;i++)
{
cin>>x>>y;
no[x].push_back(y);
no[y].push_back(x);
}
for(int i=1;i<=n;i++)
if(color[i]==0)//没有染色（原图不一定连通，一次染色不一定能染上全部）
{
if(!dfs(i,1))
{
h=true;
break;
}
}
if(h)
cout<<"NOT BICOLORABLE."<<endl;
else
cout<<"BICOLORABLE."<<endl;
}
return 0;
}UVA上还有一题，近似于模板：
再附上代码：
//
// Created by admin on 2020/7/21.
//
#include <bits/stdc++.h>
using namespace std;
int n,m,color[4000],tot,colored;
vector<int> no[4000];
bool b;
void dfs(int x,int c)
{
color[x]=c;
tot++;
if (c==1)
colored++;
for(int i=0;i<no[x].size();i++)
{
int y=no[x][i];
if (color[y]==0)
dfs(y,-c);
else
if(color[y]==c)
b=false;
}
}
int main()
{
int t;
cin>>t;
while (t--)
{
int ans=0;
memset(no,0,sizeof(no));
memset(color,0,sizeof(color));
cin>>n;
int x;
for (int j = 1; j <=n; ++j)
{
cin>>m;
for(int i=1;i<=m;i++)
{
cin>>x;
if(x>n)
continue;
no[j].push_back(x);
no[x].push_back(j);
}
}
for(int i=1;i<=n;i++)
if(color[i]==0)
{
tot=colored=0;
b=true;
dfs(i,1);
if(b)
ans+=max(colored,tot-colored);
}
cout<<ans<<endl;
}
return 0;
}
Loading Comments...