二分图匹配及其应用

二分图匹配及其应用

一、        二分图基本概念

1.       二分图：无向图G的顶点集V分成两部分x和y，G中每条边的两个端点一定是一个属于x而另一个属于y，因此二分图可简记为G=（x,y,E）

2.       怎样判别二分图

二分图的邻接矩阵一般具有如下形式

       对于较简单的图，可以直观地判断是否为二分图。对于较复杂的图，可根据下列定义判断。

定理：当且仅当无向图G的每一个回路的长度均为偶数时，G是一个二分图。如果无回路，相当于任一回路的长度为0，而0视为偶数。

证明：分别从必要性和充分性求证。

必要性：若G是二分图，则G的任一回路的长度为偶数。

设G中任一长度为m的回路C=Vi0,Vi1,…,Vim-1,Vim。因G是二分图，因此可将V分为两个互补顶点子集V1和V2，对C来讲，将下标为偶数的顶点属于V1，下标为奇数的顶点属于V2，即Vi0,Vi2,…,Vim-2∈V1，Vi1,Vi3,…,Vim-1∈V2。因m-1为奇数，故m为偶数。

路线。

问题分析：如果直接从小狗的行进路线考虑，从当前的汇合点出发到下一个汇合点，都要考虑小狗的行动方案，并要对之前的方案要进行修正，因此计算量是指数级的，且有较多的后效性。采用动态规划没有可能。

由于主人的路线是固定的。当主人从一个定点走向下一个定点时，小狗跑向一个它感兴趣的景点或与主人同路（当时间不够时）。因此，如果把主人的移动线路的每一段都抽象成点。其性质与小狗要去的景点的性质不同。所以问题就化为两类不同点之间的关系：

设景点Q(xq,yq)    主人移动路线的某一段P（A，B）

Q(xq,yq)与段P（A，B）关联的条件是：（小狗速度最快为主人的两倍）

       Xx,yy:array[1..maxm] of integer;        {景点}              0     顶点i为未盖点

       Link:array[1..maxm] of integer;           {匹配信息，link[i]=    

                                                                                                  J      (j,i)为匹配边

       d:array[1..maxm] of integer;        {顶点i的度d[i]}

       g:array[1..maxn,1..maxm] of integer;   {二分图，g[I,j]为顶点i引出的第j条边的第一个端点序号}

       used:array[1..maxn] of boolean;    {顶点询问标记}

       n,m:integer;           {定点数，景点数}

2、计算过程：

Readln(n,m);

For i:=1 to n do readln(x[i],y[i]);         {输入n个定点坐标}

For i:=1 to m do readln(xx[i],yy[i]);    {输入m个景点坐标}

For i:=1 to n-1 do         {建二分图}

For j:=1 to m do

If 2*sqrt(sqr(x[i]-x[i+1])+sqr(y[i]-y[i+1]))>=

sqrt(sqr(x[i]-xx[j])+sqr(y[i]-yy[j]))+sqrt(sqr(x[i+1]-xx[j])+sqr(y[i+1]-yy[j]))

then begin

inc(d[j]);g[j,d[j]]:=I;

end;

fillchar(link,sizeof(link),0);          {匹配边为空}

for i:=1 to m do           {匈牙利算法求最大匹配}

begin

fillchar(used,sizeof(used),false);

find(i);           {find函数另行编程}

end;

{计算二分图g的匹配数及匹配边}

Tot:=0;

充分性：若G的任一回路的长度为偶数时，G必是二分图，分两种情况讨论。

（1）       G是连通图。

将图的顶点集合V按下列定义分为两个子集

V1={Vi|Vi与某一指定顶点V0的距离为偶数}，V2=V-V1

下面证明，对于任一边e=（Vi，Vj）∈E，若Vi∈V1，则Vj∈V2

设G中任一条边e=(Vi,Vj)，如果e的两个端点Vi和Vj都在V1中，则得到一个回路C=Vi,…,V0,…,Vj,Vi

因Vi,Vj∈V1，按定义Vi和Vj到V0的距离都是偶数，再加上边e，故回路C的长度为奇数，与题设矛盾，说明Vi,Vj不可能都在Vi中。

如果e的两个端点Vi和Vj都在V2中，则按定义Vi和Vj到V0的距离都是奇数，再加上边

e，故回路C的长度亦为奇数，与题设矛盾，说明Vi和Vj也不可能都处于V2中。因此只有唯一一种可能，即e的两个端点，一个在V1中，另一个在V2中，由于e为G中任一条边，根据二分图定义，G是二分图。

（1）       G是非连通图

可对每一个连通子图进行分别讨论，对G的每个连通分量应用上面的证明，然后合并起来，即可证得。

二分图匹配及其应用

一个无向图G=（V，E）的匹配M是指G中若干条边的集合，在M中任意两条边都没有公共的端点。

在二分图中边数最多的匹配，称为二分图的最大匹配。

1.       利用增广路径求二分图最大匹配匈牙利算法

（1）       设M是二分图的一个匹配，将M中的边所关联的顶点称为盖点，其余顶点称为未盖点。

（2）       交错轨：二分图的一条路径上属于M的边和不属于M的边交替出现，则称该路径为交错轨。

（3）       增广路径：若P是一条起始点和结束点都是未盖点的交错轨，则称P为关于匹配M的增广路径。

下图为一条增广路径P=x5y1x2y5 其中实边为匹配M中的边，此时|M|=4

增广路径的性质

性质1：一条关于M的增广路径的长度为奇数，且P的第一条边和最后一条边都不属于M

性质2：对于一条关于M的增广路径P，将M中属于P的边删去，将P中不属于M的边添加到M中，所得到的边集合记为MP，则MP比M增加一条匹配边。

性质3：M为G的一个最大匹配当且仅当不存在关于M的增广路径。

上述性质为我们提供了找最大匹配的基本思想：初始时，置M为空集，然后反复在二分图中找一条关于M的增广路径P，并用MP代替M，直至二分图中不存在关于M的增广路径，最后得到的匹配M就是G的一个最大匹配。

2、匈牙利算法

Edmonds于1965年提出了一种利用增广路径求二分图最大匹配的有效算法匈牙利算法，该算法提出的问题背景是《任务安排》：

设有m个人，n项任务，能否适当安排，使得尽可能多的人有工作做？显然,当n<m时,答案时否定的,当n>=m时也不一定。但经验告诉我们，当m个人适应工作的能力愈强时，愈容

易做到。Hall定理则定量地回答了这个问题。

Hall定理对于二分图G=(X,Y,E)，存在一匹配M，使得X的所有顶点关于M饱和的充要条件是：对X的任一子集A，和A邻接的点集为P[A]，恒有：

│P[A]│≥│A│

匈牙利算法具体实现方法是构造一棵树：

取G的一个未盖点作为根，它位于树的第0层。设已经构造了树的第i-1层，现在要构造第i层，当i为奇数时，将那些关联于第i-1层的一个顶点且不属于M的边，连同该边关联的另一个顶点一起添加到树上。当i为偶数时，则添加那些关于i-1层的一个顶点且属于M的边，连同该边关联的另一个顶点。如果在上述构造树中，发现一个未盖点V被作为树的奇数层顶点，则这样的树根到顶点V的路径就是一条关于M的增广路径，如果在构造树的过程中，既没有找到增广路径，又无法按要求往树上添加新的边和顶点，则可以在余下的顶点中再取一个未盖点作树根，构造一棵新的树。这个过程一直进行下去，如果最终仍未得到任何增广路径，就说明M已经是一个最大匹配了。

3、匈牙利算法描述

(1)数据结构

Const      maxn=<顶点数上限>;

              Maxm=<变数上限>;

Type              gtype=record         {边类型}

                     x,y,next:longint;     {当前边（x,y），next指向x引出的下一条边序号}

                     end;

var          g:array[1..maxm] of gtype;   {二分图边目表}

              first:array[1..maxn] of longint;     {first[i]为x集中顶点i引出的首条边序号}

              link:array[1..maxn] of longint;     {link[i]=        0     顶点i为未盖点

                                                                                    j      （j,i）为匹配边}

              used:array[1..maxn] of boolean;           {顶点询问标志}

              n,m,tot:longint;             {顶点数n，边数m，tot边序号}

（2）主要算法

①将x端每个顶点引出的所有边放在一个链表中，add为边的插入过程

Procedure add(x,y:longint);

Begin

Inc(tot);

G[tot].x:=x;g[tot].y:=y;

G[tot].next:=first[x];first[x]:=tot;  {将当前边插入由顶点x引出的边表首部}

End;

②顶点s出发寻找增广路径（两端点为未盖点的交错轨）

从s点出发，通过回溯法逐条路径地扩展交错轨。若发现边的y端顶点为未盖点，且存在该点为一段的增广路径，则匹配该边。

下面是实现上述回溯法的递归函数：

Function find(s:longint):boolean;  {寻找顶点s出发的匹配边}

Var  temp:longint;

Begin

Find:=true;            {初始时设增广路径存在}

Temp:=first[s];              {取出顶点s引出的首条边}

While temp<>-1 do

Begin

If not used[g[temp].y] then   {若第temp条边y端的顶点未访问，则访问之}

Begin

Used[g[temp].y]:=true;         {置访问标记}

If (link[g[temp].y]=0)and(find（link[g[temp].y]）)

Then       {若第temp条边的y端顶点时未盖点，且从该顶点出发可找到增广路径，则该点s与该顶点匹配，即将第temp条边设为匹配边，并成功退出}

Begin link[g[temp].y]:=s;exit;end;

End;

End;

Find:=false;

End;

③主程序

通过函数find(s)寻找顶点s（属于x集）出发的一条匹配边，那么就可以对每一个顶点调用find以找出二分图的最大匹配。

Begin

Readln(n,m);  {读入顶点数，边数}

For i:=1 to n do first[i]:=-1;  {每个顶点存在的边集为空}

Tot:=0;           {边数tot初始化}

For i:=1 to m do begin readln(x,y);add(x,y);end;{读入m条边，构二分图}

Fillchar(link,sizeof(link),0);  {匹配边为空，所有顶点初始为未盖点}

For i:=1 to n do     {依次从每个顶点出发，寻找可增广轨}

Begin

Fillchar(used,sizeof(used),false);   {所有顶点置未访问}

Find(i);   {从顶点i出发找增广路径}

End;

For i:=1 to n do     {搜索每个顶点，若i顶点为盖点，则输出匹配边（link[i],i）}

If link[i]<>0 then writeln(link[i],‘ ‘,i);

End.

一、        二分图最大匹配的应用

例题：《小狗散步》

问题描述：Grant喜欢带着她的小狗Pandog散步。Grant以一定的速度沿着固定路线走，该路线可能自交。Pandog喜欢游览沿途的景点，不过会在给定的N个点和主人相遇。Pandog与Grant同时从（x1,y1）点出发，并同时在（xn,yn）点汇合。Pandog的速度最快是主人的两倍。当主人从一个点以直线走向另一个点时，Pandog跑向一个它感兴趣的景点。Pandog每次与主人相遇之前最多只去一个景点。

任务：为Pandog寻找一条路线（有可能与主人的路线部分相同），使它能够游览最多的景点，并能够准时与助人在给定地点相遇或汇合。

输入：第1行为顶点数n和景点数m；第2行为2n个正整数，分别给出n个定点的坐标；第3行为2m个正整数，分别给出m个景点的坐标。

输出：第1行为路线长度tot（任意两点之间都算1）；第2行为tot+1个坐标，依次给出该

For i:=1 to m do if link[i]<>0 then inc(tot);

Writeln(tot+n-1);           {输出小狗路线长度}

For i:=1 to n do            {输出小狗路线}

Begin

If i<>n

Then write(x[i],’ ‘,y[i],’ ‘)

Else write(x[i],’ ‘,y[i]);

If link[i]<>0 then write(xx[link[i]],’ ‘,yy[link[i]],’ ‘);

End;