二分图的概念

二分图的概念

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

         

上图可以存储为邻接矩阵： (0 0 0 1 1 10            也可以存储为（1 1 1 0

                       0 0 0 0 1 01                        0 1 0 1

                       0 0 0 1 0 10                        1 0 1 0）

                       1 0 1 0 0 0 0

                       1 1 0 0 0 0 0

                       1 0 1 0 0 0 0

                       0 1 0 0 0 0 0 )

5. 2 最大匹配

1.最大匹配的概念

设G=(V,E)是一个图,如果M是边E的子集,且M中的任意两条边都不与同一个顶点相关联,则称M是G的一个匹配。G的边数最多的匹配称为G的最大匹配。

2．最大匹配算法

最大流方法

1) 将图变成单向有向图A-->B

2) 添加源点s和汇点t将图变为 s-->A-->B-->t,  如上图一可变为

                   图2

3）设每条有向边的容量c为1

4）源点到汇点的最大流即为最大匹配

  例一：混双配对问题：

乒乓球队中有N名男运动员和M名女运动员。由于某种原因，在混双比赛中，某些男运动员和某些女运动员不能配对比赛，这使得教练很苦恼，他希望你能帮他找出一种最优得配对方案，组成今尽可能最多得混双配对。

输入文件：第一行两个正整数N，M（N＋M<=100),表示男、女运动的个数。以下是一个N×M的矩阵。若Aij＝1表示第i名男运动员可与第j名女运动员配对；若Aij＝0则表示不能配对。

输出文件：只有一个整数，为最多的混双配对。

程序如下：

program tpp1;
const inf='input.txt';
      maxn=100;
type
arc=record
  c, f:integer;
end;
node=record
  last:integer;
  checked:boolean;
end;
var
map:array[1..maxn+2,1..maxn+2] of arc;
imp:array[1..maxn+2] of node;
n,m,s,t:integer;
fp:text;
procedure init;
var i,j:integer;
begin
assign(fp,inf);
reset(fp);
readln(fp,n,m);
fillchar(map,sizeof(map),0);
for i:=1 to n do
  for j:=1 to m do
   read(fp,map[i,n+j].c);
s:=n+m+1;
t:=n+m+2;
for i:=1 to n do map[s,i].c:=1;
for i:=1 to m do map[i+n,t].c:=1;
close(fp);
end;
procedure main;
var flow,i:integer;
function find:boolean;
  var i,j:integer;
  begin
   find:=false;
   fillchar(imp,sizeof(imp),0);
   imp.last:=s;
   repeat
    i:=1;
    while (i<=n+m+2) and ((imp.last=0) or imp.checked)do inc(i);
    if i>n+m+2 then exit;
    for j:=1 to n+m+2 do
      if imp[j].last=0 then begin
       if map[i,j].f<map[i,j].c thenimp[j].last:=i else
        if map[j,i].f>0 thenimp[j].last:=-i; end;
    imp.checked:=true;
   until imp[t].last<>0;
   find:=true;
  end;
procedure updata;
var i,j:integer;
begin
  i:=t;j:=abs(imp.last);
  repeat
   if imp.last>0 then inc(map[j,i].f) else dec(map[i,j].f);
   i:=j;j:=abs(imp.last);
  until i=s;
end;
begin
  while find do updata;
  flow:=0;
  for i:=1 to n do inc(flow,map[s,i].f);
  writeln('maxpp=',flow);
end;
begin
init;
main;
end.