如何判断一个图是二分图

如何判断一个图是二分图

二分图：指的是可以用两个不相交的集合表示该图的节点，然后该图的每一条边的端点分别位于这两个集合中。判断二分图方法：用染色法，把图中的点染成黑色和白色。首先取一个点染成白色，然后将其相邻的点染成黑色，如果发现有相邻且同色的点，那么就退出，可知这个图并非二分图（一次bfs，O（n））。匹配：选择若干条边，然后是任意两条边无公共点树也算是一种特殊的二分图。求树的最大匹配用树形dpf[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;