二分圖匹配及其應(yīng)用

二分圖匹配及其應(yīng)用

一、        二分圖基本概念

1.       二分圖：無向圖G的頂點(diǎn)集V分成兩部分x和y，G中每條邊的兩個(gè)端點(diǎn)一定是一個(gè)屬于x而另一個(gè)屬于y，因此二分圖可簡(jiǎn)記為G=（x,y,E）

2.       怎樣判別二分圖

二分圖的鄰接矩陣一般具有如下形式

       對(duì)于較簡(jiǎn)單的圖，可以直觀地判斷是否為二分圖。對(duì)于較復(fù)雜的圖，可根據(jù)下列定義判斷。

定理：當(dāng)且僅當(dāng)無向圖G的每一個(gè)回路的長(zhǎng)度均為偶數(shù)時(shí)，G是一個(gè)二分圖。如果無回路，相當(dāng)于任一回路的長(zhǎng)度為0，而0視為偶數(shù)。

證明：分別從必要性和充分性求證。

必要性：若G是二分圖，則G的任一回路的長(zhǎng)度為偶數(shù)。

設(shè)G中任一長(zhǎng)度為m的回路C=Vi0,Vi1,…,Vim-1,Vim。因G是二分圖，因此可將V分為兩個(gè)互補(bǔ)頂點(diǎn)子集V1和V2，對(duì)C來講，將下標(biāo)為偶數(shù)的頂點(diǎn)屬于V1，下標(biāo)為奇數(shù)的頂點(diǎn)屬于V2，即Vi0,Vi2,…,Vim-2∈V1，Vi1,Vi3,…,Vim-1∈V2。因m-1為奇數(shù)，故m為偶數(shù)。

路線。

問題分析：如果直接從小狗的行進(jìn)路線考慮，從當(dāng)前的匯合點(diǎn)出發(fā)到下一個(gè)匯合點(diǎn)，都要考慮小狗的行動(dòng)方案，并要對(duì)之前的方案要進(jìn)行修正，因此計(jì)算量是指數(shù)級(jí)的，且有較多的后效性。采用動(dòng)態(tài)規(guī)劃沒有可能。

由于主人的路線是固定的。當(dāng)主人從一個(gè)定點(diǎn)走向下一個(gè)定點(diǎn)時(shí)，小狗跑向一個(gè)它感興趣的景點(diǎn)或與主人同路（當(dāng)時(shí)間不夠時(shí)）。因此，如果把主人的移動(dòng)線路的每一段都抽象成點(diǎn)。其性質(zhì)與小狗要去的景點(diǎn)的性質(zhì)不同。所以問題就化為兩類不同點(diǎn)之間的關(guān)系：

設(shè)景點(diǎn)Q(xq,yq)    主人移動(dòng)路線的某一段P（A，B）

Q(xq,yq)與段P（A，B）關(guān)聯(lián)的條件是：（小狗速度最快為主人的兩倍）

       Xx,yy:array[1..maxm] of integer;        {景點(diǎn)}              0     頂點(diǎn)i為未蓋點(diǎn)

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

                                                                                                  J      (j,i)為匹配邊

       d:array[1..maxm] of integer;        {頂點(diǎn)i的度d[i]}

       g:array[1..maxn,1..maxm] of integer;   {二分圖，g[I,j]為頂點(diǎn)i引出的第j條邊的第一個(gè)端點(diǎn)序號(hào)}

       used:array[1..maxn] of boolean;    {頂點(diǎn)詢問標(biāo)記}

       n,m:integer;           {定點(diǎn)數(shù)，景點(diǎn)數(shù)}

2、計(jì)算過程：

Readln(n,m);

For i:=1 to n do readln(x[i],y[i]);         {輸入n個(gè)定點(diǎn)坐標(biāo)}

For i:=1 to m do readln(xx[i],yy[i]);    {輸入m個(gè)景點(diǎn)坐標(biāo)}

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函數(shù)另行編程}

end;

{計(jì)算二分圖g的匹配數(shù)及匹配邊}

Tot:=0;

充分性：若G的任一回路的長(zhǎng)度為偶數(shù)時(shí)，G必是二分圖，分兩種情況討論。

（1）       G是連通圖。

將圖的頂點(diǎn)集合V按下列定義分為兩個(gè)子集

V1={Vi|Vi與某一指定頂點(diǎn)V0的距離為偶數(shù)}，V2=V-V1

下面證明，對(duì)于任一邊e=（Vi，Vj）∈E，若Vi∈V1，則Vj∈V2

設(shè)G中任一條邊e=(Vi,Vj)，如果e的兩個(gè)端點(diǎn)Vi和Vj都在V1中，則得到一個(gè)回路C=Vi,…,V0,…,Vj,Vi

因Vi,Vj∈V1，按定義Vi和Vj到V0的距離都是偶數(shù)，再加上邊e，故回路C的長(zhǎng)度為奇數(shù)，與題設(shè)矛盾，說明Vi,Vj不可能都在Vi中。

如果e的兩個(gè)端點(diǎn)Vi和Vj都在V2中，則按定義Vi和Vj到V0的距離都是奇數(shù)，再加上邊

e，故回路C的長(zhǎng)度亦為奇數(shù)，與題設(shè)矛盾，說明Vi和Vj也不可能都處于V2中。因此只有唯一一種可能，即e的兩個(gè)端點(diǎn)，一個(gè)在V1中，另一個(gè)在V2中，由于e為G中任一條邊，根據(jù)二分圖定義，G是二分圖。

（1）       G是非連通圖

可對(duì)每一個(gè)連通子圖進(jìn)行分別討論，對(duì)G的每個(gè)連通分量應(yīng)用上面的證明，然后合并起來，即可證得。

二分圖匹配及其應(yīng)用

一個(gè)無向圖G=（V，E）的匹配M是指G中若干條邊的集合，在M中任意兩條邊都沒有公共的端點(diǎn)。

在二分圖中邊數(shù)最多的匹配，稱為二分圖的最大匹配。

1.       利用增廣路徑求二分圖最大匹配——匈牙利算法

（1）       設(shè)M是二分圖的一個(gè)匹配，將M中的邊所關(guān)聯(lián)的頂點(diǎn)稱為蓋點(diǎn)，其余頂點(diǎn)稱為未蓋點(diǎn)。

（2）       交錯(cuò)軌：二分圖的一條路徑上屬于M的邊和不屬于M的邊交替出現(xiàn)，則稱該路徑為交錯(cuò)軌。

（3）       增廣路徑：若P是一條起始點(diǎn)和結(jié)束點(diǎn)都是未蓋點(diǎn)的交錯(cuò)軌，則稱P為關(guān)于匹配M的增廣路徑。

下圖為一條增廣路徑P=x5y1x2y5 其中實(shí)邊為匹配M中的邊，此時(shí)|M|=4

增廣路徑的性質(zhì)

性質(zhì)1：一條關(guān)于M的增廣路徑的長(zhǎng)度為奇數(shù)，且P的第一條邊和最后一條邊都不屬于M

性質(zhì)2：對(duì)于一條關(guān)于M的增廣路徑P，將M中屬于P的邊刪去，將P中不屬于M的邊添加到M中，所得到的邊集合記為M⊕P，則M⊕P比M增加一條匹配邊。

性質(zhì)3：M為G的一個(gè)最大匹配當(dāng)且僅當(dāng)不存在關(guān)于M的增廣路徑。

上述性質(zhì)為我們提供了找最大匹配的基本思想：初始時(shí)，置M為空集，然后反復(fù)在二分圖中找一條關(guān)于M的增廣路徑P，并用M⊕P代替M，直至二分圖中不存在關(guān)于M的增廣路徑，最后得到的匹配M就是G的一個(gè)最大匹配。

2、匈牙利算法

Edmonds于1965年提出了一種利用增廣路徑求二分圖最大匹配的有效算法——匈牙利算法，該算法提出的問題背景是《任務(wù)安排》：

設(shè)有m個(gè)人，n項(xiàng)任務(wù)，能否適當(dāng)安排，使得盡可能多的人有工作做？顯然,當(dāng)n<m時(shí),答案時(shí)否定的,當(dāng)n>=m時(shí)也不一定。但經(jīng)驗(yàn)告訴我們，當(dāng)m個(gè)人適應(yīng)工作的能力愈強(qiáng)時(shí)，愈容

易做到。Hall定理則定量地回答了這個(gè)問題。

Hall定理對(duì)于二分圖G=(X,Y,E)，存在一匹配M，使得X的所有頂點(diǎn)關(guān)于M飽和的充要條件是：對(duì)X的任一子集A，和A鄰接的點(diǎn)集為P[A]，恒有：

│P[A]│≥│A│

匈牙利算法具體實(shí)現(xiàn)方法是構(gòu)造一棵樹：

取G的一個(gè)未蓋點(diǎn)作為根，它位于樹的第0層。設(shè)已經(jīng)構(gòu)造了樹的第i-1層，現(xiàn)在要構(gòu)造第i層，當(dāng)i為奇數(shù)時(shí)，將那些關(guān)聯(lián)于第i-1層的一個(gè)頂點(diǎn)且不屬于M的邊，連同該邊關(guān)聯(lián)的另一個(gè)頂點(diǎn)一起添加到樹上。當(dāng)i為偶數(shù)時(shí)，則添加那些關(guān)于i-1層的一個(gè)頂點(diǎn)且屬于M的邊，連同該邊關(guān)聯(lián)的另一個(gè)頂點(diǎn)。如果在上述構(gòu)造樹中，發(fā)現(xiàn)一個(gè)未蓋點(diǎn)V被作為樹的奇數(shù)層頂點(diǎn)，則這樣的樹根到頂點(diǎn)V的路徑就是一條關(guān)于M的增廣路徑，如果在構(gòu)造樹的過程中，既沒有找到增廣路徑，又無法按要求往樹上添加新的邊和頂點(diǎn)，則可以在余下的頂點(diǎn)中再取一個(gè)未蓋點(diǎn)作樹根，構(gòu)造一棵新的樹。這個(gè)過程一直進(jìn)行下去，如果最終仍未得到任何增廣路徑，就說明M已經(jīng)是一個(gè)最大匹配了。

3、匈牙利算法描述

(1)數(shù)據(jù)結(jié)構(gòu)

Const      maxn=<頂點(diǎn)數(shù)上限>;

              Maxm=<變數(shù)上限>;

Type              gtype=record         {邊類型}

                     x,y,next:longint;     {當(dāng)前邊（x,y），next指向x引出的下一條邊序號(hào)}

                     end;

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

              first:array[1..maxn] of longint;     {first[i]為x集中頂點(diǎn)i引出的首條邊序號(hào)}

              link:array[1..maxn] of longint;     {link[i]=        0     頂點(diǎn)i為未蓋點(diǎn)

                                                                                    j      （j,i）為匹配邊}

              used:array[1..maxn] of boolean;           {頂點(diǎn)詢問標(biāo)志}

              n,m,tot:longint;             {頂點(diǎn)數(shù)n，邊數(shù)m，tot邊序號(hào)}

（2）主要算法

①將x端每個(gè)頂點(diǎn)引出的所有邊放在一個(gè)鏈表中，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;  {將當(dāng)前邊插入由頂點(diǎn)x引出的邊表首部}

End;

②頂點(diǎn)s出發(fā)尋找增廣路徑（兩端點(diǎn)為未蓋點(diǎn)的交錯(cuò)軌）

從s點(diǎn)出發(fā)，通過回溯法逐條路徑地?cái)U(kuò)展交錯(cuò)軌。若發(fā)現(xiàn)邊的y端頂點(diǎn)為未蓋點(diǎn)，且存在該點(diǎn)為一段的增廣路徑，則匹配該邊。

下面是實(shí)現(xiàn)上述回溯法的遞歸函數(shù)：

Function find(s:longint):boolean;  {尋找頂點(diǎn)s出發(fā)的匹配邊}

Var  temp:longint;

Begin

Find:=true;            {初始時(shí)設(shè)增廣路徑存在}

Temp:=first[s];              {取出頂點(diǎn)s引出的首條邊}

While temp<>-1 do

Begin

If not used[g[temp].y] then   {若第temp條邊y端的頂點(diǎn)未訪問，則訪問之}

Begin

Used[g[temp].y]:=true;         {置訪問標(biāo)記}

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

Then       {若第temp條邊的y端頂點(diǎn)時(shí)未蓋點(diǎn)，且從該頂點(diǎn)出發(fā)可找到增廣路徑，則該點(diǎn)s與該頂點(diǎn)匹配，即將第temp條邊設(shè)為匹配邊，并成功退出}

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

End;

End;

Find:=false;

End;

③主程序

通過函數(shù)find(s)尋找頂點(diǎn)s（屬于x集）出發(fā)的一條匹配邊，那么就可以對(duì)每一個(gè)頂點(diǎn)調(diào)用find以找出二分圖的最大匹配。

Begin

Readln(n,m);  {讀入頂點(diǎn)數(shù)，邊數(shù)}

For i:=1 to n do first[i]:=-1;  {每個(gè)頂點(diǎn)存在的邊集為空}

Tot:=0;           {邊數(shù)tot初始化}

For i:=1 to m do begin readln(x,y);add(x,y);end;{讀入m條邊，構(gòu)二分圖}

Fillchar(link,sizeof(link),0);  {匹配邊為空，所有頂點(diǎn)初始為未蓋點(diǎn)}

For i:=1 to n do     {依次從每個(gè)頂點(diǎn)出發(fā)，尋找可增廣軌}

Begin

Fillchar(used,sizeof(used),false);   {所有頂點(diǎn)置未訪問}

Find(i);   {從頂點(diǎn)i出發(fā)找增廣路徑}

End;

For i:=1 to n do     {搜索每個(gè)頂點(diǎn)，若i頂點(diǎn)為蓋點(diǎn)，則輸出匹配邊（link[i],i）}

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

End.

一、        二分圖最大匹配的應(yīng)用

例題：《小狗散步》

問題描述：Grant喜歡帶著她的小狗Pandog散步。Grant以一定的速度沿著固定路線走，該路線可能自交。Pandog喜歡游覽沿途的景點(diǎn)，不過會(huì)在給定的N個(gè)點(diǎn)和主人相遇。Pandog與Grant同時(shí)從（x1,y1）點(diǎn)出發(fā)，并同時(shí)在（xn,yn）點(diǎn)匯合。Pandog的速度最快是主人的兩倍。當(dāng)主人從一個(gè)點(diǎn)以直線走向另一個(gè)點(diǎn)時(shí)，Pandog跑向一個(gè)它感興趣的景點(diǎn)。Pandog每次與主人相遇之前最多只去一個(gè)景點(diǎn)。

任務(wù)：為Pandog尋找一條路線（有可能與主人的路線部分相同），使它能夠游覽最多的景點(diǎn)，并能夠準(zhǔn)時(shí)與助人在給定地點(diǎn)相遇或匯合。

輸入：第1行為頂點(diǎn)數(shù)n和景點(diǎn)數(shù)m；第2行為2n個(gè)正整數(shù)，分別給出n個(gè)定點(diǎn)的坐標(biāo)；第3行為2m個(gè)正整數(shù)，分別給出m個(gè)景點(diǎn)的坐標(biāo)。

輸出：第1行為路線長(zhǎng)度tot（任意兩點(diǎn)之間都算1）；第2行為tot+1個(gè)坐標(biāo)，依次給出該

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

Writeln(tot+n-1);           {輸出小狗路線長(zhǎng)度}

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;