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

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

今回は、Julia(Graphs)で最大フロー問題を解き、図示する方法を紹介します。

前提知識:フローネットワークとは:Juliaで図示する方法

 



準備

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

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

 

最大フロー問題を解き、図示する方法

最大フロー問題とは

ある地点から別の地点に水や電気、物資や人を送る問題は、フローネットワークとして定式化されます。

ネットワークとは始点(ソース)と終点(シンク)のある有向グラフで、各辺にキャパシティと呼ばれる量が割り当てられています。

上の図は、キャパシティとフローの一例です。各辺にかかれている第1成分がキャパシティ、第2成分がフローの値です。

フローとは、キャパシティの値を超えず、各頂点で出入りする量が保存される辺の関数です。

ソースから出ていく総量を、合計フローと呼び、\(\mathrm{total }(f):= \sum_{j}f(ソース,j)\)と書きます。

 

与えられたネットワークに対して、フローとしては様々な可能性が考えられます。例えば、すべて0であるフロー(ゼロフロー)です。

今回考える問題は、ネットワークが与えられたとき、合計フローを最大にするようなフローを見つける問題です。これは最大フロー問題(maximum flow problem)として知られています。

応用としては、できるだけ多くの水や人を送りたい、といった問題に対応します。

 

簡単な例

では、簡単な例で最大フローを求めてみましょう。

まず、フローネットワークのプロットで用意した関数を導入し、さきほど示した図を得てみましょう。

 

 

最大フローを求める関数には、引数としてキャパシティを行列の形で与える必要があります。

キャパシティベクトルを行列に変換する関数を作りましょう。

この行列は例えば、\((1,2)\)成分=頂点1から2へ向かう辺のキャパシティが\(5.0\)であることを示しています。

 

「maximum_flow(グラフ,ソース,シンク,キャパシティ行列)」という関数で、与えられたネットワークの最大フローを求められます。

デフォルトでは、プッシュ・リラベル最大フローアルゴリズム(Push–relabel maximum flow algorithm)と呼ばれる方法が使われています。

第1成分が合計フロー、第2成分がフローを行列として表示したものです。

 

フローを今までと同じように図示するために、この行列をベクトルに変換しましょう。

 

これを使えば、最大フローが図示できます。

最初に図示したフロー合計は4でしたが、このフローの合計は6で、最大化されている(らしい)ことがわかりますね。

 

一般化

以上の結果を一般化して、ネットワークを与えたら、その最大フローの合計フローを求め、図示する関数を作りましょう。

 

別の例として、次のネットワークを考えます。

 

さきほどの関数を使えば、最大フローが簡単に求められます。

 

以上、Julia(Graphs)で最大フロー問題を解き、図示する方法を紹介してきました。

与えられたネットワークのフローの候補はたくさんあるので、手計算で求めるのは、不可能ではありませんが大変です。

最大フロー問題を解くアルゴリズムはいくつかありますが、それを学ぶにあたっても、まずは今回のように具体的に問題を解いてみてはいかがでしょうか。

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

 

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

 

こちらもおすすめ

フローネットワークとは:Juliaで図示する方法

グラフ理論入門:グラフとは、グラフの同型

Julia(Graphs)でグラフ理論におけるグラフ作成、次数、隣接行列を求める方法