組合せとグラフの理論(塩田)第12回 (1) フローとは何か?
フロー(流れ)とは何か?
問 1 例えば次のような単純なコンピュータネットワークを考えましょう。
数字は回線容量を表すとします。
(単位は例えば Mbps = 1秒間に何メガビット送れるか、とします。)
パケット通信を用いて複数の経路を経由してデータが送れるとしたとき、
サーバからクライアントへの最大通信容量はいくらでしょうか?
データが流れるとは?
データが安定して流れていると、次の2つが成り立ちます。
- 各回線では、回線容量を超えない範囲でデータが送られている
- 各中継点ではデータの流入量と流出量が釣り合っている
(1) は、川で例えると、流せる上限を超える量の水はあふれてしまうということです。
(2) は、
- 流入量が流出量を超えたらデータが中継点に溜まってしまうし
- 届いてもないデータは送り出せない
ということです。
イマジネーションを働かせてみてください。
問 1 の答え 次のようにデータを送れば 7Mbps の通信容量が実現できます。
それぞれの回線容量を超えていないことを確かめてください。
また中継点 $A$ では流入量 $5$ と 流出量 $2+3$ が釣り合っていますし、
中継点 $B$ では流入量 $2+2$ と 流出量 $4$ が釣り合っていますね。
中継点で流入量と流出量が釣り合っているので、
必然的に、サーバからの送信量 $5+2=7$ がクライアントの受信量 $3+4=7$ に一致しています。