Basic flow definitions - Revision history

Weihe: /* Flow value */

2015-11-17T13:42:53Z

Flow value

← Older revision		Revision as of 13:42, 17 November 2015
Line 54:		Line 54:

	'''Remark:'''		'''Remark:'''
	A straightforward induction on <math>k\geq\|S\|</math> shows that for all partitions <math>(V_S,V_T)</math> of <math>V</math> with <math>S\subseteq V_S</math>, <math>T\subseteq V_T</math> and <math>\|V_S\|=k</math>, it is		A straightforward induction on <math>k\geq\|V_S\|</math> shows that for all partitions <math>(V_S,V_T)</math> of <math>V</math> with <math>S\subseteq V_S</math>, <math>T\subseteq V_T</math> and <math>\|V_S\|=k</math>, it is
	:<math>v(f)=\sum_{v\in V_S,w\in V_T\atop(v,w)\in A}f(v,w)-\sum_{v\in V_S,w\in V_T\atop(w,v)\in A}f(w,v)</math>.		:<math>v(f)=\sum_{v\in V_S,w\in V_T\atop(v,w)\in A}f(v,w)-\sum_{v\in V_S,w\in V_T\atop(w,v)\in A}f(w,v)</math>.
	In particular, mirror-symmetrically to the definition of <math>v(f)</math>, it is		In particular, mirror-symmetrically to the definition of <math>v(f)</math>, it is

Weihe: /* Flow value */

2015-11-17T13:40:26Z

Flow value

← Older revision		Revision as of 13:40, 17 November 2015
Line 50:		Line 50:
	== Flow value ==		== Flow value ==

	Let <math>S,T\in V</math> such that <math>S\cap T=\emptyset</math>, and let <math>f</math> be a flow with respect to <math>S\cup T</math>. The '''flow value''' <math>v(f)</math> of <math>f</math> is defined by		Let <math>S,T\subseteq V</math> such that <math>S\cap T=\emptyset</math>, and let <math>f</math> be a flow with respect to <math>S\cup T</math>. The '''flow value''' <math>v(f)</math> of <math>f</math> is defined by
	:<math>v(f):=\sum_{s\in S,v\in V\setminus S\atop(s,v)\in A}f(s,v)-\sum_{s\in S,v\in V\setminus S\atop(v,s)\in A}f(v,s)</math>.		:<math>v(f):=\sum_{s\in S,v\in V\setminus S\atop(s,v)\in A}f(s,v)-\sum_{s\in S,v\in V\setminus S\atop(v,s)\in A}f(v,s)</math>.

Weihe: /* Feasible flow */

2015-11-17T13:38:13Z

Feasible flow

← Older revision		Revision as of 13:38, 17 November 2015
Line 41:		Line 41:
	# A '''feasible flow''' (or '''flow''' for short) with respect to <math>W\subseteq V</math> is an arc weighting that satisfies the capacity constraints and the flow conservation condition.		# A '''feasible flow''' (or '''flow''' for short) with respect to <math>W\subseteq V</math> is an arc weighting that satisfies the capacity constraints and the flow conservation condition.
	# For <math>S,T\subseteq V</math>, a '''feasible <math>(S,T)</math>-flow''' is a feasible flow with respect to <math>W=S\cup T</math>.		# For <math>S,T\subseteq V</math>, a '''feasible <math>(S,T)</math>-flow''' is a feasible flow with respect to <math>W=S\cup T</math>.
	# For <math>s,t\in V</math>, a '''feasible <math>(s,t)</math>-flow''' is a feasible flow with respect to <math>W=\{S,T\}</math>.		# For <math>s,t\in V</math>, a '''feasible <math>(s,t)</math>-flow''' is a feasible flow with respect to <math>W=\{s,t\}</math>.

	== Preflow ==		== Preflow ==

Weihe: /* Flow value */

2015-11-16T10:43:03Z

Flow value

← Older revision		Revision as of 10:43, 16 November 2015
Line 54:		Line 54:

	'''Remark:'''		'''Remark:'''
	A straightforward induction on <math>k\geq\|S\|</math> shows that for all partitions <math>(V_S,V_T)</math> of <math>V</math> with <math>\|V_S\|=k</math>, it is		A straightforward induction on <math>k\geq\|S\|</math> shows that for all partitions <math>(V_S,V_T)</math> of <math>V</math> with <math>S\subseteq V_S</math>, <math>T\subseteq V_T</math> and <math>\|V_S\|=k</math>, it is
	:<math>v(f)=\sum_{v\in V_S,w\in V_T\atop(v,w)\in A}f(v,w)-\sum_{v\in V_S,w\in V_T\atop(w,v)\in A}f(w,v)</math>.		:<math>v(f)=\sum_{v\in V_S,w\in V_T\atop(v,w)\in A}f(v,w)-\sum_{v\in V_S,w\in V_T\atop(w,v)\in A}f(w,v)</math>.
	In particular, mirror-symmetrically to the definition of <math>v(f)</math>, it is		In particular, mirror-symmetrically to the definition of <math>v(f)</math>, it is

Weihe: /* Feasible flow */

2015-11-16T10:32:07Z

Feasible flow

← Older revision		Revision as of 10:32, 16 November 2015
Line 41:		Line 41:
	# A '''feasible flow''' (or '''flow''' for short) with respect to <math>W\subseteq V</math> is an arc weighting that satisfies the capacity constraints and the flow conservation condition.		# A '''feasible flow''' (or '''flow''' for short) with respect to <math>W\subseteq V</math> is an arc weighting that satisfies the capacity constraints and the flow conservation condition.
	# For <math>S,T\subseteq V</math>, a '''feasible <math>(S,T)</math>-flow''' is a feasible flow with respect to <math>W=S\cup T</math>.		# For <math>S,T\subseteq V</math>, a '''feasible <math>(S,T)</math>-flow''' is a feasible flow with respect to <math>W=S\cup T</math>.
	# For <math>s,t\in V</math>, a '''feasible <math>(s,t)</math>-flow''' is a feasible flow with respect to <math>~~WST~~</math>.		# For <math>s,t\in V</math>, a '''feasible <math>(s,t)</math>-flow''' is a feasible flow with respect to <math>W=\{S,T\}</math>.

	== Preflow ==		== Preflow ==

Weihe: /* Feasible flow */

2015-11-16T10:31:47Z

Feasible flow

← Older revision		Revision as of 10:31, 16 November 2015
Line 41:		Line 41:
	# A '''feasible flow''' (or '''flow''' for short) with respect to <math>W\subseteq V</math> is an arc weighting that satisfies the capacity constraints and the flow conservation condition.		# A '''feasible flow''' (or '''flow''' for short) with respect to <math>W\subseteq V</math> is an arc weighting that satisfies the capacity constraints and the flow conservation condition.
	# For <math>S,T\subseteq V</math>, a '''feasible <math>(S,T)</math>-flow''' is a feasible flow with respect to <math>W=S\cup T</math>.		# For <math>S,T\subseteq V</math>, a '''feasible <math>(S,T)</math>-flow''' is a feasible flow with respect to <math>W=S\cup T</math>.
	# For <math>s,t\in V</math>, a '''feasible <math>(s,t)</math>-flow''' is a feasible flow with respect to <math>~~W=ST~~</math>.		# For <math>s,t\in V</math>, a '''feasible <math>(s,t)</math>-flow''' is a feasible flow with respect to <math>WST</math>.

	== Preflow ==		== Preflow ==

Weihe: /* Feasible flow */

2015-11-16T10:31:38Z

Feasible flow

← Older revision		Revision as of 10:31, 16 November 2015
Line 41:		Line 41:
	# A '''feasible flow''' (or '''flow''' for short) with respect to <math>W\subseteq V</math> is an arc weighting that satisfies the capacity constraints and the flow conservation condition.		# A '''feasible flow''' (or '''flow''' for short) with respect to <math>W\subseteq V</math> is an arc weighting that satisfies the capacity constraints and the flow conservation condition.
	# For <math>S,T\subseteq V</math>, a '''feasible <math>(S,T)</math>-flow''' is a feasible flow with respect to <math>W=S\cup T</math>.		# For <math>S,T\subseteq V</math>, a '''feasible <math>(S,T)</math>-flow''' is a feasible flow with respect to <math>W=S\cup T</math>.
	# For <math>s,t\in V</math>, a '''feasible <math>(s,t)</math>-flow''' is a feasible flow with respect to <math>W=\{ST\}</math>.		# For <math>s,t\in V</math>, a '''feasible <math>(s,t)</math>-flow''' is a feasible flow with respect to <math>W=ST</math>.

	== Preflow ==		== Preflow ==

Weihe: /* Feasible flow */

2015-11-16T10:31:28Z

Feasible flow

← Older revision		Revision as of 10:31, 16 November 2015
Line 41:		Line 41:
	# A '''feasible flow''' (or '''flow''' for short) with respect to <math>W\subseteq V</math> is an arc weighting that satisfies the capacity constraints and the flow conservation condition.		# A '''feasible flow''' (or '''flow''' for short) with respect to <math>W\subseteq V</math> is an arc weighting that satisfies the capacity constraints and the flow conservation condition.
	# For <math>S,T\subseteq V</math>, a '''feasible <math>(S,T)</math>-flow''' is a feasible flow with respect to <math>W=S\cup T</math>.		# For <math>S,T\subseteq V</math>, a '''feasible <math>(S,T)</math>-flow''' is a feasible flow with respect to <math>W=S\cup T</math>.
	# For <math>s,t\in V</math>, a '''feasible <math>(s,t)</math>-flow''' is a feasible flow with respect to <math>W=\{~~S,T~~\}</math>.		# For <math>s,t\in V</math>, a '''feasible <math>(s,t)</math>-flow''' is a feasible flow with respect to <math>W=\{ST\}</math>.

	== Preflow ==		== Preflow ==

Weihe: /* Feasible flow */

2015-11-16T10:31:11Z

Feasible flow

← Older revision		Revision as of 10:31, 16 November 2015
Line 40:		Line 40:
	'''Feasibility:'''		'''Feasibility:'''
	# A '''feasible flow''' (or '''flow''' for short) with respect to <math>W\subseteq V</math> is an arc weighting that satisfies the capacity constraints and the flow conservation condition.		# A '''feasible flow''' (or '''flow''' for short) with respect to <math>W\subseteq V</math> is an arc weighting that satisfies the capacity constraints and the flow conservation condition.
	# For <math>S\subseteq V</math>, a '''feasible <math>(S,T)</math>-flow''' is a feasible flow with respect to <math>W=S\cup T</math>.		# For <math>S,T\subseteq V</math>, a '''feasible <math>(S,T)</math>-flow''' is a feasible flow with respect to <math>W=S\cup T</math>.
	# For <math>s,t\in V</math>, a '''feasible <math>(s,t)</math>-flow''' is a feasible flow with respect to <math>W=\{S,T\}</math>.		# For <math>s,t\in V</math>, a '''feasible <math>(s,t)</math>-flow''' is a feasible flow with respect to <math>W=\{S,T\}</math>.

Weihe: /* Feasible flow */

2015-11-16T10:30:53Z

Feasible flow

← Older revision		Revision as of 10:30, 16 November 2015
Line 40:		Line 40:
	'''Feasibility:'''		'''Feasibility:'''
	# A '''feasible flow''' (or '''flow''' for short) with respect to <math>W\subseteq V</math> is an arc weighting that satisfies the capacity constraints and the flow conservation condition.		# A '''feasible flow''' (or '''flow''' for short) with respect to <math>W\subseteq V</math> is an arc weighting that satisfies the capacity constraints and the flow conservation condition.
	# For <math>S,T\subseteq V</math>,		# For <math>S\subseteq V</math>, a '''feasible <math>(S,T)</math>-flow''' is a feasible flow with respect to <math>W=S\cup T</math>.
	#a '''feasible <math>(S,T)</math>-flow''' is a feasible flow with respect to <math>W=S\cup T</math>.
	# For <math>s,t\in V</math>, a '''feasible <math>(s,t)</math>-flow''' is a feasible flow with respect to <math>W=\{S,T\}</math>.		# For <math>s,t\in V</math>, a '''feasible <math>(s,t)</math>-flow''' is a feasible flow with respect to <math>W=\{S,T\}</math>.