如何判断一个图是二分图

指的是可以用两个不相交的集合表示该图的节点，然后该图的每一条边的端点分别位于这两个集合中。

判断二分图方法：

用染色法，把图中的点染成黑色和白色。

首先取一个点染成白色，然后将其相邻的点染成黑色，如果发现有相邻且同色的点，那么就退出，可知这个图并非二分图（一次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

设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i

in

A,j

in

B)，则称图G为一个二分图。