Max-Flow Problems - Revision history

Weihe at 08:58, 31 March 2018

2018-03-31T08:58:19Z

← Older revision		Revision as of 08:58, 31 March 2018
Line 29:		Line 29:
	## First, we construct a new graph <math>G'=(V',A')</math> as follows: We add a super-source <math>s'</math> and a super-target <math>t'</math> to <math>V</math>. Next, for every node <math>v\in V</math>, we add an arc <math>(s',v)</math> and an arc <math>(v,t')</math> to <math>A</math>. Finally we add an arc <math>(t,s)</math> to <math>A</math>, if not in <math>A</math> yet.		## First, we construct a new graph <math>G'=(V',A')</math> as follows: We add a super-source <math>s'</math> and a super-target <math>t'</math> to <math>V</math>. Next, for every node <math>v\in V</math>, we add an arc <math>(s',v)</math> and an arc <math>(v,t')</math> to <math>A</math>. Finally we add an arc <math>(t,s)</math> to <math>A</math>, if not in <math>A</math> yet.
	## For all arcs <math>a\in A</math>, we set <math>\ell'(a):=0</math>. For each node <math>v\in V</math>, we set		## For all arcs <math>a\in A</math>, we set <math>\ell'(a):=0</math>. For each node <math>v\in V</math>, we set
	##:<math>u'(s',v):=\sum_{(w,v)\in A}\ell(w,v)</math> and <math>u'(v,t'):=\sum_{(v,w)\in A} \ell(v,w)</math>.		##:<math>u'(s',v):=\max\{0,\sum_{(w,v)\in A}\ell(w,v)\}</math> and <math>u'(v,t'):=\max\{0,\sum_{(v,w)\in A} \ell(v,w)\}</math>.
	##:For all arcs <math>a\in A</math>, we set <math>u'(a):=u(a)-\ell(a)</math>. Finally, we set <math>u'(t,s):=+\infty</math>.		##:For all arcs <math>a\in A</math>, we set <math>u'(a):=u(a)-\ell(a)</math>. Finally, we set <math>u'(t,s):=+\infty</math>.
	## If all additional arcs <math>(s',\cdot)</math> and <math>(\cdot,t')</math> are [[Basic flow definitions#Flow-augmenting paths and saturated arcs\|saturated]] by some feasible (and obviously maximum) <math>(s',t')</math>-flow <math>f</math>, the values <math>f(a)+\ell(a)</math> on all original arcs of <math>G</math> obviously form a feasible <math>(s,t)</math>-flow in <math>G</math> with respect to <math>\ell</math> and <math>u</math>. On the other hand, if there is a feasible <math>(s,t)</math>-flow <math>f</math> in <math>G</math> with respect to <math>\ell</math> and <math>u</math>, the values <math>f(a)-\ell(a)</math> on all original arcs in <math>G</math> along with saturating flow values on all additional arcs form a feasible (and obviously maximum) <math>(s',t')</math>-flow.		## If all additional arcs <math>(s',\cdot)</math> and <math>(\cdot,t')</math> are [[Basic flow definitions#Flow-augmenting paths and saturated arcs\|saturated]] by some feasible (and obviously maximum) <math>(s',t')</math>-flow <math>f</math>, the values <math>f(a)+\ell(a)</math> on all original arcs of <math>G</math> obviously form a feasible <math>(s,t)</math>-flow in <math>G</math> with respect to <math>\ell</math> and <math>u</math>. On the other hand, if there is a feasible <math>(s,t)</math>-flow <math>f</math> in <math>G</math> with respect to <math>\ell</math> and <math>u</math>, the values <math>f(a)-\ell(a)</math> on all original arcs in <math>G</math> along with saturating flow values on all additional arcs form a feasible (and obviously maximum) <math>(s',t')</math>-flow.

Weihe: /* Generalizations */

2015-11-23T08:48:21Z

Generalizations

← Older revision		Revision as of 08:48, 23 November 2015
Line 32:		Line 32:
	##:For all arcs <math>a\in A</math>, we set <math>u'(a):=u(a)-\ell(a)</math>. Finally, we set <math>u'(t,s):=+\infty</math>.		##:For all arcs <math>a\in A</math>, we set <math>u'(a):=u(a)-\ell(a)</math>. Finally, we set <math>u'(t,s):=+\infty</math>.
	## If all additional arcs <math>(s',\cdot)</math> and <math>(\cdot,t')</math> are [[Basic flow definitions#Flow-augmenting paths and saturated arcs\|saturated]] by some feasible (and obviously maximum) <math>(s',t')</math>-flow <math>f</math>, the values <math>f(a)+\ell(a)</math> on all original arcs of <math>G</math> obviously form a feasible <math>(s,t)</math>-flow in <math>G</math> with respect to <math>\ell</math> and <math>u</math>. On the other hand, if there is a feasible <math>(s,t)</math>-flow <math>f</math> in <math>G</math> with respect to <math>\ell</math> and <math>u</math>, the values <math>f(a)-\ell(a)</math> on all original arcs in <math>G</math> along with saturating flow values on all additional arcs form a feasible (and obviously maximum) <math>(s',t')</math>-flow.		## If all additional arcs <math>(s',\cdot)</math> and <math>(\cdot,t')</math> are [[Basic flow definitions#Flow-augmenting paths and saturated arcs\|saturated]] by some feasible (and obviously maximum) <math>(s',t')</math>-flow <math>f</math>, the values <math>f(a)+\ell(a)</math> on all original arcs of <math>G</math> obviously form a feasible <math>(s,t)</math>-flow in <math>G</math> with respect to <math>\ell</math> and <math>u</math>. On the other hand, if there is a feasible <math>(s,t)</math>-flow <math>f</math> in <math>G</math> with respect to <math>\ell</math> and <math>u</math>, the values <math>f(a)-\ell(a)</math> on all original arcs in <math>G</math> along with saturating flow values on all additional arcs form a feasible (and obviously maximum) <math>(s',t')</math>-flow.
	## Therefore, we may safely terminate the whole procedure if the additional arcs are '''not''' saturated by a maximum <math>(s',t')</math>-flow. Otherwise, we may construct an instance <math>(G'=(V,A'),s,t,u')</math> of the standard version as follows: for each original arc <math>a=(v,w)\in A</math> insert an opposite arc <math>a'=(w,v)</math> and set <math>u'(a):=u(a)-f(a)\geq 0</math> and <math>u'(a'):=f(a)-\ell(a)\geq 0</math>.[[File:Maxflowmultiplesource.png\|350px\|thumb\|right\|Max-Flow Problem with several sources and targets]]		## Therefore, we may safely terminate the whole procedure if the additional arcs are '''not''' saturated by a maximum <math>(s',t')</math>-flow. Otherwise, we may construct an instance <math>(G'=(V,A'),s,t,u')</math> of the standard version as follows: for each original arc <math>a=(v,w)\in A</math> insert an opposite arc <math>a'=(w,v)</math> and set <math>u'(a):=u(a)-f(a)\geq 0</math> and <math>u'(a'):=f(a)-\ell(a)\geq 0</math> (cf. [[Basic flow definitions#Residual network\|residual network]]).[[File:Maxflowmultiplesource.png\|350px\|thumb\|right\|Max-Flow Problem with several sources and targets]]
	# More than one source and more than one target can be reduced to the standard version by adding a super-source node <math>s</math>, a super-target node <math>t</math>, an arc <math>(s,v)</math> with "infinite" capacity for each source <math>v</math>, and an arc <math>(v,t)</math> with "infinite" capacity for each target <math>v</math> (for example, the sum of the upper bounds of all arcs is sufficiently large to serve as "infinity").		# More than one source and more than one target can be reduced to the standard version by adding a super-source node <math>s</math>, a super-target node <math>t</math>, an arc <math>(s,v)</math> with "infinite" capacity for each source <math>v</math>, and an arc <math>(v,t)</math> with "infinite" capacity for each target <math>v</math> (for example, the sum of the upper bounds of all arcs is sufficiently large to serve as "infinity").
	# Usually, the term '''generalized flow''' is reserved for the specific generalization in which for each node <math>v\in V\setminus\{s,t\}</math>, the ratio of the total sum of all incoming flow and the total sum of all outgoing flow is given (in the standard version, this ratio is 1 due to the flow conservation condition).		# Usually, the term '''generalized flow''' is reserved for the specific generalization in which for each node <math>v\in V\setminus\{s,t\}</math>, the ratio of the total sum of all incoming flow and the total sum of all outgoing flow is given (in the standard version, this ratio is 1 due to the flow conservation condition).
	# The max-flow problem asks for an optimal steady-state flow. However, in many applications, a certain amount of flow is to be sent as soon as possible from the source to the target. It is easy to see that, if the amount of flow is sufficiently large, then an optimal solution is constant most of the time, and the maximum steady-state flow is this constant flow.		# The max-flow problem asks for an optimal steady-state flow. However, in many applications, a certain amount of flow is to be sent as soon as possible from the source to the target. It is easy to see that, if the amount of flow is sufficiently large, then an optimal solution is constant most of the time, and the maximum steady-state flow is this constant flow.

Weihe: /* Generalizations */

2015-11-23T08:47:01Z

Generalizations

← Older revision		Revision as of 08:47, 23 November 2015
Line 32:		Line 32:
	##:For all arcs <math>a\in A</math>, we set <math>u'(a):=u(a)-\ell(a)</math>. Finally, we set <math>u'(t,s):=+\infty</math>.		##:For all arcs <math>a\in A</math>, we set <math>u'(a):=u(a)-\ell(a)</math>. Finally, we set <math>u'(t,s):=+\infty</math>.
	## If all additional arcs <math>(s',\cdot)</math> and <math>(\cdot,t')</math> are [[Basic flow definitions#Flow-augmenting paths and saturated arcs\|saturated]] by some feasible (and obviously maximum) <math>(s',t')</math>-flow <math>f</math>, the values <math>f(a)+\ell(a)</math> on all original arcs of <math>G</math> obviously form a feasible <math>(s,t)</math>-flow in <math>G</math> with respect to <math>\ell</math> and <math>u</math>. On the other hand, if there is a feasible <math>(s,t)</math>-flow <math>f</math> in <math>G</math> with respect to <math>\ell</math> and <math>u</math>, the values <math>f(a)-\ell(a)</math> on all original arcs in <math>G</math> along with saturating flow values on all additional arcs form a feasible (and obviously maximum) <math>(s',t')</math>-flow.		## If all additional arcs <math>(s',\cdot)</math> and <math>(\cdot,t')</math> are [[Basic flow definitions#Flow-augmenting paths and saturated arcs\|saturated]] by some feasible (and obviously maximum) <math>(s',t')</math>-flow <math>f</math>, the values <math>f(a)+\ell(a)</math> on all original arcs of <math>G</math> obviously form a feasible <math>(s,t)</math>-flow in <math>G</math> with respect to <math>\ell</math> and <math>u</math>. On the other hand, if there is a feasible <math>(s,t)</math>-flow <math>f</math> in <math>G</math> with respect to <math>\ell</math> and <math>u</math>, the values <math>f(a)-\ell(a)</math> on all original arcs in <math>G</math> along with saturating flow values on all additional arcs form a feasible (and obviously maximum) <math>(s',t')</math>-flow.
	## Therefore, we may safely terminate the whole procedure if the additional arcs are '''not''' saturated by a maximum <math>(s',t')</math>-flow. Otherwise, we may construct an instance <math>(G'=(V,A'),s,t,u')</math> of the standard version as follows: for each original ~~arc <math>a\in A</math>, for each~~ arc <math>a=(v,w)\in A</math> insert an opposite arc <math>a'=(w,v)</math> and set <math>u'(a):=u(a)-f(a)\geq 0</math> and <math>u'(a'):=f(a)-\ell(a)\geq 0</math>.[[File:Maxflowmultiplesource.png\|350px\|thumb\|right\|Max-Flow Problem with several sources and targets]]		## Therefore, we may safely terminate the whole procedure if the additional arcs are '''not''' saturated by a maximum <math>(s',t')</math>-flow. Otherwise, we may construct an instance <math>(G'=(V,A'),s,t,u')</math> of the standard version as follows: for each original arc <math>a=(v,w)\in A</math> insert an opposite arc <math>a'=(w,v)</math> and set <math>u'(a):=u(a)-f(a)\geq 0</math> and <math>u'(a'):=f(a)-\ell(a)\geq 0</math>.[[File:Maxflowmultiplesource.png\|350px\|thumb\|right\|Max-Flow Problem with several sources and targets]]
	# More than one source and more than one target can be reduced to the standard version by adding a super-source node <math>s</math>, a super-target node <math>t</math>, an arc <math>(s,v)</math> with "infinite" capacity for each source <math>v</math>, and an arc <math>(v,t)</math> with "infinite" capacity for each target <math>v</math> (for example, the sum of the upper bounds of all arcs is sufficiently large to serve as "infinity").		# More than one source and more than one target can be reduced to the standard version by adding a super-source node <math>s</math>, a super-target node <math>t</math>, an arc <math>(s,v)</math> with "infinite" capacity for each source <math>v</math>, and an arc <math>(v,t)</math> with "infinite" capacity for each target <math>v</math> (for example, the sum of the upper bounds of all arcs is sufficiently large to serve as "infinity").
	# Usually, the term '''generalized flow''' is reserved for the specific generalization in which for each node <math>v\in V\setminus\{s,t\}</math>, the ratio of the total sum of all incoming flow and the total sum of all outgoing flow is given (in the standard version, this ratio is 1 due to the flow conservation condition).		# Usually, the term '''generalized flow''' is reserved for the specific generalization in which for each node <math>v\in V\setminus\{s,t\}</math>, the ratio of the total sum of all incoming flow and the total sum of all outgoing flow is given (in the standard version, this ratio is 1 due to the flow conservation condition).
	# The max-flow problem asks for an optimal steady-state flow. However, in many applications, a certain amount of flow is to be sent as soon as possible from the source to the target. It is easy to see that, if the amount of flow is sufficiently large, then an optimal solution is constant most of the time, and the maximum steady-state flow is this constant flow.		# The max-flow problem asks for an optimal steady-state flow. However, in many applications, a certain amount of flow is to be sent as soon as possible from the source to the target. It is easy to see that, if the amount of flow is sufficiently large, then an optimal solution is constant most of the time, and the maximum steady-state flow is this constant flow.

Weihe: /* Generalizations */

2015-11-23T08:45:55Z

Generalizations

← Older revision		Revision as of 08:45, 23 November 2015
Line 32:		Line 32:
	##:For all arcs <math>a\in A</math>, we set <math>u'(a):=u(a)-\ell(a)</math>. Finally, we set <math>u'(t,s):=+\infty</math>.		##:For all arcs <math>a\in A</math>, we set <math>u'(a):=u(a)-\ell(a)</math>. Finally, we set <math>u'(t,s):=+\infty</math>.
	## If all additional arcs <math>(s',\cdot)</math> and <math>(\cdot,t')</math> are [[Basic flow definitions#Flow-augmenting paths and saturated arcs\|saturated]] by some feasible (and obviously maximum) <math>(s',t')</math>-flow <math>f</math>, the values <math>f(a)+\ell(a)</math> on all original arcs of <math>G</math> obviously form a feasible <math>(s,t)</math>-flow in <math>G</math> with respect to <math>\ell</math> and <math>u</math>. On the other hand, if there is a feasible <math>(s,t)</math>-flow <math>f</math> in <math>G</math> with respect to <math>\ell</math> and <math>u</math>, the values <math>f(a)-\ell(a)</math> on all original arcs in <math>G</math> along with saturating flow values on all additional arcs form a feasible (and obviously maximum) <math>(s',t')</math>-flow.		## If all additional arcs <math>(s',\cdot)</math> and <math>(\cdot,t')</math> are [[Basic flow definitions#Flow-augmenting paths and saturated arcs\|saturated]] by some feasible (and obviously maximum) <math>(s',t')</math>-flow <math>f</math>, the values <math>f(a)+\ell(a)</math> on all original arcs of <math>G</math> obviously form a feasible <math>(s,t)</math>-flow in <math>G</math> with respect to <math>\ell</math> and <math>u</math>. On the other hand, if there is a feasible <math>(s,t)</math>-flow <math>f</math> in <math>G</math> with respect to <math>\ell</math> and <math>u</math>, the values <math>f(a)-\ell(a)</math> on all original arcs in <math>G</math> along with saturating flow values on all additional arcs form a feasible (and obviously maximum) <math>(s',t')</math>-flow.
	## Therefore, we may safely terminate the whole procedure if the additional arcs are '''not''' saturated by a maximum <math>(s',t')</math>-flow. Otherwise, we may ~~use the values~~ <math>f(a)~~+\ell(a~~)</math> in <math>G</math> as an ~~initial feasible~~ <math>(s,t)</math>~~-flow for the computation of a maximum~~ <math>(~~s,t~~)</math>~~-flow in~~ <math>G</math>.[[File:Maxflowmultiplesource.png\|350px\|thumb\|right\|Max-Flow Problem with several sources and targets]]		## Therefore, we may safely terminate the whole procedure if the additional arcs are '''not''' saturated by a maximum <math>(s',t')</math>-flow. Otherwise, we may construct an instance <math>(G'=(V,A'),s,t,u')</math> of the standard version as follows: for each original arc <math>a\in A</math>, for each arc <math>a=(v,w)\in A</math> insert an opposite arc <math>a'=(w,v)</math> and set <math>u'(a):=u(a)-f(a)\geq 0</math> and <math>u'(a'):=f(a)-\ell(a)\geq 0</math>.[[File:Maxflowmultiplesource.png\|350px\|thumb\|right\|Max-Flow Problem with several sources and targets]]
	# More than one source and more than one target can be reduced to the standard version by adding a super-source node <math>s</math>, a super-target node <math>t</math>, an arc <math>(s,v)</math> with "infinite" capacity for each source <math>v</math>, and an arc <math>(v,t)</math> with "infinite" capacity for each target <math>v</math> (for example, the sum of the upper bounds of all arcs is sufficiently large to serve as "infinity").		# More than one source and more than one target can be reduced to the standard version by adding a super-source node <math>s</math>, a super-target node <math>t</math>, an arc <math>(s,v)</math> with "infinite" capacity for each source <math>v</math>, and an arc <math>(v,t)</math> with "infinite" capacity for each target <math>v</math> (for example, the sum of the upper bounds of all arcs is sufficiently large to serve as "infinity").
	# Usually, the term '''generalized flow''' is reserved for the specific generalization in which for each node <math>v\in V\setminus\{s,t\}</math>, the ratio of the total sum of all incoming flow and the total sum of all outgoing flow is given (in the standard version, this ratio is 1 due to the flow conservation condition).		# Usually, the term '''generalized flow''' is reserved for the specific generalization in which for each node <math>v\in V\setminus\{s,t\}</math>, the ratio of the total sum of all incoming flow and the total sum of all outgoing flow is given (in the standard version, this ratio is 1 due to the flow conservation condition).
	# The max-flow problem asks for an optimal steady-state flow. However, in many applications, a certain amount of flow is to be sent as soon as possible from the source to the target. It is easy to see that, if the amount of flow is sufficiently large, then an optimal solution is constant most of the time, and the maximum steady-state flow is this constant flow.		# The max-flow problem asks for an optimal steady-state flow. However, in many applications, a certain amount of flow is to be sent as soon as possible from the source to the target. It is easy to see that, if the amount of flow is sufficiently large, then an optimal solution is constant most of the time, and the maximum steady-state flow is this constant flow.

Weihe: /* Generalizations */

2015-11-23T08:38:11Z

Generalizations

← Older revision		Revision as of 08:38, 23 November 2015
Line 32:		Line 32:
	##:For all arcs <math>a\in A</math>, we set <math>u'(a):=u(a)-\ell(a)</math>. Finally, we set <math>u'(t,s):=+\infty</math>.		##:For all arcs <math>a\in A</math>, we set <math>u'(a):=u(a)-\ell(a)</math>. Finally, we set <math>u'(t,s):=+\infty</math>.
	## If all additional arcs <math>(s',\cdot)</math> and <math>(\cdot,t')</math> are [[Basic flow definitions#Flow-augmenting paths and saturated arcs\|saturated]] by some feasible (and obviously maximum) <math>(s',t')</math>-flow <math>f</math>, the values <math>f(a)+\ell(a)</math> on all original arcs of <math>G</math> obviously form a feasible <math>(s,t)</math>-flow in <math>G</math> with respect to <math>\ell</math> and <math>u</math>. On the other hand, if there is a feasible <math>(s,t)</math>-flow <math>f</math> in <math>G</math> with respect to <math>\ell</math> and <math>u</math>, the values <math>f(a)-\ell(a)</math> on all original arcs in <math>G</math> along with saturating flow values on all additional arcs form a feasible (and obviously maximum) <math>(s',t')</math>-flow.		## If all additional arcs <math>(s',\cdot)</math> and <math>(\cdot,t')</math> are [[Basic flow definitions#Flow-augmenting paths and saturated arcs\|saturated]] by some feasible (and obviously maximum) <math>(s',t')</math>-flow <math>f</math>, the values <math>f(a)+\ell(a)</math> on all original arcs of <math>G</math> obviously form a feasible <math>(s,t)</math>-flow in <math>G</math> with respect to <math>\ell</math> and <math>u</math>. On the other hand, if there is a feasible <math>(s,t)</math>-flow <math>f</math> in <math>G</math> with respect to <math>\ell</math> and <math>u</math>, the values <math>f(a)-\ell(a)</math> on all original arcs in <math>G</math> along with saturating flow values on all additional arcs form a feasible (and obviously maximum) <math>(s',t')</math>-flow.
	## Therefore, we may safely terminate the whole procedure if the additional arcs are '''not''' saturated by a maximum <math>(s',t')</math>-flow. Otherwise, we may use the values <math>f(a)+\ell(a)</math> in <math>G</math> as an initial flow for the computation of a maximum <math>(s,t)</math>-flow in <math>G</math>.[[File:Maxflowmultiplesource.png\|350px\|thumb\|right\|Max-Flow Problem with several sources and targets]]		## Therefore, we may safely terminate the whole procedure if the additional arcs are '''not''' saturated by a maximum <math>(s',t')</math>-flow. Otherwise, we may use the values <math>f(a)+\ell(a)</math> in <math>G</math> as an initial feasible <math>(s,t)</math>-flow for the computation of a maximum <math>(s,t)</math>-flow in <math>G</math>.[[File:Maxflowmultiplesource.png\|350px\|thumb\|right\|Max-Flow Problem with several sources and targets]]
	# More than one source and more than one target can be reduced to the standard version by adding a super-source node <math>s</math>, a super-target node <math>t</math>, an arc <math>(s,v)</math> with "infinite" capacity for each source <math>v</math>, and an arc <math>(v,t)</math> with "infinite" capacity for each target <math>v</math> (for example, the sum of the upper bounds of all arcs is sufficiently large to serve as "infinity").		# More than one source and more than one target can be reduced to the standard version by adding a super-source node <math>s</math>, a super-target node <math>t</math>, an arc <math>(s,v)</math> with "infinite" capacity for each source <math>v</math>, and an arc <math>(v,t)</math> with "infinite" capacity for each target <math>v</math> (for example, the sum of the upper bounds of all arcs is sufficiently large to serve as "infinity").
	# Usually, the term '''generalized flow''' is reserved for the specific generalization in which for each node <math>v\in V\setminus\{s,t\}</math>, the ratio of the total sum of all incoming flow and the total sum of all outgoing flow is given (in the standard version, this ratio is 1 due to the flow conservation condition).		# Usually, the term '''generalized flow''' is reserved for the specific generalization in which for each node <math>v\in V\setminus\{s,t\}</math>, the ratio of the total sum of all incoming flow and the total sum of all outgoing flow is given (in the standard version, this ratio is 1 due to the flow conservation condition).
	# The max-flow problem asks for an optimal steady-state flow. However, in many applications, a certain amount of flow is to be sent as soon as possible from the source to the target. It is easy to see that, if the amount of flow is sufficiently large, then an optimal solution is constant most of the time, and the maximum steady-state flow is this constant flow.		# The max-flow problem asks for an optimal steady-state flow. However, in many applications, a certain amount of flow is to be sent as soon as possible from the source to the target. It is easy to see that, if the amount of flow is sufficiently large, then an optimal solution is constant most of the time, and the maximum steady-state flow is this constant flow.

Weihe: /* Generalizations */

2015-11-23T08:37:38Z

Generalizations

← Older revision		Revision as of 08:37, 23 November 2015
Line 31:		Line 31:
	##:<math>u'(s',v):=\sum_{(w,v)\in A}\ell(w,v)</math> and <math>u'(v,t'):=\sum_{(v,w)\in A} \ell(v,w)</math>.		##:<math>u'(s',v):=\sum_{(w,v)\in A}\ell(w,v)</math> and <math>u'(v,t'):=\sum_{(v,w)\in A} \ell(v,w)</math>.
	##:For all arcs <math>a\in A</math>, we set <math>u'(a):=u(a)-\ell(a)</math>. Finally, we set <math>u'(t,s):=+\infty</math>.		##:For all arcs <math>a\in A</math>, we set <math>u'(a):=u(a)-\ell(a)</math>. Finally, we set <math>u'(t,s):=+\infty</math>.
	## If all additional arcs <math>(s',\cdot)</math> and <math>(\cdot,t')</math> are [[Basic flow definitions#Flow-augmenting paths and saturated arcs\|saturated]] by some feasible (and obviously maximum) <math>(s',t')</math>-flow <math>f</math>, the values <math>f(a)+\ell(a)</math> on all original arcs of <math>G</math> obviously form a feasible <math>(s,t)</math>-flow in <math>G</math> with respect to <math>\ell</math> and <math>u</math>. On the other hand, if there is a feasible <math>(s,t)</math>-flow <math>f</math> in <math>G</math> with respect to <math>\ell</math> and <math>u</math>, the values <math>f(a)-\ell(a)</math> on all original arcs in <math>G</math> along with saturating flow values on all additional arcs form a feasible (and obviously maximum) <math>(s',t')</math>-flow. Therefore, we may safely terminate the whole procedure if the additional arcs are '''not''' saturated by a maximum <math>(s',t')</math>-flow.		## If all additional arcs <math>(s',\cdot)</math> and <math>(\cdot,t')</math> are [[Basic flow definitions#Flow-augmenting paths and saturated arcs\|saturated]] by some feasible (and obviously maximum) <math>(s',t')</math>-flow <math>f</math>, the values <math>f(a)+\ell(a)</math> on all original arcs of <math>G</math> obviously form a feasible <math>(s,t)</math>-flow in <math>G</math> with respect to <math>\ell</math> and <math>u</math>. On the other hand, if there is a feasible <math>(s,t)</math>-flow <math>f</math> in <math>G</math> with respect to <math>\ell</math> and <math>u</math>, the values <math>f(a)-\ell(a)</math> on all original arcs in <math>G</math> along with saturating flow values on all additional arcs form a feasible (and obviously maximum) <math>(s',t')</math>-flow.
	## Otherwise, we may use the values <math>f(a)+\ell(a)</math> in <math>G</math> as an initial flow for the computation of a maximum <math>(s,t)</math>-flow in <math>G</math>.[[File:Maxflowmultiplesource.png\|350px\|thumb\|right\|Max-Flow Problem with several sources and targets]]		## Therefore, we may safely terminate the whole procedure if the additional arcs are '''not''' saturated by a maximum <math>(s',t')</math>-flow. Otherwise, we may use the values <math>f(a)+\ell(a)</math> in <math>G</math> as an initial flow for the computation of a maximum <math>(s,t)</math>-flow in <math>G</math>.[[File:Maxflowmultiplesource.png\|350px\|thumb\|right\|Max-Flow Problem with several sources and targets]]
	# More than one source and more than one target can be reduced to the standard version by adding a super-source node <math>s</math>, a super-target node <math>t</math>, an arc <math>(s,v)</math> with "infinite" capacity for each source <math>v</math>, and an arc <math>(v,t)</math> with "infinite" capacity for each target <math>v</math> (for example, the sum of the upper bounds of all arcs is sufficiently large to serve as "infinity").		# More than one source and more than one target can be reduced to the standard version by adding a super-source node <math>s</math>, a super-target node <math>t</math>, an arc <math>(s,v)</math> with "infinite" capacity for each source <math>v</math>, and an arc <math>(v,t)</math> with "infinite" capacity for each target <math>v</math> (for example, the sum of the upper bounds of all arcs is sufficiently large to serve as "infinity").
	# Usually, the term '''generalized flow''' is reserved for the specific generalization in which for each node <math>v\in V\setminus\{s,t\}</math>, the ratio of the total sum of all incoming flow and the total sum of all outgoing flow is given (in the standard version, this ratio is 1 due to the flow conservation condition).		# Usually, the term '''generalized flow''' is reserved for the specific generalization in which for each node <math>v\in V\setminus\{s,t\}</math>, the ratio of the total sum of all incoming flow and the total sum of all outgoing flow is given (in the standard version, this ratio is 1 due to the flow conservation condition).
	# The max-flow problem asks for an optimal steady-state flow. However, in many applications, a certain amount of flow is to be sent as soon as possible from the source to the target. It is easy to see that, if the amount of flow is sufficiently large, then an optimal solution is constant most of the time, and the maximum steady-state flow is this constant flow.		# The max-flow problem asks for an optimal steady-state flow. However, in many applications, a certain amount of flow is to be sent as soon as possible from the source to the target. It is easy to see that, if the amount of flow is sufficiently large, then an optimal solution is constant most of the time, and the maximum steady-state flow is this constant flow.

Weihe: /* Generalizations */

2015-11-23T08:36:32Z

Generalizations

← Older revision		Revision as of 08:36, 23 November 2015
Line 31:		Line 31:
	##:<math>u'(s',v):=\sum_{(w,v)\in A}\ell(w,v)</math> and <math>u'(v,t'):=\sum_{(v,w)\in A} \ell(v,w)</math>.		##:<math>u'(s',v):=\sum_{(w,v)\in A}\ell(w,v)</math> and <math>u'(v,t'):=\sum_{(v,w)\in A} \ell(v,w)</math>.
	##:For all arcs <math>a\in A</math>, we set <math>u'(a):=u(a)-\ell(a)</math>. Finally, we set <math>u'(t,s):=+\infty</math>.		##:For all arcs <math>a\in A</math>, we set <math>u'(a):=u(a)-\ell(a)</math>. Finally, we set <math>u'(t,s):=+\infty</math>.
	## If all additional arcs <math>(s',\cdot)</math> and <math>(\cdot,t')</math> are [[Basic flow definitions\|saturated]] by some feasible (and obviously maximum) <math>(s',t')</math>-flow <math>f</math>, the values <math>f(a)+\ell(a)</math> on all original arcs of <math>G</math> obviously form a feasible <math>(s,t)</math>-flow in <math>G</math> with respect to <math>\ell</math> and <math>u</math>. On the other hand, if there is a feasible <math>(s,t)</math>-flow <math>f</math> in <math>G</math> with respect to <math>\ell</math> and <math>u</math>, the values <math>f(a)-\ell(a)</math> on all original arcs in <math>G</math> along with saturating flow values on all additional arcs form a feasible (and obviously maximum) <math>(s',t')</math>-flow. Therefore, we may safely terminate the whole procedure if the additional arcs are '''not''' saturated by a maximum <math>(s',t')</math>-flow.		## If all additional arcs <math>(s',\cdot)</math> and <math>(\cdot,t')</math> are [[Basic flow definitions#Flow-augmenting paths and saturated arcs\|saturated]] by some feasible (and obviously maximum) <math>(s',t')</math>-flow <math>f</math>, the values <math>f(a)+\ell(a)</math> on all original arcs of <math>G</math> obviously form a feasible <math>(s,t)</math>-flow in <math>G</math> with respect to <math>\ell</math> and <math>u</math>. On the other hand, if there is a feasible <math>(s,t)</math>-flow <math>f</math> in <math>G</math> with respect to <math>\ell</math> and <math>u</math>, the values <math>f(a)-\ell(a)</math> on all original arcs in <math>G</math> along with saturating flow values on all additional arcs form a feasible (and obviously maximum) <math>(s',t')</math>-flow. Therefore, we may safely terminate the whole procedure if the additional arcs are '''not''' saturated by a maximum <math>(s',t')</math>-flow.
	## Otherwise, we may use the values <math>f(a)+\ell(a)</math> in <math>G</math> as an initial flow for the computation of a maximum <math>(s,t)</math>-flow in <math>G</math>.[[File:Maxflowmultiplesource.png\|350px\|thumb\|right\|Max-Flow Problem with several sources and targets]]		## Otherwise, we may use the values <math>f(a)+\ell(a)</math> in <math>G</math> as an initial flow for the computation of a maximum <math>(s,t)</math>-flow in <math>G</math>.[[File:Maxflowmultiplesource.png\|350px\|thumb\|right\|Max-Flow Problem with several sources and targets]]
	# More than one source and more than one target can be reduced to the standard version by adding a super-source node <math>s</math>, a super-target node <math>t</math>, an arc <math>(s,v)</math> with "infinite" capacity for each source <math>v</math>, and an arc <math>(v,t)</math> with "infinite" capacity for each target <math>v</math> (for example, the sum of the upper bounds of all arcs is sufficiently large to serve as "infinity").		# More than one source and more than one target can be reduced to the standard version by adding a super-source node <math>s</math>, a super-target node <math>t</math>, an arc <math>(s,v)</math> with "infinite" capacity for each source <math>v</math>, and an arc <math>(v,t)</math> with "infinite" capacity for each target <math>v</math> (for example, the sum of the upper bounds of all arcs is sufficiently large to serve as "infinity").
	# Usually, the term '''generalized flow''' is reserved for the specific generalization in which for each node <math>v\in V\setminus\{s,t\}</math>, the ratio of the total sum of all incoming flow and the total sum of all outgoing flow is given (in the standard version, this ratio is 1 due to the flow conservation condition).		# Usually, the term '''generalized flow''' is reserved for the specific generalization in which for each node <math>v\in V\setminus\{s,t\}</math>, the ratio of the total sum of all incoming flow and the total sum of all outgoing flow is given (in the standard version, this ratio is 1 due to the flow conservation condition).
	# The max-flow problem asks for an optimal steady-state flow. However, in many applications, a certain amount of flow is to be sent as soon as possible from the source to the target. It is easy to see that, if the amount of flow is sufficiently large, then an optimal solution is constant most of the time, and the maximum steady-state flow is this constant flow.		# The max-flow problem asks for an optimal steady-state flow. However, in many applications, a certain amount of flow is to be sent as soon as possible from the source to the target. It is easy to see that, if the amount of flow is sufficiently large, then an optimal solution is constant most of the time, and the maximum steady-state flow is this constant flow.

Weihe: /* Generalizations */

2015-11-23T08:34:31Z

Generalizations

← Older revision		Revision as of 08:34, 23 November 2015
Line 32:		Line 32:
	##:For all arcs <math>a\in A</math>, we set <math>u'(a):=u(a)-\ell(a)</math>. Finally, we set <math>u'(t,s):=+\infty</math>.		##:For all arcs <math>a\in A</math>, we set <math>u'(a):=u(a)-\ell(a)</math>. Finally, we set <math>u'(t,s):=+\infty</math>.
	## If all additional arcs <math>(s',\cdot)</math> and <math>(\cdot,t')</math> are [[Basic flow definitions\|saturated]] by some feasible (and obviously maximum) <math>(s',t')</math>-flow <math>f</math>, the values <math>f(a)+\ell(a)</math> on all original arcs of <math>G</math> obviously form a feasible <math>(s,t)</math>-flow in <math>G</math> with respect to <math>\ell</math> and <math>u</math>. On the other hand, if there is a feasible <math>(s,t)</math>-flow <math>f</math> in <math>G</math> with respect to <math>\ell</math> and <math>u</math>, the values <math>f(a)-\ell(a)</math> on all original arcs in <math>G</math> along with saturating flow values on all additional arcs form a feasible (and obviously maximum) <math>(s',t')</math>-flow. Therefore, we may safely terminate the whole procedure if the additional arcs are '''not''' saturated by a maximum <math>(s',t')</math>-flow.		## If all additional arcs <math>(s',\cdot)</math> and <math>(\cdot,t')</math> are [[Basic flow definitions\|saturated]] by some feasible (and obviously maximum) <math>(s',t')</math>-flow <math>f</math>, the values <math>f(a)+\ell(a)</math> on all original arcs of <math>G</math> obviously form a feasible <math>(s,t)</math>-flow in <math>G</math> with respect to <math>\ell</math> and <math>u</math>. On the other hand, if there is a feasible <math>(s,t)</math>-flow <math>f</math> in <math>G</math> with respect to <math>\ell</math> and <math>u</math>, the values <math>f(a)-\ell(a)</math> on all original arcs in <math>G</math> along with saturating flow values on all additional arcs form a feasible (and obviously maximum) <math>(s',t')</math>-flow. Therefore, we may safely terminate the whole procedure if the additional arcs are '''not''' saturated by a maximum <math>(s',t')</math>-flow.
	## Otherwise, we may use the values <math>f(a)+\ell</math> in <math>G</math> as an initial flow for the computation of a maximum <math>(s,t)</math>-flow in <math>G</math>.[[File:Maxflowmultiplesource.png\|350px\|thumb\|right\|Max-Flow Problem with several sources and targets]]		## Otherwise, we may use the values <math>f(a)+\ell(a)</math> in <math>G</math> as an initial flow for the computation of a maximum <math>(s,t)</math>-flow in <math>G</math>.[[File:Maxflowmultiplesource.png\|350px\|thumb\|right\|Max-Flow Problem with several sources and targets]]
	# More than one source and more than one target can be reduced to the standard version by adding a super-source node <math>s</math>, a super-target node <math>t</math>, an arc <math>(s,v)</math> with "infinite" capacity for each source <math>v</math>, and an arc <math>(v,t)</math> with "infinite" capacity for each target <math>v</math> (for example, the sum of the upper bounds of all arcs is sufficiently large to serve as "infinity").		# More than one source and more than one target can be reduced to the standard version by adding a super-source node <math>s</math>, a super-target node <math>t</math>, an arc <math>(s,v)</math> with "infinite" capacity for each source <math>v</math>, and an arc <math>(v,t)</math> with "infinite" capacity for each target <math>v</math> (for example, the sum of the upper bounds of all arcs is sufficiently large to serve as "infinity").
	# Usually, the term '''generalized flow''' is reserved for the specific generalization in which for each node <math>v\in V\setminus\{s,t\}</math>, the ratio of the total sum of all incoming flow and the total sum of all outgoing flow is given (in the standard version, this ratio is 1 due to the flow conservation condition).		# Usually, the term '''generalized flow''' is reserved for the specific generalization in which for each node <math>v\in V\setminus\{s,t\}</math>, the ratio of the total sum of all incoming flow and the total sum of all outgoing flow is given (in the standard version, this ratio is 1 due to the flow conservation condition).
	# The max-flow problem asks for an optimal steady-state flow. However, in many applications, a certain amount of flow is to be sent as soon as possible from the source to the target. It is easy to see that, if the amount of flow is sufficiently large, then an optimal solution is constant most of the time, and the maximum steady-state flow is this constant flow.		# The max-flow problem asks for an optimal steady-state flow. However, in many applications, a certain amount of flow is to be sent as soon as possible from the source to the target. It is easy to see that, if the amount of flow is sufficiently large, then an optimal solution is constant most of the time, and the maximum steady-state flow is this constant flow.

Weihe: /* Generalizations */

2015-11-23T08:34:18Z

Generalizations

← Older revision		Revision as of 08:34, 23 November 2015
Line 32:		Line 32:
	##:For all arcs <math>a\in A</math>, we set <math>u'(a):=u(a)-\ell(a)</math>. Finally, we set <math>u'(t,s):=+\infty</math>.		##:For all arcs <math>a\in A</math>, we set <math>u'(a):=u(a)-\ell(a)</math>. Finally, we set <math>u'(t,s):=+\infty</math>.
	## If all additional arcs <math>(s',\cdot)</math> and <math>(\cdot,t')</math> are [[Basic flow definitions\|saturated]] by some feasible (and obviously maximum) <math>(s',t')</math>-flow <math>f</math>, the values <math>f(a)+\ell(a)</math> on all original arcs of <math>G</math> obviously form a feasible <math>(s,t)</math>-flow in <math>G</math> with respect to <math>\ell</math> and <math>u</math>. On the other hand, if there is a feasible <math>(s,t)</math>-flow <math>f</math> in <math>G</math> with respect to <math>\ell</math> and <math>u</math>, the values <math>f(a)-\ell(a)</math> on all original arcs in <math>G</math> along with saturating flow values on all additional arcs form a feasible (and obviously maximum) <math>(s',t')</math>-flow. Therefore, we may safely terminate the whole procedure if the additional arcs are '''not''' saturated by a maximum <math>(s',t')</math>-flow.		## If all additional arcs <math>(s',\cdot)</math> and <math>(\cdot,t')</math> are [[Basic flow definitions\|saturated]] by some feasible (and obviously maximum) <math>(s',t')</math>-flow <math>f</math>, the values <math>f(a)+\ell(a)</math> on all original arcs of <math>G</math> obviously form a feasible <math>(s,t)</math>-flow in <math>G</math> with respect to <math>\ell</math> and <math>u</math>. On the other hand, if there is a feasible <math>(s,t)</math>-flow <math>f</math> in <math>G</math> with respect to <math>\ell</math> and <math>u</math>, the values <math>f(a)-\ell(a)</math> on all original arcs in <math>G</math> along with saturating flow values on all additional arcs form a feasible (and obviously maximum) <math>(s',t')</math>-flow. Therefore, we may safely terminate the whole procedure if the additional arcs are '''not''' saturated by a maximum <math>(s',t')</math>-flow.
	## ~~More specifically~~, ~~for~~ <math>(~~v,w~~)\in A</math>~~, we set~~ <math>f(v,~~w):=f'(v,w)+\ell(v,w~~)</math>.[[File:Maxflowmultiplesource.png\|350px\|thumb\|right\|Max-Flow Problem with several sources and targets]]		## Otherwise, we may use the values <math>f(a)+\ell</math> in <math>G</math> as an initial flow for the computation of a maximum <math>(s,t)</math>-flow in <math>G</math>.[[File:Maxflowmultiplesource.png\|350px\|thumb\|right\|Max-Flow Problem with several sources and targets]]
	# More than one source and more than one target can be reduced to the standard version by adding a super-source node <math>s</math>, a super-target node <math>t</math>, an arc <math>(s,v)</math> with "infinite" capacity for each source <math>v</math>, and an arc <math>(v,t)</math> with "infinite" capacity for each target <math>v</math> (for example, the sum of the upper bounds of all arcs is sufficiently large to serve as "infinity").		# More than one source and more than one target can be reduced to the standard version by adding a super-source node <math>s</math>, a super-target node <math>t</math>, an arc <math>(s,v)</math> with "infinite" capacity for each source <math>v</math>, and an arc <math>(v,t)</math> with "infinite" capacity for each target <math>v</math> (for example, the sum of the upper bounds of all arcs is sufficiently large to serve as "infinity").
	# Usually, the term '''generalized flow''' is reserved for the specific generalization in which for each node <math>v\in V\setminus\{s,t\}</math>, the ratio of the total sum of all incoming flow and the total sum of all outgoing flow is given (in the standard version, this ratio is 1 due to the flow conservation condition).		# Usually, the term '''generalized flow''' is reserved for the specific generalization in which for each node <math>v\in V\setminus\{s,t\}</math>, the ratio of the total sum of all incoming flow and the total sum of all outgoing flow is given (in the standard version, this ratio is 1 due to the flow conservation condition).
	# The max-flow problem asks for an optimal steady-state flow. However, in many applications, a certain amount of flow is to be sent as soon as possible from the source to the target. It is easy to see that, if the amount of flow is sufficiently large, then an optimal solution is constant most of the time, and the maximum steady-state flow is this constant flow.		# The max-flow problem asks for an optimal steady-state flow. However, in many applications, a certain amount of flow is to be sent as soon as possible from the source to the target. It is easy to see that, if the amount of flow is sufficiently large, then an optimal solution is constant most of the time, and the maximum steady-state flow is this constant flow.

Weihe: /* Generalizations */

2015-11-23T08:30:47Z

Generalizations

← Older revision		Revision as of 08:30, 23 November 2015
Line 31:		Line 31:
	##:<math>u'(s',v):=\sum_{(w,v)\in A}\ell(w,v)</math> and <math>u'(v,t'):=\sum_{(v,w)\in A} \ell(v,w)</math>.		##:<math>u'(s',v):=\sum_{(w,v)\in A}\ell(w,v)</math> and <math>u'(v,t'):=\sum_{(v,w)\in A} \ell(v,w)</math>.
	##:For all arcs <math>a\in A</math>, we set <math>u'(a):=u(a)-\ell(a)</math>. Finally, we set <math>u'(t,s):=+\infty</math>.		##:For all arcs <math>a\in A</math>, we set <math>u'(a):=u(a)-\ell(a)</math>. Finally, we set <math>u'(t,s):=+\infty</math>.
	## If all additional arcs <math>(s',\cdot)</math> and <math>(\cdot,t')</math> are [[Basic flow definitions\|saturated]] by some feasible (and obviously maximum) <math>(s',t')</math>-flow <math>f</math>, the values <math>f(a)+\ell(a)</math> on all original arcs of <math>G</math> obviously form a feasible <math>(s,t)</math>-flow in <math>G</math> with respect to <math>\ell</math> and <math>u</math>. On the other hand, if there is a feasible <math>(s,t)</math>-flow in <math>G</math> with respect to <math>\ell</math> and <math>u</math>, saturating all additional arcs ~~forms~~ a feasible (and obviously maximum) <math>(s',t')</math>-flow. Therefore, we may safely terminate the whole procedure if the additional arcs are '''not'''saturated.		## If all additional arcs <math>(s',\cdot)</math> and <math>(\cdot,t')</math> are [[Basic flow definitions\|saturated]] by some feasible (and obviously maximum) <math>(s',t')</math>-flow <math>f</math>, the values <math>f(a)+\ell(a)</math> on all original arcs of <math>G</math> obviously form a feasible <math>(s,t)</math>-flow in <math>G</math> with respect to <math>\ell</math> and <math>u</math>. On the other hand, if there is a feasible <math>(s,t)</math>-flow <math>f</math> in <math>G</math> with respect to <math>\ell</math> and <math>u</math>, the values <math>f(a)-\ell(a)</math> on all original arcs in <math>G</math> along with saturating flow values on all additional arcs form a feasible (and obviously maximum) <math>(s',t')</math>-flow. Therefore, we may safely terminate the whole procedure if the additional arcs are '''not''' saturated by a maximum <math>(s',t')</math>-flow.
	## More specifically, for <math>(v,w)\in A</math>, we set <math>f(v,w):=f'(v,w)+\ell(v,w)</math>.[[File:Maxflowmultiplesource.png\|350px\|thumb\|right\|Max-Flow Problem with several sources and targets]]		## More specifically, for <math>(v,w)\in A</math>, we set <math>f(v,w):=f'(v,w)+\ell(v,w)</math>.[[File:Maxflowmultiplesource.png\|350px\|thumb\|right\|Max-Flow Problem with several sources and targets]]
	# More than one source and more than one target can be reduced to the standard version by adding a super-source node <math>s</math>, a super-target node <math>t</math>, an arc <math>(s,v)</math> with "infinite" capacity for each source <math>v</math>, and an arc <math>(v,t)</math> with "infinite" capacity for each target <math>v</math> (for example, the sum of the upper bounds of all arcs is sufficiently large to serve as "infinity").		# More than one source and more than one target can be reduced to the standard version by adding a super-source node <math>s</math>, a super-target node <math>t</math>, an arc <math>(s,v)</math> with "infinite" capacity for each source <math>v</math>, and an arc <math>(v,t)</math> with "infinite" capacity for each target <math>v</math> (for example, the sum of the upper bounds of all arcs is sufficiently large to serve as "infinity").
	# Usually, the term '''generalized flow''' is reserved for the specific generalization in which for each node <math>v\in V\setminus\{s,t\}</math>, the ratio of the total sum of all incoming flow and the total sum of all outgoing flow is given (in the standard version, this ratio is 1 due to the flow conservation condition).		# Usually, the term '''generalized flow''' is reserved for the specific generalization in which for each node <math>v\in V\setminus\{s,t\}</math>, the ratio of the total sum of all incoming flow and the total sum of all outgoing flow is given (in the standard version, this ratio is 1 due to the flow conservation condition).
	# The max-flow problem asks for an optimal steady-state flow. However, in many applications, a certain amount of flow is to be sent as soon as possible from the source to the target. It is easy to see that, if the amount of flow is sufficiently large, then an optimal solution is constant most of the time, and the maximum steady-state flow is this constant flow.		# The max-flow problem asks for an optimal steady-state flow. However, in many applications, a certain amount of flow is to be sent as soon as possible from the source to the target. It is easy to see that, if the amount of flow is sufficiently large, then an optimal solution is constant most of the time, and the maximum steady-state flow is this constant flow.