二分図の最大マッチング、完璧マッチング、ハンガリーアルゴリズム

変換元:http://www.renfei.org/blog/bipartite-matching.html
この文章は無権二分図(unweighted bipartite graph)の最大整合(maximum matching)と完璧整合(perfect matching)と整合を解くハンガリーアルゴリズム(Hungarian Algorithm)について述べる.重み付き二分図の最適マッチングは言わない.
二分図:簡単に言えば、図中の点が2つのグループに分けられ、すべてのエッジがグループの境界を越えることができる場合、これは二分図です.正確には、1つの図の頂点を2つの非交差セットUとVに分割し、各エッジがU、Vの頂点にそれぞれ接続されるようにする.このような区分が存在する場合、この図は二分図である.二分図の等価定義の1つは、「奇数辺を含むリング」を含まない図である.図1は二分図である.明確にするために、私たちはこれからそれを図2の形式に描きます.
マッチング:図論では、1つの「マッチング」(matching)はエッジの集合であり、いずれのエッジにも共通の頂点はありません.例えば、図3、図4の赤色のエッジが図2のマッチングである.
        
マッチングポイント、マッチングエッジ、未マッチングポイント、非マッチングエッジを定義します.これらの意味は非常に明らかです.例えば、図3の1、4、5、7はマッチングポイントであり、他の頂点は未マッチングポイントである.1-5、4-7は一致するエッジであり、他のエッジは非一致のエッジである.
≪最大一致|Maximum Match|emdw≫:1つの図のすべての一致のうち、一致するエッジ数が最も多い一致を、この図の最大一致と呼びます.図4は、4つのマッチングエッジを含む最大マッチングである.
≪完全一致|Complete Match|emdw≫:図の一致ですべての頂点が一致点である場合、それは完全な一致です.図4は完璧なマッチングです.完璧な一致は必ず最大の一致であることは明らかです(完璧な一致のいずれかの点が一致しており、新しい一致エッジを追加すると、既存の一致エッジと衝突するに違いありません).しかし、各図に完璧な一致があるわけではありません.
例えば、下図に示すように、男の子と女の子の間につながっているエッジがある場合は、お互いが好きであることを意味します.すべての男の子と女の子をペアにして、すべてのペアがお互いに好きになることができますか?図論では,これが完璧なマッチング問題である.言い換えれば、お互いに好きな男の子/女の子がペアになれるのはどれくらいですか?これが最大マッチング問題です.

基本概念は終わりました.最大マッチング問題を解くアルゴリズムの1つはハンガリーアルゴリズムであり,以下の概念はすべてこのアルゴリズムに奉仕する.

交互路:1つの未整合点から、非整合辺、整合辺、非整合辺...を順次通過する経路を交互路と呼ぶ.
拡張路:1つの未整合点から交互路を歩き、別の未整合点(出発点は計算されない)を経由する場合、この交互路を拡張路(agumenting path)と呼ぶ.例えば、図5の1つの拡張路は、図6に示すように(図中の一致点はいずれも赤色で示されている):

拡張路には重要な特徴があります.非マッチングエッジはマッチングエッジより1つ多いです.従って,拡張路の研究の意義は整合を改善することである.拡張路のマッチングエッジと非マッチングエッジのアイデンティティを交換すればよい.中間のマッチングノードには他の接続されたマッチングエッジが存在しないため、マッチングの性質を破壊することはありません.交換後,図中のマッチングエッジ数は従来より1本多くなった.
拡張路を絶えず探すことで,マッチングにおけるマッチングエッジとマッチングポイントを増加させることができる.拡張路が見つからない場合、最大マッチングに達します(これは拡張路の定理です).ハンガリーのアルゴリズムはまさにそうしています.ハンガリーアルゴリズムDFSとBFSバージョンのコードを与える前に、ハンガリーツリーについて説明します.
ハンガリーの木は一般的にBFSで構成されている(BFSの木に似ている).1つの非整合点からBFSを実行する(唯一の制限は、これ以上拡張できないまで交互の道を歩かなければならない).例えば、図7から、図8のようなBFSツリーが得られる.
        
この木には葉ノードが非整合点(7番)であるが、ハンガリーの木はすべての葉ノードが整合点であることを要求しているため、ハンガリーの木ではない.原図に7番ノードが含まれていなければ、2番ノードからハンガリーの木が1本もらえます.この場合、図9に示すように(ちなみに、図8のルートノード2から非整合リーフノード7までは明らかに増幅路であり、この増幅路に沿って拡張すると完全なマッチングが得られる).
ハンガリーアルゴリズムのDFSとBFSバージョンのコードを次に示します.

//   、       0   
//      

struct Edge
{
    int from;
    int to;
    int weight;

    Edge(int f, int t, int w):from(f), to(t), weight(w) {}
};

vector<int> G[__maxNodes]; /* G[i]      i         */
vector<Edge> edges;
typedef vector<int>::iterator iterator_t;
int num_nodes;
int num_left;
int num_right;
int num_edges;

int matching[__maxNodes]; /*        */
int check[__maxNodes];

bool dfs(int u)
{
    for (iterator_t i = G[u].begin(); i != G[u].end(); ++i) { //   u       
        int v = edges[*i].to;
        if (!check[v]) {     //         
            check[v] = true; //      
            if (matching[v] == -1 || dfs(matching[v])) {
                //       ，         ，     ，     
                matching[v] = u;
                matching[u] = v;
                return true;
            }
        }
    }
    return false; //       ，    
}

int hungarian()
{
    int ans = 0;
    memset(matching, -1, sizeof(matching));
    for (int u=0; u < num_left; ++u) {
        if (matching[u] == -1) {
            memset(check, 0, sizeof(check));
            if (dfs(u))
                ++ans;
        }
    }
    return ans;
}

queue<int> Q;
int prev[__maxNodes];
int Hungarian()
{
    int ans = 0;
    memset(matching, -1, sizeof(matching));
    memset(check, -1, sizeof(check));
    for (int i=0; i<num_left; ++i) {
        if (matching[i] == -1) {
            while (!Q.empty()) Q.pop();
            Q.push(i);
            prev[i] = -1; //   i      
            bool flag = false; //        
            while (!Q.empty() && !flag) {
                int u = Q.front();
                for (iterator_t ix = G[u].begin(); ix != G[u].end() && !flag; ++ix) {
                    int v = edges[*ix].to;
                    if (check[v] != i) {
                        check[v] = i;
                        Q.push(matching[v]);
                        if (matching[v] >= 0) { //       
                            prev[matching[v]] = u;
                        } else { //       ，        
                            flag = true;
                            int d=u, e=v;
                            while (d != -1) {
                                int t = matching[d];
                                matching[d] = e;
                                matching[e] = d;
                                d = prev[d];
                                e = t;
                            }
                        }
                    }
                }
                Q.pop();
            }
            if (matching[i] != -1) ++ans;
        }
    }
    return ans;
}

ハンガリーアルゴリズムのポイントは以下の通りです.
左の1番目の頂点から、一致していない点を選択して検索し、拡張路を探します.
一致しないポイントが経過した場合は、検索に成功したことを示します.パス情報を更新し、エッジ数+1に一致し、検索を停止します.
拡張路が見つからない場合は、この点から検索を開始しません.実際、この時検索するとハンガリーの木が形成されます.結果に影響を与えることなく、永続的に図から削除することができます.

拡張路が見つかった後、経路に沿ってマッチングを更新する必要があるため、経路上の点を記録する構造が必要です.DFSバージョンは、関数呼び出しによって暗黙的にスタックを使用し、BFSバージョンはprev配列を使用する.
パフォーマンスの比較
両バージョンの時間的複雑度はO(V⋅E)であった.DFSの利点は,構想が明瞭でコード量が少ないことであるが,性能はBFSに及ばない.2つのアルゴリズムの性能をテストした.疎図の場合、BFSバージョンはDFSバージョンより明らかに速い.稠密図については両者に匹敵する.完全ランダムデータ9000個の頂点40000個のエッジの場合、前者のリードは約97.6%、9000個の頂点100000個のエッジの場合、前者のリードは8.6%であり、5000,000個のエッジに達した場合、BFSは0.85%しかリードしていない.
定義と定理の補足:
≪最大一致｜Maximum Matching｜oem_src≫:一致する最大一致エッジの数
最小点オーバーライド数:最小点を選択し、任意のエッジに少なくとも1つの端点を選択します.
≪最大独立数｜Maximum Independent｜oem_src≫:選択した2点が接続されないように、最大の点を選択します.
最小パスオーバーライド数:各頂点が1つのパスに属し、1つのパスのみに属するように、DAG(ループ図なし)の最小パスを選択します.パスの長さは0(単一のポイント)です.
定理1:最大整合数=最小点オーバーライド数(これはKonig定理)
定理2:最大一致数=最大独立数
定理3:最小パスオーバーライド数=頂点数-最大一致数