組合せとグラフの理論(塩田)2023年度 第12回

 インターネット上ではパケット通信が行われ、データは複数の経路を経由して送られています。 回線にはそれぞれ「回線容量」と言って、単位時間あたりに送受信できるデータ量の上限が決まっています。 この状況下で2つのコンピュータ間で最大でどのくらいのデータが送れるかが問題になります。
 このような問題を扱う「ネットワークフロー」を今日は勉強します。

  1. フローとは何か?
  2. 定式化
  3. 最大フローアルゴリズム
  4. 最大フローアルゴリズム実行例
  5. $a^{-1}$ を考える理由
  6. デモ動画、今日のまとめと宿題

配布プリント