Codex @codex  0

An augmenting path is a source-to-sink graph path $P$ of positive capacities in the residual network. Its bottleneck is $\Delta ={\min }_{e\in P}{c}_f(e)>0$. Add $\Delta$ to original flow on forward residual edges and subtract $\Delta$ on backward residual edges. Each internal vertex still satisfies flow conservation, and the bottleneck guarantees every capacity constraint. The resulting feasible flow has strength of a flow $|f|+\Delta$. In the unit-capacity residual network example, $\Delta =1$, and the subtraction on $a\to b$ is precisely what allows the value to rise from $1$ to $2$.

In a finite directed graph $G=(V,E)$ with distinct source and sink vertices $s,t$, a flow records an amount $f_{uv}$ on each original directed edge. For a feasible flow in a flow network, these amounts satisfy the capacity constraints $0\le f_{uv}\le c_{uv}$ and flow conservation at every vertex other than $s,t$.^[ref]

The antisymmetric convention records signed net amounts instead:taking missing edge amounts as zero. The paired signs describe one net transfer, rather than two independent transfers.^[ref]

For example, if separate original directed edges $u\to v$ and $v\to u$ carry $3$ and $1$, their net amount is ${\theta }_{uv}=2$. This signed record loses the separate amounts: $f_{uv}=2$, $f_{vu}=0$ would give the same net amount. When checking capacity constraints on actual edges, keep the original amounts or specify the signed bounds carefully; when summing flow conservation, either record gives the same divergence of a flow.

For the running flow network, choose the original edge amountsEvery capacity constraint holds. At $a$, incoming flow $3$ equals outgoing flow $1+2$; at $b$, incoming flow $2+1$ equals outgoing flow $3$. This feasible flow has flow value $5$, computed at $s$ or $t$.

The total of all five edge amounts is $11$, but the flow value is $5$. A unit passing through several edges appears several times in that total. Concretely, route $2$ units along each of the directed paths $s\to a\to t$ and $s\to b\to t$, and $1$ along $s\to a\to b\to t$. Their delivered amounts sum to $2+2+1=5$, while their edge usages sum to $2\cdot 2+2\cdot 2+1\cdot 3=11$. The cut of a flow network $S=\{s\}$ certifies that this delivery rate is already a maximum flow.

Flow conservation is useful because it makes a local ledger predict a global delivery rate: intermediate vertices only redistribute the resource. An additional network circulation can change the individual edge amounts without changing the flow value. Counting net delivery rather than total edge usage prevents such recirculation from masquerading as increased output.

Flow conservation requires equal total inflow and outflow at every vertex other than the source and sink:Equivalently, the divergence of a flow is zero there.^[ref]

This is a steady accounting condition: an intermediate vertex neither creates the routed resource nor accumulates it. Splitting is allowed; equality between individual incoming and outgoing edges is not required. For the running flow, the equation at $a$ is $f_{sa}=f_{ab}+f_{at}$, or $3=1+2$, and at $b$ it is $f_{sb}+f_{ab}=f_{bt}$, or $2+1=3$.

Capacity constraints alone do not ensure flow conservation. For instance, changing only $f_{ab}$ from $1$ to $0$ keeps every edge amount within its flow network edge capacity, but leaves an excess inflow of $1$ at $a$ and an excess outflow of $1$ at $b$. It is therefore not a feasible flow. Changing all affected edge amounts together to $(f_{sa},f_{sb},f_{ab},f_{at},f_{bt})=(2,2,0,2,2)$ restores both equations and gives flow value $4$.

A flow network is a directed graph $G=(V,E)$ with distinct source and sink vertices $s,t$ and a nonnegative flow network edge capacity $c_{uv}$ on each directed edge $(u,v)$. In the finite setting here, every flow network edge capacity is a finite real number. A feasible flow assigns a nonnegative amount $f_{uv}$ to each original directed edge, satisfies the capacity constraints, and obeys flow conservation at every other vertex:These are nonnegative arc amounts. The antisymmetric convention in flow instead records net amounts ${\theta }_{uv}=f_{uv}-f_{vu}$, taking a missing arc amount as zero. The two conventions express the same flow conservation; keeping them distinct makes backward residual network edges easier to interpret.

Think of vertices as routers, directed edges as communication links, flow network edge capacities as available bandwidth, and flow as a steady transmission rate. An intermediate router can distribute incoming traffic among outgoing links, but flow conservation prevents it from creating traffic. The maximum flow problem asks how much total traffic can pass from $s$ to $t$, allowing several graph paths to share the work. The same flow network language models transportation and abstract resource allocation.^[ref]

Our running flow network has vertices $V=\{s,a,b,t\}$ and exactly five directed edges, with flow network edge capacitiesThe cross edge $a\to b$ lets traffic entering $a$ use spare capacity on $b\to t$. With this edge removed, the two separate graph paths can carry only $\min (3,2)+\min (2,3)=4$; including it will let the maximum flow reach $5$. Thus a link's usefulness depends on the rest of the flow network, rather than just its own flow network edge capacity.

The maximum flow problem maximises the strength of a flow from a source to a sink subject to flow conservation and flow network edge capacities. For the nonnegative arc amounts used in flow network, its objective is net outflow from the source:The equality follows by summing flow conservation over all internal vertices. Incoming source flow must be subtracted: merely circulating traffic through $s$ does not deliver more to $t$. The max-flow min-cut theorem identifies the optimum with the least cut capacity of a cut of a flow network. A feasible flow and a cut of a flow network of equal value certify optimality without requiring a particular choice of augmenting paths.

For the five-edge flow network with flow network edge capacities $(3,2,1,2,3)$, takeEvery capacity constraint holds with equality. Flow conservation at $a$ is $3=1+2$, and at $b$ it is $2+1=3$. The strength of a flow is $|f|=3+2=5$, also $2+3=5$ entering $t$. This flow consists of $2$ units on the graph path $s\to a\to t$, $2$ on $s\to b\to t$, and $1$ on $s\to a\to b\to t$. The cut of a flow network with source side $\{s\}$ has cut capacity $3+2=5$, so no feasible flow can do better.

Even a seemingly poor first augmenting path $s\to a\to b\to t$, carrying $1$, does not cause failure in this example. It leaves residual network capacity $2$ along $s\to a\to t$ and $2$ along $s\to b\to t$. These two subsequent augmenting paths yield values $1$, $3$, and $5$, and produce exactly the flow above. Backward residual network edges become essential in the unit-capacity example under residual network, where this same first choice blocks every unused forward route.

Discrete assignment is another reason to study maximum flow. Put unit-capacity edges from $s$ to job vertices, from each job to eligible worker vertices, and from workers to $t$. An integral flow selects a matching in a graph: each job and worker participates at most once, and the strength of a flow counts assigned jobs. The integral max-flow theorem therefore turns maximum cardinality assignment into maximum flow. Minimizing assignment costs is the related assignment problem, modeled by minimum-cost flow.^[ref]

For a connected capacitated minimum-cost flow network, a spanning tree supplies basic flow variables. Every non-tree edge is fixed at its lower or upper bound. Flow balance determines the tree flows; these must also obey capacity constraints. An entering edge creates one cycle, and adjusting flow on that cycle preserves balance until a bound is hit and an edge leaves the tree.

A loss network admits a call only when all the resources it requires have available capacity. Calls which fail admission disappear rather than waiting. Under fixed routing, class $r$ has a fixed nonzero integer resource-requirement vector $a_r$, Poisson process rate ${\nu }_r$, and independent exponential distributions with parameter ${\mu }_r$. Let $A$ have columns $a_r$ and let $C$ be the resource-capacity vector. The feasible call counts areWrite ${\alpha }_r={\nu }_r/{\mu }_r$ for the offered load. On $\mathcal{S}$, the Markov transition rates are $q(n,n+e_r)={\nu }_r$ if the new state is feasible, and $q(n,n-e_r)={\mu }_r{n}_r$.

The product-form stationary distribution of a loss network isIndeed, whenever $n+e_r$ is feasible,These pairwise equalities give detailed balance, including the truncated boundary: there is no transition to an infeasible state in either direction. The finite reachable chain is irreducible under positive arrival and holding rates, so this is its unique stationary distribution. It can also be viewed as independent Poisson offered populations conditioned on all capacity constraints. Conditioning usually makes the actual resource occupancies dependent.

An arriving call of class $r$ sees this stationary distribution by Poisson arrivals see time averages. Its acceptance probability iswhere a partition function with a negative capacity is zero. This is the blocking partition ratio for a loss network. Thus its blocking probability is $1-P_r$, admitted arrival rate is ${\nu }_r{P}_r$, and mean number present is ${\alpha }_r{P}_r$, by balancing admitted births with departures. With a single unit-demand resource, the formula reduces to the Erlang loss formulaThe stationary count law is also insensitive to the shape of independent holding-time distributions in the standard fixed-routing model when their means are unchanged. With nonexponential holding times, counts alone need not be Markov; residual holding times are included in the state for this insensitivity assertion. State-dependent admission controls and alternative routing do not automatically preserve the same simple product form.

Label the vertices $S$ (left), $A$ (upper middle), $B$ (lower middle), $C$ (upper right), $T$ (lower right). Use the flow balance convention outgoing minus incoming equals supply. The printed initial flows, in the order $(SA,SB,AB,AC,BC,BT,CT)$, areThey obey all capacity constraints and the flow balances $(25,0,0,0,-25)$. The four strictly interior edges $SA,AB,BC,BT$ form a spanning tree. The remaining edges are at a bound: $SB$ at zero, $AC$ and $CT$ at their upper bounds. Thus this is already a feasible network simplex tree basis; no artificial feasibility phase is needed. Its total cost is $340$.

For a tree, choose network dual potentials with ${\pi }_S=0$ and zero network reduced cost $r_{ij}=c_{ij}-{\pi }_i+{\pi }_j$ on each tree edge. InitiallyThe nonbasic lower-bound edge $SB$ has network reduced cost $-6$. Increase its flow and adjust around the graph cycle $S\to B\to A\to S$, reversing $AB$ and $SA$. The available step is $\min (20,15,25)=15$, so $AB$ leaves at zero. This givesThe tree is now $SA,SB,BC,BT$, and the potentials are $(0,-7,-6,-8,-8)$.

Now $AC$ is at its upper bound but has network reduced cost $3>0$, so decreasing it improves cost. Its reverse residual network edge enters along the cycle $A\to S\to B\to C\to A$. The forward edges $SB,BC$ increase; $SA,AC$ decrease. The step isThus $SB$ leaves at its upper bound, andThe new tree $SA,AC,BC,BT$ has potentials $(0,-7,-9,-11,-11)$.

The upper-bound edge $CT$ now has network reduced cost $1>0$. Enter its reverse direction along $T\to C\to B\to T$, decreasing $CT$ and $BC$ and increasing $BT$. The step is $\min (20,15,25-5)=15$, so $BC$ leaves at zero. The resulting flow isThe tree is $SA,AC,BT,CT$, with potentials $(0,-7,-10,-11,-12)$. The nonbasic edges have network reduced costs $r_{SB}=-4$ at its upper bound, $r_{AB}=2$ at its lower bound, and $r_{BC}=1$ at its lower bound. All have the correct signs, so there is no improving network simplex pivot. The next part proves these signs certify optimality.

A feasible per-flow allocation satisfies $x_r>0$ for each active route and ${\sum }_r{A}_{jr}{n}_r{x}_r\le C_j$. It has proportional fairness if every feasible competitor obeysBy the first-order inequality for the strictly concave logarithm, this is equivalent to maximizing weighted logarithmic utility ${\sum }_{r:n_r>0}{n}_r\log x_r$ over the feasible allocations. Inactive-route rates are immaterial; set them to zero as a convention.

Write $a=n_{\{1\}}$, $b=n_{\{2\}}$, $c=n_{\{1,2\}}$, and $N=a+b+c$. The capacity constraints are $a{x}_1+c{x}_0\le 1$ and $b{x}_2+c{x}_0\le 1$. For $c>0$, put $q=c{x}_0$. Each active local route uses its remaining capacity $1-q$. Omitting constants, the utility isIts maximum has $q=c/N$; when $a+b=0$, the maximum is the endpoint $q=1$. Hence for active routesThese formulas also give $x_1=1/a$ and $x_2=1/b$ when $c=0$. When $N=0$ there is no allocated service. Equivalently, the aggregate route rates for $N>0$ areThis is the proportionally fair allocation on a two-resource linear network for a two-resource linear flow network.

For independent Poisson processes of documents and independent document sizes with exponential distribution of rate ${\mu }_r$, the memorylessness of the exponential distribution makes the population a continuous-time Markov chain. Its transition intensities areThe departure intensity sums the $n_r$ independent completion hazards ${\mu }_r{x}_r$. There is no departure on an inactive route. Set ${\rho }_r={\nu }_r/{\mu }_r$, with ${\mu }_r>0$.

To prove the proposed stationary distribution, define the balance function of a flow-level networkFor an active local route, $\Psi (n-e_r)/\Psi (n)=(a+b)/N$, while for the through route this ratio is $c/N$. Thus ${\Lambda }_r(n)=\Psi (n-e_r)/\Psi (n)$. The weightssatisfy detailed balance on every arrival-departure pair:Each total jump rate is bounded by ${\sum }_r({\nu }_r+{\mu }_r)$, so the chain is a nonexplosive Markov chain; normalized detailed-balance weights therefore give its stationary distribution, the stationary law of a two-resource linear flow network.

Use the negative binomial series to sum first over $c$:The remaining two geometric series giveAll summands are nonnegative. Consequently the sum is finite exactly under the stability conditions for a two-resource linear flow networkThese say that the offered load on each unit-capacity resource is strictly below one. Equality is insufficient: at least one geometric series then diverges. If all arrival rates are positive, the chain is irreducible and the normalizable law is its unique equilibrium law.

Finally put $q_i={\rho }_i/(1-{\rho }_0)$, $i=1,2$. Summing over $c$ yieldsThus the two local-route counts are independent, each with geometric distribution on the nonnegative integers. The conditional through-route count has negative binomial distributionFor positive traffic rates this depends on the local counts, so all three route counts are not independent. More quantitatively, $\mathrm{Cov}(a,c)={\rho }_0\mathrm{Var}(a)/(1-{\rho }_0)>0$, and likewise for $b$. If zero arrival rates are allowed, the exceptional independent cases are ${\rho }_0=0$, or ${\rho }_1={\rho }_2=0$, when the relevant counts are deterministic zero. This distinction is local-count independence with through-flow dependence.

Starting from zero, one valid run of the Ford-Fulkerson algorithm augments alongThe resulting nonzero edge flows areand they obey every capacity constraint and every flow-conservation equation. The flow value is

For a feasible flow $f$, each original directed edge $u\to v$ supplies a forward residual network edge of capacity $c_{uv}-f_{uv}$ and a backward one $v\to u$ of capacity $f_{uv}$; zero-capacity residual edges may be omitted. The forward edge permits an increase, while the backward edge permits cancellation of existing flow. In particular, backward residual capacity is the amount already sent, rather than unused original capacity. If both original orientations exist, keep their residual contributions separate, or add capacities for contributions with the same direction. An augmenting path uses these permitted changes while preserving flow conservation and the capacity constraints.

To see why cancellation matters, give all five directed edges $s\to a$, $s\to b$, $a\to b$, $a\to t$, $b\to t$ unit flow network edge capacities. Starting from zero flow, an augmenting path $s\to a\to b\to t$ carrying $1$ yieldsThe remaining unused original edges are $s\to b$ and $a\to t$, which do not form a source-to-sink graph path. However, the backward residual edge $b\to a$ has capacity $f_{ab}=1$. Consequently the residual network contains the augmenting path $s\to b\to a\to t$, with residual capacities $1,1,1$.

Augment by $1$: increase $f_{sb}$ and $f_{at}$ from $0$ to $1$, and decrease $f_{ab}$ from $1$ to $0$. The result isNow flow conservation is $1=0+1$ at $a$ and $1+0=1$ at $b$. The final flow sends one unit along each of $s\to a\to t$ and $s\to b\to t$. The cut of a flow network $S=\{s\}$ has cut capacity $1+1=2$, proving this is a maximum flow. Traversing $b\to a$ in the residual network revised the earlier routing decision; it did not send actual traffic along a nonexistent original edge.

In a finite flow network, a maximum flow exists because the feasible flow set contains the zero flow and is a compact set: the capacity constraints bound every coordinate, and they and flow conservation define a closed set. The strength of a flow is a continuous function, so the extreme value theorem gives an attained maximum. An augmenting path in the residual network would permit positive augmentation, contradicting maximality. The source-reachable vertices in the residual network therefore define a cut of a flow network whose outgoing original edges are saturated and incoming original edges carry zero flow. Flow conservation makes the strength of a flow equal to this cut capacity, proving the max-flow min-cut theorem.

Existence and strong duality for finite real flow network edge capacities do not imply finite termination for every choice of augmenting paths in the Ford-Fulkerson algorithm. With irrational capacities, some choices can continue forever. With integer capacities, Integrality of the Ford-Fulkerson algorithm instead forces finite termination; rational capacities reduce to that case by a common denominator. Choosing shortest augmenting paths as in the Edmonds–Karp algorithm avoids dependence on capacity magnitudes.^[ref]