ネットワークフロー問題

ネットワークフロー問題（ネットワークフローもんだい、英: network flow problems）とは、組合せ最適化の（グラフの辺上に容量の値が課せられた）フローネットワークにおいて各頂点において入るフローと出るフローが同じ量でかつすべての辺において流れるフローがその辺の容量以下となるようなフローを求める問題である。ネットワークフロー問題における特筆すべき問題としては以下のものが挙げられる: 最大流問題：フローネットワークにおいて始点となる頂点から終点となる頂点へ向けてフローを流すとき、最大のフローとなるものを求める問題である。