Walk assignments and augmentation along residual walks #
Weighting a directed walk p by q : K gives the arrow assignment walkAssignment p q, which
places n • q on an arrow that p traverses n times; natural-number scalar multiplication needs
no multiplicative structure on K. A walk from s to t raises the excess at t by q and
lowers the excess at s by q, so a closed walk gives a circulation. A walk that repeats no
arrow, such as a directed path or cycle, places q on each arrow it traverses and zero elsewhere.
For 0 ≤ q it is then an ordinary s–t flow for any nonnegative capacities that are at least
q along the walk.
Applied to the residual arrows of a feasible assignment, this is augmentation. Augmenting an
ordinary s–t flow between distinct terminals s ≠ t along a residual walk that repeats no
arrow, by an amount between zero and the residual capacities along the walk, gives a flow of value
larger by that amount. The largest such amount is the bottleneck of the walk, its least residual
capacity, which is positive on an augmenting path, where every residual capacity is positive.
Directed paths and cycles repeat no arrow (TauCeti.ArrowWalk.IsPath.nodup_arrows,
TauCeti.ArrowWalk.IsCycle.nodup_arrows), so all of this applies to them. Along a closed
residual walk that repeats no arrow, the residual update preserves feasibility for arbitrary lower
and upper bounds and preserves every excess: this is cycle augmentation of bounded circulations.
Main definitions #
TauCeti.walkAssignment p q: the assignment of the walkpweighted byq.TauCeti.walkFlow: a walk repeating no arrow, weighted by a feasible amount, as an ordinary flow.TauCeti.Flow.augmentWalk: augmentation of an ordinary flow along a residual walk.TauCeti.Flow.augmentBottleneck: augmentation by the bottleneck of the residual walk.
Main results #
TauCeti.Assignment.map_walkAssignment: additive changes of coefficients commute with weighting a walk.TauCeti.excessAt_walkAssignment: a walk fromstotweighted byqhas excessqattand-qats.TauCeti.walkAssignment_mem_Icc: a walk repeating no arrow, weighted byq, lies between zero and any nonnegative capacities that are at leastqalong the walk.TauCeti.walkAssignment_bottleneck_le: a walk repeating no arrow, weighted by its bottleneck for a nonnegative assignment, is bounded by the assignment.TauCeti.card_filter_pos_sub_walkAssignment_bottleneck_lt: subtracting a nonempty walk of positive arrows, weighted by its bottleneck, strictly decreases the number of positive arrows.TauCeti.Flow.val_augmentWalkandTauCeti.Flow.val_augmentBottleneck: augmentation along a residuals–twalk between distinct terminalss ≠ tincreases the value by the augmenting amount.TauCeti.Flow.val_lt_val_augmentBottleneck: augmentation along an augmentings–tpath by its bottleneck strictly increases the value.TauCeti.Flow.augmentWalk_memandTauCeti.Flow.augmentBottleneck_mem: augmentation preserves values in an additive subgroup that contains the capacities, as does the bottleneck (TauCeti.Flow.bottleneck_residualCapacity_mem).TauCeti.residualUpdate_walkAssignment_mem_IccandTauCeti.excessAt_residualUpdate_walkAssignment_self: augmentation along a residual walk preserves feasibility, and along a closed walk it also preserves every excess.
References #
- L. R. Ford, D. R. Fulkerson, Maximal flow through a network, Canadian J. Math. 8 (1956).
- R. K. Ahuja, T. L. Magnanti, J. B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, 1993 (augmenting paths and cycles).
Walk assignments #
The assignment of the walk p weighted by q: an arrow traversed n times by p carries
n • q.
Instances For
Additive coefficient maps commute with weighting a walk.
A walk that traverses no arrow twice carries its weight on each arrow it traverses.
A walk assignment takes values in any additive submonoid containing the weight.
A walk weighted by a nonnegative amount gives a nonnegative assignment.
Feasibility of a walk. A walk that traverses no arrow twice, weighted by q ≥ 0, lies
between zero and any nonnegative capacities that are at least q on every arrow it traverses.
A walk that traverses no arrow twice, weighted by its bottleneck for a nonnegative
assignment f, is bounded by f.
The total value that a walk weighted by q brings into v is q times the number of visits
of the walk to v after its start.
Excess of a walk. A walk from s to t weighted by q has excess q at t, excess -q
at s, and zero excess elsewhere; for a closed walk the two cancel.
A closed walk gives a circulation.
A walk from s to t that traverses no arrow twice, weighted by q ≥ 0, as an ordinary
s–t flow for nonnegative capacities that are at least q on every arrow it traverses.
Instances For
A walk between distinct vertices, weighted by q, is a flow of value q.
Subtracting a nonempty walk of positive arrows, weighted by its bottleneck, strictly decreases the number of arrows of positive value: the arrows of positive value afterwards were positive before, and an arrow attaining the bottleneck becomes nonpositive. Repeated arrows may make the difference negative.
Subtracting a walk of positive arrows that traverses no arrow twice, weighted by its bottleneck, leaves a nonnegative assignment in the same additive subgroup and strictly decreases the number of positive arrows.
Subtract a walk from s to t ≠ s, weighted by q > 0, from a nonnegative assignment f
that vanishes on the arrows entering s and on the arrows leaving t, such that the difference
g is still nonnegative. Then f has negative excess at s and positive excess at t, and every
vertex of negative, respectively positive, excess for g has negative, respectively positive,
excess for f.
Augmentation #
Cycle augmentation. Updating along a closed residual walk preserves the excess at every
vertex. Together with residualUpdate_walkAssignment_mem_Icc, augmenting a bounded circulation
along a residual cycle gives a bounded circulation.
Feasibility of augmentation. Updating a feasible assignment f along a residual walk that
traverses no arrow twice, by an amount between zero and the residual capacities along the walk,
gives a feasible assignment. Lower bounds may be negative. For a closed walk, such as a residual
cycle, the update also preserves every excess (excessAt_residualUpdate_walkAssignment_self).
The augmentation of an ordinary s–t flow f along a residual walk from s to t that
traverses no arrow twice, by an amount q between zero and the residual capacities along the walk:
each forward residual arrow of the walk raises its arrow's value by q, and each reverse residual
arrow lowers it by q.
Instances For
Augmenting along a residual walk between distinct terminals increases the value by the augmenting amount.
Augmenting a flow with values in an additive subgroup along a residual walk, by an amount in the subgroup, gives a flow with values in the subgroup.
The augmentation of an ordinary s–t flow f along a residual walk from s to t that
traverses an arrow but no arrow twice, by its bottleneck: the least residual capacity of an arrow
of the walk, which is the largest amount that the residual capacities along the walk allow.
Instances For
Augmenting along a residual walk between distinct terminals by its bottleneck increases the value by the bottleneck.
The bottleneck of a residual walk lies in an additive subgroup that contains the capacities and the flow values.
Augmenting by the bottleneck preserves values in an additive subgroup that contains the capacities.
Augmentation along an augmenting path. If every arrow of a residual walk between distinct terminals has positive residual capacity, as on an augmenting path, then augmenting by the bottleneck strictly increases the value of the flow.