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