An algebraic flow for a diagraph D=(V,A) is a generalization of a circulation for D in which the operation of addition is replaced by a binary operation defined over a commutative semigroup. A substantial literature exists in which flow-theory has been studied in this more general setting. For example, Hamacher has generalized the classical max-flow min-cut theorem to algebraic flows. In this paper, the authors show that x is an algebraic flow if and only if for each pair of distinct vertices s and t, the value of a maximum (s,t) algebraic flow with capacities x is equal to the value of a maximum (t,s) algebraic flow with capacities x. This characterization, which is called flow-symmetry, is a common generalization of two previous flow-symmetric results that have appeared in the literature. First, Lovász, by proving a conjecture of Kotzig, showed that flow-symmetry holds for the usual semigroup operation of addition of non-negative reals. That is, a vector x≥0 defined on the arc set A is a circulation for D if and only if for each pair of distinct vertices s and t the value of a maximum (s,t) flow in D with capacities x equals the value of a maximum (t,s) flow in D with capacities x. Second, in a previous paper, the authors showed that the analogous result holds for the semigroup in which the summation operator is replaced by the maximization operator. That is, x is a max-balanced flow if and only if for each pair of distinct vertices s and t, the value of a maximum bottleneck (s,t) path in D with capacities x equals the value of a maximum bottleneck (t,s) path in D with capacities x. In this paper, the authors show that these results are each special cases of the present characterization of an algebraic flow.
