Julia(Glaphs)で2部グラフの最大マッチングを求め、図示する方法

どうも、木村(@kimu3_slime)です。

今回は、Julia(Glaphs)で2部グラフの最大マッチングを求め、図示する方法を紹介します。

前提知識:Julia(Graphs)で2部グラフかどうかを判別し、図示する方法Julia(Graphs)で最大フロー問題を解き、図示する方法

 

準備

Graphs, GraphPlotColors, GraphsFlowsを使うので、持っていなければインストールしておきましょう。

準備として、以下のコードを実行しておきます。

 

2部グラフの最大マッチングを求め、図示する方法

最大マッチングとは、求め方

グラフ\(G= (V,E)\)のマッチング\(M\)とは、辺の部分集合\(M\subset E\)であって、それらの辺が共通する端点を持たないことです。

一般に、マッチングには複数の可能性があります。その中で、辺の個数が最も多いマッチングを最大マッチング(Maximum cardinality matching)と呼びます。

以下の図で示したグラフにおいて、赤い辺が最大マッチングの例です。

 

最大マッチングを求める方法は、いくつか知られています。

特に2部グラフにおける最大マッチング問題は、最大フロー問題に帰着させることができます。

  • 2部グラフの頂点の集合を分けた集合を\(V_1,V_2\)とする。
  • \(V_1\)から\(V_2\)へと向きをつけた辺を持つグラフを考える。
  • ソースとシンクとして新たな頂点2つを加え、ソースからは\(V_1\)の各頂点へ、\(V_2\)の各頂点からはシンクへの向きをつけた辺を加える。
  • すべての辺のキャパシティを等しく1とする。
  • こうしてできるネットワークの最大フロー問題の解が、元の2部グラフの最大マッチングに対応する。

 

参考:離散数学入門#11: マッチング(2):最大マッチングを見つける2つの方法 – Momoko Hayamizu

今回はこの方法に従って、最大マッチングを求めましょう。

 

簡単な例

まず、2部グラフの描写に用いる関数を導入します。

 

最初に考えるのは、次の簡単な2部グラフです。

 

これに新たな頂点(ソースとシンク)を加え、有向グラフを作りましょう。

頂点をグループ分けする集合\(V_1,V_2\)は、「bipartite_map」で求められます。

頂点数を2つ増やした有向グラフを作り、元のグラフの\(V_1,V_2\)の情報を使って有向辺を加え、ソースとシンクに\(V_1,V_2\)を対応させる辺を加えます。

\(6\)がソース、\(7\)がシンクです。

 

以前作った最大フローをプロットする関数を使い、すべてのキャパシティを1としたネットワークの図示をしましょう。

 

これで最大フローが求められました。

辺にかかれている第2成分の数値がフローであり、それが\(1.0\)である辺が最大マッチングに対応する辺です。

 

一般化

以上の結果を、一般化した関数を作りましょう。

これで無向2部グラフを与えると、拡大した有向グラフのキャパシティ1のときの最大フローを、辺とフローの組として返してくれます。

元のグラフで図示するには、加えた頂点(ここでは\(6,7\))を含む辺を無視し、フローの値が\(1.0\)となる辺を色付けすれば良いでしょう。

 

少し複雑ですが、最大マッチングを図示する関数は次のようになります。

「edgecolor」に、最大マッチングの色情報を代入しています。最大フローの辺の端点がソースまたはシンクでなければ、その辺のもとのグラフにおける辺番号(indexin)に、トマト色を指定しました。

 

これで求める結果が得られました。

 

別のグラフを考え、適切な結果が得られるか見てみましょう。

ヒーウッドグラフ(Heawood graph)

 

彩色された辺はすべて独立(共通する頂点を含まない)で、すべての頂点がマッチしているので、これは確かに最大マッチングです。

 

パップスグラフ(Pappus graph)

 

最後に、最大マッチングでもマッチングできない頂点が生まれるようなグラフ(完全マッチングを持たないグラフ)を考えましょう。

 

以上、Julia(Glaphs)で2部グラフの最大マッチングを求め、図示する方法を紹介してきました。

GraphsMatching.jlというパッケージでも最大マッチングは求められるようなのですが、僕の環境だとうまくインストールできませんでした。

今回の方法ならば最大フローさえ求めれれば使えるので(GraphsFlows.jl)、参考になれば嬉しいです。

木村すらいむ(@kimu3_slime)でした。ではでは。

 

1から始める Juliaプログラミング
進藤 裕之(著), 佐藤 建太(著)
コロナ社 (2020-03-26T00:00:01Z)
5つ星のうち4.5
¥7,353 (コレクター商品)

 

こちらもおすすめ

グラフ理論における2部グラフ、マッチング、結婚定理とは

Julia(Graphs)で2部グラフかどうかを判別し、図示する方法

Julia(Graphs)で最大フロー問題を解き、図示する方法