きままにものづくり

日々の気付いたことなんかを書いてます。

グラフ理論

最大フロー最小カット定理

最大フロー最小カット定理は、最大フロー問題に関する定理である。 この定理は、「最大フローと最小カットの容量は等しい」ということを示す。 目次 関連 証明 関連 この定理は、フォード-ファルカーソンが最大フロー問題に対して正しい答えを導くことを証明…

メンガーの定理

グラフ理論-証明-

最大フロー問題 最大フロー最小カット定理 メンガーの定理

グラフ理論-アルゴリズム-

グラフ理論に関するアルゴリズムを紹介する。 最短経路問題 ベルマン-フォード ダイクストラ ワーシャル-フロイド 最大フロー問題 フォード-ファルカーソン

フォード-ファルカーソン

フォード-ファルカーソン法は、最小フロー問題を解くアルゴリズムのひとつである。 目次 アルゴリズムの説明 計算量 コード アルゴリズムの説明 このアルゴリズムを説明する前に、残余ネットワークの説明をする。残余ネットワークとは、現状での流すことがで…