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

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

今回は、フローネットワークとは何か、Julia(Graphs)で図示する方法を紹介します。

前提知識:グラフ理論入門:グラフとは、グラフの同型Julia(Graphs)でグラフ理論におけるグラフ作成、次数、隣接行列を求める方法

 

フローネットワークとは

ある出発点から別の終点に、水や電気、情報や物資や人を効率よく送りたい。そんな問題(輸送問題)を考えるとき、フローネットワーク(flow network)の考え方が役に立ちます。

例えば、ある地域で災害があったときに、できるだけ多くの人が速く安全な地点まで避難したい。そんなときに、どの道をどのくらいの人が通れば良いか。その問題は、最速避難計画問題と呼ばれています。

参考:最速避難計画のモデリングと解法 – 日本オペレーションズ・リサーチ

 

フローネットワークは、グラフ理論によって定式化されます。

まず、辺に向きのあるグラフ(有向グラフ)\(G=(V,E)\)を考えましょう。そこに区別される2つの頂点、出発点と終点、ソース(source)とシンク(sink)があります。ソースを黄色に、シンクを紫色にしました。

各辺にかかれている数字は、人や水が通れる限界量を示しています。一般に、各辺に対して非負の値を対応させる関数\(c: E \to [0,\infty)\)をキャパシティ(capacity)、容量と呼びます。上の図の例ならば、例えば\(c(1,2)=5\)、\(c(2,3)=2\)です。

そして、有向グラフ、ソース、シンク、キャパシティの組をまとめて、ネットワーク(network)と呼びます。

 

ネットワークの上を、水が流れたり、人が通ったりする状況を表しましょう。

辺の上に書かれている数字が増えました。第1成分がキャパシティ、第2成分が流れている量:フローです。

(実行可能な)フロー(flow)とは、辺に対し非負値を割り当てる関数\(f: E \to [0,\infty)\)で、

  • キャパシティ条件:すべての辺\((i,j) \in E\)に対し、\(f(i,j) \leq c(i,j)\)
  • 量の保存:ソースとシンク以外のすべての頂点\(i \in V\)に対し、入ってくるフロー(inflow)と出ていくフロー(outflow)が等しい。
    • \(\sum_{k}f(k,i) = \sum_{j} f(i,j)\)
  • 量の保存:\(\sum_{j}f(ソース,j) = \sum_{k} f(k,シンク)\)

を満たすものです。

上の図の辺に書かれた情報\((c,f)\)を見て、フローの条件を満たすことをチェックしてみてください。(慣習によっては、\((c,f)\)ではなく\(f/c\)と逆の順序で書かれていることもあります。)

まず、右側の数字は左側の数字を超えません。キャパシティ以上にフローを流すことはできないわけです。

そして、途中の頂点では、入ってくるフローと出ていくフローが必ず等しいです。どこかに漏れてしまったりはしないと仮定しているわけですね。頂点\(4\)に注目すれば、入ってくるフローの合計は\(f(2,4)+f(3,4)=1+2=3\)、出ていくフローの合計は\(f(4,5)+f(4,6)=2+1=3\)と等しいです。他の頂点でもチェックしてみてください。

さらに、ソースから出ていくフローとシンクが受け取るフローは等しいです。\(f(1,2)+f(1,3)=1+3=4\)、\(f(4,6)+f(5,6)=4\)ですね。

ソースから出ていく総量を、合計フロー(total flow)、フローの値(value of flow)と呼びます。つまり、\(\mathrm{total }(f):= \sum_{j}f(ソース,j)\)です。この値を、単にフローと呼んでいることもあるので注意。

 

与えられたネットワークに対して、フローとしては様々な可能性が考えられます。

例えば、すべての辺に何も流さない\(f(i,j)=0\)はフローの定義を満たしますね(チェックしてみてください)。これをゼロフローと呼びます。

 

ただし、何も流れないフローを考えたのでは、役に立ちそうにありませんね。

例えば、できるだけ多くの水や人を送りたい、つまり合計フローを最大化するフローを求めることはできないでしょうか。これは最大フロー問題として知られています。別記事で紹介予定。

 

Juliaで図示する方法

フローとネットワークの考え方を一通り知ったところで、使ってきた図をJuliaで描く方法を紹介します。

準備

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

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

 

簡単な例

まず、次のような有向グラフを考えましょう。

「DiGraph(6)」で6頂点で(辺のない)有向グラフを作成。その後、辺の候補を作って、「Graphs.add_edge!」で辺を追加しました。

 

各辺に対するキャパシティは、キャパシティベクトルとして与えられます。

 

また、ソースとシンクを色を変えて図示しましょう。次のように色のベクトルが作れます。

 

以上の情報を使って、グラフをプロットしましょう。辺の上に描く数字をキャパシティベクトル、頂点の色を指定しています。

 

さらに、フローの具体例も図示しましょう。

フローもキャパシティと同様に、フローベクトルとして与えられます。

キャパシティとベクトルの組を作って、それを使って辺のラベルを描きましょう。

 

関数による一般化

今までの結果を一般化したのが、次の関数です。

 

 

別のネットワーク、フローを考えて、関数で図示してみましょう。

 

 

うまくプロットできていますね。

 

以上、フローネットワークとは何か、Julia(Graphs)で図示する方法を紹介してきました。

輸送に関する問題が、フローネットワークによって定式化できるのがわかりました。最大フロー問題については、別記事で紹介します。

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

 

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

 

こちらもおすすめ

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

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