二分図最大マッチング--ハンガリーアルゴリズム
二分図が何なのかはくどくどしない.
ハンガリーアルゴリズムの核心は、Pが図Gの2つの非整合頂点を連通する経路であり、Mに属するエッジとMに属さないエッジ(すなわち、整合されたエッジと整合されるエッジ)がP上に交互に現れる場合、PをMに対する拡張経路と呼ぶ.(Mは一致)を選択し、このパスを反転すると、一致するエッジが1増加します.
C言語コード:
http://course.cug.edu.cn/21cn/%E7%A6%BB%E6%95%A3%E6%95%B0%E5%AD%A6%EF%BC%88%E5%8C%97%E5%A4%A7%EF%BC%89/part4/chapter18/18_03_02_01.htm
二、Hall定理
定理18.5
(
ホールの定理
)二部図G=1
,V
2
,E>中,|V
1
|≤|V
2
|.GにはVから
1
Vまで
2
の完全一致は、V
1
中任意k(k＝1,2,…,｜V
1
|)個の頂点は少なくともV
2
のk個の頂点が隣接しています.
本定理の条件を「相異性条件」と呼ぶことが多い.
証定理の必要性は明らかである.以下では,相異性条件を満たす限り,Gにおける最大整合が完全整合であることを証明する.MをGの中の1つの最大マッチングとする.Mが完全整合でなければ,vx∈V 1がMである非飽和点が必ず存在する.e∈E 1=E−Mがvxに関連付けられる必要があります.そうしないと、vxは孤立点になり、相異性条件と矛盾します.また,V 2におけるvxに隣接する頂点はすべてM−飽和点であり,vy∈V 2(vxに隣接する)が非飽和点である場合,M′=M∈(vx,vy)も一致し,これは明らかにMが最大整合であることと矛盾する.vxからの可能な限り長いすべてのインタリーブ経路を考慮すると、Mは最大整合であるため、定理18.4から分かるように、これらのインタリーブ経路は拡張可能ではない.すなわち、各経路がvxと異なる端点はM−飽和点であるに違いない.そこで、これらの端点はすべてV 1にあり、
S={v|v∈V 1,vはvxからのインタリーブ経路上}T={v|v∈V 2,vはvxからのインタリーブ経路上}
各交錯経路の2つの端点が全てS中であるため、|S|=|T|+1となる.これはV
1
中|T|+1個の頂点はVのみ
2
中|T|個の頂点が隣接しており、これは相異性条件と矛盾しているため、V
1
中にはM−非飽和点は存在し得ないので,Mは完全整合である.
図18.4(3)において、V 1に存在する2つの頂点は、V 2のうちの1つの頂点にのみ隣接しているため、相異性条件を満たさず、(3)において完全な一致は存在しない.一方,(1),(2)はいずれも相異性条件を満たすため,完全なマッチングが存在する.
定理18.5からは、以下の定理も得られる.
定理18.6は、二部図G=において、V 1の各頂点が少なくともt(t≧1)のエッジを関連付け、V 2の各頂点がtのエッジまで関連付けられると、GにはV 1~V 2の完全なマッチングが存在するとする.
定理中の条件から分かるように、V 1中の任意のk(1≦k≦|V 1|)個の頂点は、少なくともkt個のエッジに関連付けられているが、V 2中の各頂点は、t個のエッジに関連付けられているため、このkt個のエッジは、少なくともV 2中のk個の頂点に関連付けられている.
定理18.6と呼ばれる条件はt条件である.図18.4において、(2)はt=2のt条件を満たし、もちろん完全マッチングが存在し、(1)はt条件を満たしていないが、相異性条件を満たすため、完全マッチングが存在する.
ハンガリーアルゴリズムの核心は、Pが図Gの2つの非整合頂点を連通する経路であり、Mに属するエッジとMに属さないエッジ(すなわち、整合されたエッジと整合されるエッジ)がP上に交互に現れる場合、PをMに対する拡張経路と呼ぶ.(Mは一致)を選択し、このパスを反転すると、一致するエッジが1増加します.
C言語コード:
#include<stdio.h>
#include<string.h>
bool g[201][201];
int n,m,ans;
bool b[201];
int link[201];
bool init()
{
int _x,_y;
memset(g,0,sizeof(g));
memset(link,0,sizeof(link));
ans=0;
if(scanf("%d%d",&n,&m)==EOF)return false;
for(int i=1;i<=n;i++)
{
scanf("%d",&_x);
for(int j=0;j<_x;j++)
{
scanf("%d",&_y);
g[ i ][_y]=true;
}
}
return true;
}
bool find(int a)
{
for(int i=1;i<=m;i++)
{
if(g[a][ i ]==1&&!b[ i ])
{
b[ i ]=true;
if(link[ i ]==0||find(link[ i ]))
{
link[ i ]=a;
return true;
}
}
}
return false;
}
int main()
{
while(init())
{
for(int i=1;i<=n;i++)
{
memset(b,0,sizeof(b));
if(find(i))ans++;
}
printf("%d
",ans);
}
}http://course.cug.edu.cn/21cn/%E7%A6%BB%E6%95%A3%E6%95%B0%E5%AD%A6%EF%BC%88%E5%8C%97%E5%A4%A7%EF%BC%89/part4/chapter18/18_03_02_01.htm
二、Hall定理
定理18.5
(
ホールの定理
)二部図G=
,V
2
,E>中,|V
1
|≤|V
2
|.GにはVから
1
Vまで
2
の完全一致は、V
1
中任意k(k＝1,2,…,｜V
1
|)個の頂点は少なくともV
2
のk個の頂点が隣接しています.
本定理の条件を「相異性条件」と呼ぶことが多い.
証定理の必要性は明らかである.以下では,相異性条件を満たす限り,Gにおける最大整合が完全整合であることを証明する.MをGの中の1つの最大マッチングとする.Mが完全整合でなければ,vx∈V 1がMである非飽和点が必ず存在する.e∈E 1=E−Mがvxに関連付けられる必要があります.そうしないと、vxは孤立点になり、相異性条件と矛盾します.また,V 2におけるvxに隣接する頂点はすべてM−飽和点であり,vy∈V 2(vxに隣接する)が非飽和点である場合,M′=M∈(vx,vy)も一致し,これは明らかにMが最大整合であることと矛盾する.vxからの可能な限り長いすべてのインタリーブ経路を考慮すると、Mは最大整合であるため、定理18.4から分かるように、これらのインタリーブ経路は拡張可能ではない.すなわち、各経路がvxと異なる端点はM−飽和点であるに違いない.そこで、これらの端点はすべてV 1にあり、
S={v|v∈V 1,vはvxからのインタリーブ経路上}T={v|v∈V 2,vはvxからのインタリーブ経路上}
各交錯経路の2つの端点が全てS中であるため、|S|=|T|+1となる.これはV
1
中|T|+1個の頂点はVのみ
2
中|T|個の頂点が隣接しており、これは相異性条件と矛盾しているため、V
1
中にはM−非飽和点は存在し得ないので,Mは完全整合である.
図18.4(3)において、V 1に存在する2つの頂点は、V 2のうちの1つの頂点にのみ隣接しているため、相異性条件を満たさず、(3)において完全な一致は存在しない.一方,(1),(2)はいずれも相異性条件を満たすため,完全なマッチングが存在する.
定理18.5からは、以下の定理も得られる.
定理18.6は、二部図G=
定理中の条件から分かるように、V 1中の任意のk(1≦k≦|V 1|)個の頂点は、少なくともkt個のエッジに関連付けられているが、V 2中の各頂点は、t個のエッジに関連付けられているため、このkt個のエッジは、少なくともV 2中のk個の頂点に関連付けられている.
定理18.6と呼ばれる条件はt条件である.図18.4において、(2)はt=2のt条件を満たし、もちろん完全マッチングが存在し、(1)はt条件を満たしていないが、相異性条件を満たすため、完全マッチングが存在する.