Поиск максимального потока в транспортной сети - История изменений

ASA в 14:03, 6 марта 2018

2018-03-06T14:03:58Z

← Предыдущая версия		Версия от 14:03, 6 марта 2018
Строка 1:		Строка 1:
			{{level-p}}

	== Постановка задачи ==		== Постановка задачи ==

Nebaruzdin: Исправление формул.

2015-12-08T16:26:51Z

Исправление формул.

← Предыдущая версия		Версия от 16:26, 8 декабря 2015
Строка 15:		Строка 15:

	:<math>		:<math>
	\~~lvert~~ f \~~rvert~~ = \sum_{e = (s, v)} f(e).		\left \vert f \right \vert = \sum_{e = (s, v)} f(e).
	</math>		</math>

	'''Задача о максимальном потоке в транспортной сети.''' Требуется найти поток максимальной величины:		'''Задача о максимальном потоке в транспортной сети.''' Требуется найти поток максимальной величины:
	:<math>\~~lvert~~ f \~~rvert~~ \to \max.</math>		:<math>\left \vert f \right \vert \to \max.</math>

	== Свойства задачи ==		== Свойства задачи ==

ASA в 11:32, 29 июля 2015

2015-07-29T11:32:04Z

← Предыдущая версия		Версия от 11:32, 29 июля 2015
Строка 46:		Строка 46:

	<references />		<references />

			[[Категория:Статьи в работе]]

Daryin: /* Постановка задачи */

2015-06-12T20:59:11Z

Постановка задачи

← Предыдущая версия		Версия от 20:59, 12 июня 2015
Строка 1:		Строка 1:
	== Постановка задачи ==		== Постановка задачи ==

	''Транспортной сетью'' называется ориентированный граф <math>G = (V, E)</math>, каждому ребру <math>e \in E</math> которого приписана ~~положительная~~ пропускная способность <math>c(e)</math>.		''Транспортной сетью'' называется ориентированный граф <math>G = (V, E)</math>, каждому ребру <math>e \in E</math> которого приписана неотрицательная пропускная способность <math>c(e) \ge 0</math>. Будем считать, что вместе с каждым ребром <math>e = (v, w) \in E</math> граф содержит и обратное к нему <math>e^R = (w, v)</math> (при необходимости приписывая ему нулевую пропускную способность).

	Пусть в графе <math>G</math> выделены две вершины: источник <math>s</math> и сток <math>t</math>. Без ограничения общности можно считать, что все остальные вершины лежат на каком-либо пути из <math>s</math> в <math>t</math>. ''Потоком'' называется функция <math>E \to \mathbb{R}</math>, удовлетворяющая следующим требованиям:		Пусть в графе <math>G</math> выделены две вершины: источник <math>s</math> и сток <math>t</math>. Без ограничения общности можно считать, что все остальные вершины лежат на каком-либо пути из <math>s</math> в <math>t</math>. ''Потоком'' называется функция <math>f: E \to \mathbb{R}</math>, удовлетворяющая следующим требованиям:
	* ограничение по пропускной способности: <math>f(e) \le c(e)</math>;		* ограничение по пропускной способности: <math>f(e) \le c(e)</math>;
			* антисимметричность: <math>f(e^R) = -f(e)</math>;
	* закон сохранения потока:		* закон сохранения потока:

Daryin: Описание задачи

2015-06-09T21:47:08Z

Описание задачи

Новая страница

== Постановка задачи ==

''Транспортной сетью'' называется ориентированный граф <math>G = (V, E)</math>, каждому ребру <math>e \in E</math> которого приписана положительная пропускная способность <math>c(e)</math>.

Пусть в графе <math>G</math> выделены две вершины: источник <math>s</math> и сток <math>t</math>. Без ограничения общности можно считать, что все остальные вершины лежат на каком-либо пути из <math>s</math> в <math>t</math>. ''Потоком'' называется функция <math>E \to \mathbb{R}</math>, удовлетворяющая следующим требованиям:
* ограничение по пропускной способности: <math>f(e) \le c(e)</math>;
* закон сохранения потока:

:<math>
\forall v \ne s, t: \quad \sum_{e = (w, v)} f(e) = \sum_{e = (v, w)} f(e).
</math>

''Величиной потока'' называется суммарный поток из источника:

:<math>
\lvert f \rvert = \sum_{e = (s, v)} f(e).
</math>

'''Задача о максимальном потоке в транспортной сети.''' Требуется найти поток максимальной величины:
:<math>\lvert f \rvert \to \max.</math>

== Свойства задачи ==

Суммарный поток из источника равен суммарному потоку в сток:
:<math>
\forall v \ne s, t: \quad \sum_{e = (s, v)} f(e) = \sum_{e = (v, t)} f(e).
</math>
(Для доказательства достаточно просуммировать закон сохранения потока для всех вершин, кроме источника и стока.)

== Варианты задачи ==

В зависимости от ограничений на значения пропускной способности:
* произвольная положительная пропускная способность;
* целая пропускная способность;
* единичная пропускная способность (в этом случае максимальный поток равен [[Связность в графах|рёберной связности]] графа).

== Алгоритмы решения задачи ==

* [[Алгоритм Форда-Фалкерсона]]<ref>Ford, L R, Jr., and D R Fulkerson. “Maximal Flow Through a Network.” Canadian Journal of Mathematics 8 (1956): 399–404. doi:10.4153/CJM-1956-045-5.</ref> и его варианты<ref>Edmonds, Jack, and Richard M Karp. “Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems.” Journal of the ACM 19, no. 2 (April 1972): 248–64. doi:10.1145/321694.321699.</ref><ref>Диниц, Е. А. “Алгоритм решения задачи о максимальном потоке в сети со степенной оценкой.” Доклады АН СССР 194, no. 4 (1970): 754–57.</ref> со сложностью <math>O(n^2m)</math> (для алгоритма Диница). В случае целых пропускных способностей, не превосходящих <math>K</math>, сложность <math>O(Km)</math>.
* [[Алгоритм проталкивания предпотока]]<ref>Goldberg, Andrew V, and Robert Endre Tarjan. “A New Approach to the Maximum-Flow Problem.” Journal of the ACM 35, no. 4 (October 1988): 921–40. doi:10.1145/48014.61051.</ref> со сложностью <math>O(mn \ln n)</math> (при использовании динамических деревьев Тарьяна-Слитора<ref>Sleator, Daniel D, and Robert Endre Tarjan. “A Data Structure for Dynamic Trees,” STOC'81, 114–22, New York, USA: ACM Press, 1981. doi:10.1145/800076.802464.</ref><ref>Sleator, Daniel Dominic, and Robert Endre Tarjan. “Self-Adjusting Binary Search Trees.” Journal of the ACM 32, no. 3 (July 1985): 652–86. doi:10.1145/3828.3835.</ref>).

Обозначения: <math>m</math> – число рёбер, <math>n</math> – число вершин.

== Ссылки ==

<references />