翻訳と辞書 Words near each other ・ フォード・トランジット コネクト ・ フォード・トリノ ・ フォード・トリノ・コブラ ・ フォード・トリノ・タラデガ ・ フォード・トーラス ・ フォード・トーラスX ・ フォード・ニューエッジデザイン ・ フォード・ニュークレオン ・ フォード・ピント ・ フォード・ファイブハンドレッド ・ フォード・ファルカーソンのアルゴリズム ・ フォード・ファルコン (オーストラリア) ・ フォード・フィエスタ ・ フォード・フィエスタ RS WRC ・ フォード・フィエスタWRC ・ フォード・フィールド ・ フォード・フェアレーン500 ・ フォード・フェアレーンの冒険 ・ フォード・フェアレーン・コブラ ・ フォード・フェスティバ Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク フォード・ファルカーソンのアルゴリズム ： ウィキペディア日本語版 フォード・ファルカーソンのアルゴリズム フォード・ファルカーソンのアルゴリズム（）とは、フローネットワークにおける最大フローを求めるアルゴリズムである。 と にちなんで命名されたもので、1956年に発表された。フォード・ファルカーソンのアルゴリズムの特殊版であるエドモンズ-カープアルゴリズムも「フォード・ファルカーソン」と呼ばれることがある。 このアルゴリズムの背景にある考え方は非常に単純である。始点から終点への経路があって、経路上の各辺に容量の空きがあるとき、その経路を使って流れを作ることができる。これを経路が見つかるたびにくりかえす。容量に空きがある経路を「増加道; 」と呼ぶ。 == アルゴリズム == グラフ $G(V,E)$ にて、$u$ から $v$ への容量 $c(u,v)$ でフロー $f(u,v)=0$ とする。ここで、始点 $s$ から終点 $t$ への最大フローを求める。最終的に、次のような状態となる。 * $\backslash \; f(u,v)\; \backslash leq\; c(u,v)$ : $u$ から $v$ へのフローは容量を超えない。 * $\backslash \; f(u,v)\; =\; -\; f(v,u)$ : $u$ と $v$ の間の総フローの性質。$u$ から $v$ へのフローが $a$、$v$ から $u$ へのフローが $b$ であるとき、$f(u,v)=a-b$ であり、かつ $f(v,u)=b-a$ となる。 * $\backslash \; \backslash sum\_v\; f(u,v)\; =\; 0\; \backslash Longleftrightarrow\; f\_(u)\; =\; f\_(u)$ : $s$ と $t$ を除く全てのノード $u$ で成り立つ。あるノードに流れ込むフローとそこから出て行くフローは常に等しい。 すなわち、ネットワーク上のフローは、アルゴリズムの毎回の適用後に常に正当なものとなる。ここで、残余ネットワーク $G\_f(V,E\_f)$ を容量が $c\_f(u,v)\; =\; c(u,v)\; -\; f(u,v)$ で、フローのないネットワークと定義する。ただし、$u,v$ のフローによって $u,v$ がクローズ（満杯）となっても $v,u$ は残余ネットワークに残る可能性があるため、$E=E\_f$ となるかどうかは定かではない。 アルゴリズム フォード・ファルカーソン :入力 フロー容量 $\backslash ,c$、始点 $\backslash ,s$、終点 $\backslash ,t$ のグラフ $\backslash ,G$ :出力 $\backslash ,s$ から $\backslash ,t$ へのフロー $\backslash ,f$ の最大値 :# 全ての枝 $\backslash ,(u,v)$ について $f(u,v)\; \backslash leftarrow\; 0$ とする。 :# $\backslash ,G\_f$ 内で $\backslash ,s$ から $\backslash ,t$ への経路 $\backslash ,p$ があり、経路上の全ての枝 $(u,v)\; \backslash in\; p$ について $\backslash ,c\_f(u,v)\; >\; 0$ であるとき: :## $\backslash ,c\_f(p)\; =\; \backslash min\backslash$ を求める。 :## $(u,v)\; \backslash in\; p$ であるような各枝について :### $f(u,v)\; \backslash leftarrow\; f(u,v)\; +\; c\_f(p)$ （この枝にそってフローを送る） :### $f(v,u)\; \backslash leftarrow\; f(v,u)\; -\; c\_f(p)$ （フローは後で返される） 経路は、$G\_f(V,E\_f)$ について、例えば幅優先探索や深さ優先探索を行うことで得られる。前者の場合を特にエドモンズ-カープアルゴリズムと呼ぶ。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「フォード・ファルカーソンのアルゴリズム」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.