ネットワークフロー問題 - 版の履歴

2008年11月13日 (木) 04:30にAlbeit-Kunによる

2008-11-13T04:30:09Z

2008年8月6日 (水) 03:15にImahoriによる

2008-08-06T03:15:46Z

Imahori: 基礎編と用語編のマージ

2008-03-13T14:08:33Z

基礎編と用語編のマージ

2007年8月8日 (水) 11:55にKanda.kによる

2007-08-08T11:55:00Z

Orsjwiki: "ネットワークフロー問題" を保護しました。 [edit=sysop:move=sysop]

2007-07-20T01:20:46Z

"ネットワークフロー問題" を保護しました。 [edit=sysop:move=sysop]

2007年7月17日 (火) 07:05に122.17.2.240による

2007-07-17T07:05:44Z

122.17.2.240: 新しいページ: '【ねっとわーくふろーもんだい (network flow problem)】ネットワーク上のフローを扱う最適化問題の総称. 最大フロー問題, 最小費用フ...'

2007-07-12T15:05:57Z

新しいページ: '【ねっとわーくふろーもんだい (network flow problem)】ネットワーク上のフローを扱う最適化問題の総称. 最大フロー問題, 最小費用フ...'

新規ページ

【ねっとわーくふろーもんだい (network flow problem)】

ネットワーク上のフローを扱う最適化問題の総称. 最大フロー問題, 最小費用フロー問題, 輸送問題, 多品種フロー問題, 利得/損失付きフロー問題(一般化フロー問題)などがある. 最短路問題, 割当問題, 最小カット問題もネットワークフロー問題として扱うこともある.

← 古い版		2008年11月13日 (木) 04:30時点における版
87行目:		87行目:

	[[Category:グラフ･ネットワーク\|ねっとわーく・ふろーもんだい]]		[[Category:グラフ･ネットワーク\|ねっとわーく・ふろーもんだい]]
		+
		+	[[Category:組合せ最適化\|ねっとわーく・ふろーもんだい]]

@@ 16行目: / 16行目: @@
 を満たす<math>\varphi\, </math>をフローといい，フローを扱った最適化問題を[[ネットワークフロー問題]]という [1] ．ただし，<math>\delta^+v (\delta^-v)\, </math>は点<math>v\, </math>から出る (へ入る) 枝の全体を表す．
-　代表的なネットワーク・フロー問題に最大フロー問題がある．最大フロー問題とは，特別な点として入口<math>s\, </math>と出口<math>t\, </math>があり，<math>s, t\, </math>以外での供給量<math>d(v)\, </math>が0であるとき，<math>s\, </math>から入る量 (フロー値) を最大にするようなフロー (最大フロー) を求める問題であり，以下のように定式化できる．
+　代表的なネットワークフロー問題に最大フロー問題がある．最大フロー問題とは，特別な点として入口<math>s\, </math>と出口<math>t\, </math>があり，<math>s, t\, </math>以外での供給量<math>d(v)\, </math>が0であるとき，<math>s\, </math>から入る量 (フロー値) を最大にするようなフロー (最大フロー) を求める問題であり，以下のように定式化できる．
@@ 53行目: / 53行目: @@
 　増加道が存在しなくなったとき，<math>{\mathcal N}_\varphi\, </math>上で<math>s\, </math>から到達可能な点集合を<math>X\, </math>とすると，<math>X\, </math>は<math>s-t\, </math>カットであり，その容量はフロー値と一致する．よって，増加道法が終了したときのフローが最大フローであり，<math>X\, </math>が最小カットである．
-　増加道の選択を，枝数最小や，<math>\varepsilon\, </math>最小の基準で行うと，多項式時間の[[最大フローアルゴリズム]]となる．一方，流量保存則を緩和したプリフローを用い，増加道が存在しないようなプリフローを維持しながら，最大フローを求めるプッシュ・再ラベル法も効率よい最大フロー・アルゴリズムである．
+　増加道の選択を，枝数最小や，<math>\varepsilon\, </math>最大の基準で行うと，多項式時間の[[最大フローアルゴリズム]]となる．一方，流量保存則を緩和したプリフローを用い，増加道が存在しないようなプリフローを維持しながら，最大フローを求めるプッシュ・再ラベル法も効率よい最大フローアルゴリズムである．
 　[[最小費用フロー問題]]もネットワーク・フロー問題の一つである．各枝<math>a\, </math>のフロー1単位あたりの費用<math>\gamma(a)\, </math>が与えられているとき，総費用<math>\textstyle {\sum}_{a \in A}\gamma(a)\varphi(a)\, </math>を最小にするフローを求める問題である．特に，すべての点で供給量<math>d(v)=0\, </math>のとき，[[循環フロー]]という．また，[[輸送問題]]も最小費用フロー問題の特殊ケースである．複数の供給地と需要地があり，各々の供給/需要量と，各供給地と需要地間の輸送費用がわかっているとき，供給/需要を満たし，輸送にかかる総費用を最小とする輸送方法とその輸送量を決定する輸送問題は，容量制約のない2部グラフ上の最小費用フロー問題である．
-　最小費用フロー・アルゴリズムも多数ある．補助ネットワーク<math>{\mathcal N}_\varphi\, </math>上の費用を
+　最小費用フローアルゴリズムも多数ある．補助ネットワーク<math>{\mathcal N}_\varphi\, </math>上の費用を
@@ 79行目: / 79行目: @@
 [2] L. R. Ford, Jr. and D. R. Fulkerson, ''Flows in Networks'', Princeton University Press, 1962.
 [[Category:グラフ･ネットワーク|ねっとわーく・ふろーもんだい]]

@@ 1行目: / 1行目: @@
 '''【ねっとわーくふろーもんだい (network flow problem)】'''
 ネットワーク上のフローを扱う最適化問題の総称. 最大フロー問題, 最小費用フロー問題, 輸送問題, 多品種フロー問題, 利得/損失付きフロー問題(一般化フロー問題)などがある. 最短路問題, 割当問題, 最小カット問題もネットワークフロー問題として扱うこともある.
-詳しくは[[《ネットワーク・フロー問題》|基礎編：ネットワーク・フロー問題]]を参照.
+=== 詳説 ===

← 古い版		2007年8月8日 (水) 11:55時点における版
2行目:		2行目:

	ネットワーク上のフローを扱う最適化問題の総称. 最大フロー問題, 最小費用フロー問題, 輸送問題, 多品種フロー問題, 利得/損失付きフロー問題(一般化フロー問題)などがある. 最短路問題, 割当問題, 最小カット問題もネットワークフロー問題として扱うこともある.		ネットワーク上のフローを扱う最適化問題の総称. 最大フロー問題, 最小費用フロー問題, 輸送問題, 多品種フロー問題, 利得/損失付きフロー問題(一般化フロー問題)などがある. 最短路問題, 割当問題, 最小カット問題もネットワークフロー問題として扱うこともある.
		+
		+	詳しくは[[《ネットワーク・フロー問題》\|基礎編：ネットワーク・フロー問題]]を参照.

← 古い版		2007年7月17日 (火) 07:05時点における版
1行目:		1行目:
−	【ねっとわーくふろーもんだい (network flow problem)】	+	'''【ねっとわーくふろーもんだい (network flow problem)】'''

	ネットワーク上のフローを扱う最適化問題の総称. 最大フロー問題, 最小費用フロー問題, 輸送問題, 多品種フロー問題, 利得/損失付きフロー問題(一般化フロー問題)などがある. 最短路問題, 割当問題, 最小カット問題もネットワークフロー問題として扱うこともある.		ネットワーク上のフローを扱う最適化問題の総称. 最大フロー問題, 最小費用フロー問題, 輸送問題, 多品種フロー問題, 利得/損失付きフロー問題(一般化フロー問題)などがある. 最短路問題, 割当問題, 最小カット問題もネットワークフロー問題として扱うこともある.

← 古い版	2007年7月20日 (金) 01:20時点における版
(相違点なし)