きままにものづくり

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

2013-08-08から1日間の記事一覧

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

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

メンガーの定理

数論-証明-

グラフ理論-証明-

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

データ構造

データ構造に関しての説明をする。 Union Find Tree Binary Index Tree Segment Tree(未完)

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

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

数論-アルゴリズム-

主に初頭整数論におけるアルゴリズムを説明する。 テクニック MOD乗算 MOD指数演算 理論 ユークリッドの互除法 拡張ユークリッドの互除法 ポラード・ロー素因数分解 モジュラ逆数 中国余剰定理 素数判定 エラトステネスのふるい フェルマーテスト ミラーラビ…

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

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