本文目录
什么叫二部图
二部图又称双分图、二分图，偶图，指顶点可以分成两个不相交的集使得在同一个集内的顶点不相邻（没有共同边）的图。
图G=《V，E》，如果V1∪V2=V，V1∩V2=Φ，对于每个(x，y)∈E，皆有x∈V1，y∈V2，或x∈V2，y∈V1，则称G为二部图 (或偶图)。
二分图的充要条件
无向图G为二分图的充分必要条件是，G至少有两个顶点，且其所有回路的长度均为偶数。
证先证必要性。
设G为二分图《X，E，Y》。由于X，Y非空，故G至少有两个顶点。若C为G中任一回路，令
C = (v0,v 1,v2，…，v l-1,v l = v0)
其中诸vi (i = 0,1，…，l）必定相间出现于X及Y中，不妨设
{v0,v2,v4，…，v l = v0} Í X
{v1,v3,v5，…，v l-1} Í Y
因此l必为偶数，从而C中有偶数条边。
再证充分性。
设G的所有回路具有偶数长度，并设G为连通图（不失一般性，若G不连通，则可对G的各连通分支作下述讨论）。
令G的顶点集为V，边集为E，现构作X，Y，使《X，E，Y》 = G。取v0ÎV，置
X = {v | v= v0或v到v0有偶数长度的通路}
Y = V-X
X显然非空。现需证Y非空，且没有任何边的两个端点都在X中或都在Y中。
由于|V|≥2并且G为一连通图，因此v0必定有相邻顶点，设为v1，那么v1ÎY；故Y不空。
设有边（u,v），使uÎX，vÎX。那么，v0到u有偶数长度的通路，或u = v0；v0到v有偶数长度的通路，或v = v0。无论何种情况，均有一条从v0到v0的奇数长度的闭路径，因而有从v0到v0的奇数长度的回路（因从闭路径上可能删去的回路长度总为偶数），与题设矛盾。故不可能有边（u,v）使u,v均在X中。
“没有任何边的两个端点全在Y中”的证明可仿上进行，请读者思考。
二分图匹配的例题
中、日、韩三个足球队进行比赛，已知A不是第一名，B不是韩国队，也不是第二名，第一名不是日本队，中国队第二.问A、B、C各代表哪国队？各是第几名？
我们先来降低难度.先只要求你判断出中、日、韩各是第几名（不必判断A、B、C）.可以把中、日、韩各用一个点代表，列于上一行.第一、二、三名各用一个点代表，列于下一行，记为：
V1={中，日，韩}，V2={第1名，第2名，第3名}.
V1中的点与V2中某一个点有肯定关系的，就画一条实线，如和②.否定关系的两点之间画一条虚线，如不是②；不是①.把已知条件不加任何推理地表现于图上.虚线2条，实线1条，共3条线.
现在，有两个明显的事实；第一，V1中每点有且只有一条实线与V2中相应点配对，V2中每点有且只有一条实线与V1中相应点配对.V1内部点之间不会有线相联结，V2内部点之间也不会有线相联结.第二，从V1（或V2）中某一个点，例如说a点如发出了一条实线向着V2（或V1）中某一个点，例如说x点，那么a点与V2（或V1）中其他点之间必然只能用虚线联结.（这是逻辑推理中的排它性）
由此，我们很容易将中、日、韩的名次判出.
这样的问题，抽象起来可归属于图论中称之为“二分图的匹配”问题.
图论的名词术语太多，这里不作详细定义，只是描述性介绍一下，大家以前在“一笔画”等讲中已初步接触.所谓二分图，就是顶点集合可以划分成两个部分，V=V1+V2，如V1有p个点，记为V1={v1，v2…，vp}，V2有q个点，记为V2={vp+1，vp+2…，vp+q}，而V1中任意一点，不会与V1中其他点联结，而只能与V2中某些点联结；V2也如此.大家看几个例.
一般的图记为G=（V，E），V是顶点集合，E是边（也可称为线）的集合.大家在哥尼斯堡七桥问题中已领略过这种抽象.现在的二分图是一类特殊的图，只不过顶点集V划分为两部分，而这只能“跨越”于V1中某个点和V2中另一个点.二分图的匹配问题，就是找一个边的集合，这些边之间都没有公共的端点.
关于二分图的匹配，要研究的是“最大匹配”，即找一个边最多的匹配.
就本讲开始引入的问题看，我们还没有解完，因为还有A、B、C三个代号到底如何归于中、日、韩三队的问题.一种解题办法，是把已判出的国籍和名次捆绑在一个顶点内，如（中2）、（韩1）、（日3），再和A、B、C构造一个新的二分图：
显然，推知B是（日3），因为B有2条虚线，而必然有1条实线，只能推出B与（日3）之间为实线.同理，（韩1）只能为C；剩下的唯一的情况留给了A为（中2）.全部问题解决了.
再看最初的题目，如果你选择先判断中、日、韩和A、B、C三个代号之间的匹配关系，将会怎样呢？画一个图看，利用已知条件画出实、虚线.
只能利用B不是韩国队及中国队第二，B不是第二（因此B不是中国队）这样一些条件，题目中另二句话：A不是第一名，第一名不是日本队，这种否定关系之间，没有传递性，你不能判定A是不是日本队.因此根据已知条件所画的图中只有两条虚线，之后最多只能确定日、B之间为实线.所以对这样的二分图，无法找出合理的最大匹配.这方法使问题求解走进了死胡同.
那么你选择先判A、B、C和第一、第二、第三名之间的匹配关系，又会怎样呢？画一个图看.
现在也只有二条虚线，仍然无法找出最大匹配，或说解不唯一，对求解问题无助.
现在回过头来看，先找国别与名次之间的匹配，似乎有些“碰运气”，因为完全可以把题目改动，使先找国别与名次的匹配无法解决，例如叙述改为：
中、日、韩三足球队比赛，已知结果为：第1名不是A，第2名不是韩国队也不是B，A不是日本队，中国队为B，问A、B、C，和1、2、3名与各国队如何匹配？
细心读者发现，这只是把原题中A、B、C的地位与1、2、3名的地位互换而已.所以现在改动后的题目，再先抓“国别”和“名次”的匹配，就无法求解.
但是数学要求找出一种解一般问题的方法而不是“碰运气”，而且完全可以找一个例子，使得无论取国别与名次；或国别与代号（A，B，C）；或代号与名次这三类二分图的匹配都无法求解，而必须找更广泛意义下的匹配才能解决，为此先介绍一般的三个因素一起考虑的“匹配”方法.
先结合前例，将国别用三个不同点表示于上方，三个名次点表示于左下方，三个代号点表示于右下方.用实线的肯定关系和虚线的否定关系把已知条件“翻译”于图上.-二分图
如何判断一个图是二分图
二分图：
指的是可以用两个不相交的集合表示该图的节点，然后该图的每一条边的端点分别位于这两个集合中。
判断二分图方法：
用染色法，把图中的点染成黑色和白色。
首先取一个点染成白色，然后将其相邻的点染成黑色，如果发现有相邻且同色的点，那么就退出，可知这个图并非二分图（一次bfs，O（n））。
匹配：选择若干条边，然后是任意两条边无公共点
树也算是一种特殊的二分图。
求树的最大匹配用树形dp
f[i,0]表示标号为i的点不选取所能获得的最大匹配数
f[i,1]表示标号为i的点选取所能获得的最大匹配数
f[i,0]=sigma{f[k,1],f[k,0]}；(k，表示以i为父节点的点的标号)f[i,1]=sigma{f[k,1],f[k,0]}+1+f[j,0]；{j表示与i相连的点，k是除j外的点}
存储图的方法用前向星
前向星的存取：{示例是以有向边为准}
read(x,y);{表示x，y中有一条边相连}
inc（tot）；{tot表示目前边的总数}
e[tot]:=y；{表示第tot条边以y结尾}
pre[tot]:=last[x];{表示与第tot条边同起点的前一条边的位置}
last[x]:=tot;{目前以x为起点的最后一条边是tot}
tmp：=last[a];{目前要访问a}
while tmp《》0 do begin{表示还有边}
if not bl[e[tmp]] then dfs(e[tmp]);{表示当前访问的点之前没有被访问过}
tmp：=pre[tmp];
end;
-二分图
哪些现实问题涉及用二分图的思路来解决
应用就很多了，这也是二分图匹配最常考的了
最常见的就是两种题型吧，一个是题目里明确说了要匹配的，正常连边就可以
还有一个是二分图的一个转化模型，比如说放棋子，每行只能放一个，每列只能放一个这种的，那么我们可以把每一行当成左半部分的点，每一列当成右半部分的点，每个能放棋子的地方就把他的行向列连一条边就可以了，这样的题目也不少，比如说
P1263 宫廷守卫 上面的模型稍微变化一下就好了
[SCOI2015] 小凸玩矩阵 二分一下就好等等
然后还有一些其他的，比如说
[JSOI2016] 反质数序列判断质数，按奇偶性连边
————————————————
版权声明：本文为CSDN博主「NephrenRuqInsania」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/devout_/article/details/104950249
-二分图
二分图的辨析示例
区别二分图，关键是看点集是否能分成两个独立的点集。
上图中U和V构造的点集所形成的循环圈不为奇数，所以是二分图。
上图中U和V和W构造的点集所形成的的循环圈为奇数，所以不是二分图。
二分图判定
#include 《iostream》
#include 《cstring》
#include 《queue》
using namespace std;
int edge;
bool vis;
bool has;
int color; // 0 for white, 1 for black
int main() {
int N, M;
cin 》》 N 》》 M;
memset(edge, 0, sizeof(edge));
memset(vis, 0, sizeof(vis));
memset(has, 0, sizeof(has));
for (int i = 0; i 《 M; i++) {
int a, b;
cin 》》 a 》》 b;
has[a] = has[b] = 1;
edge[a][b] = edge[b][a] = 1;
}
bool flag = true;
int counts = 0;
for (int i = 1; flag && i 《= N; i++) {
if (vis[i] || !has[i]) continue;
queue《int》 q;
q.push(i);
vis[i] = true;
color[i] = 0;
counts++;
while (flag && !q.empty()) {
int temp = q.front();
q.pop();
for (int j = 1; j 《= N; j++) {
if (!edge[temp][j]) continue;
if (vis[j]) {
if (color[j] == color[temp]) {
flag = false;
break;
}
else {
continue;
}
}
vis[j] = true;
color[j] = 1 - color[temp];
counts += 1 - color[j];
q.push(j);
}
}
}
if (flag) {
cout 《《 “yes“ 《《 endl;
cout 《《 counts 《《 endl;
bool first = true;
for (int i = 1; i 《= N; i++) {
if (vis[i] == 1 && color[i] == 0) {
if (first) {
first = false;
}
else {
cout 《《 “ “;
}
cout 《《 i;
}
}
cout 《《 endl;
}
else {
cout 《《 “no“ 《《 endl;
}
// system(“pause“);
}
-二分图
二分图相关概念
二分图又称作二部图，是图论中的一种特殊模型。
设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i
in
A,j
in
B)，则称图G为一个二分图。
-二分图
