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$.

A flow on a directed graph satisfying capacity constraints and a specified net inflow $d_v$ at each vertex. Positive $d_v$ denotes consumption and negative $d_v$ supply. Summing all balances cancels each edge once as inflow and once as outflow, so ${\sum }_v{d}_v=0$ is necessary. With balanced demands and no lower bounds, add a source edge of flow network edge capacity $-d_v$ into every supply vertex and an edge of flow network edge capacity $d_v$ from each demand vertex to a new sink. A maximum flow saturating all auxiliary edges exists exactly when the demands are feasible.

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.

A prescribed minimum amount on each directed edge can be removed by substituting $f_e={\ell }_e+x_e$. The new capacity constraints are $0\le x_e\le c_e-{\ell }_e$. For a circulation with vertex demands using net inflow $d_v$, the adjusted demand is $d_v^{\prime }=d_v-({\sum }_u{\ell }_{uv}-{\sum }_w{\ell }_{vw})$. Solving the adjusted problem and adding $\ell$ back gives a one-to-one correspondence of feasible solutions. In particular, removing a lower bound on $u\to v$ increases $u$'s residual demand and decreases $v$'s by that amount.

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 flow network is a finite directed graph $G=(V,E)$ with nonnegative flow network edge capacities $c_e$, together with distinct source and sink vertices $s,t$. A feasible flow in the nonnegative directed-edge convention is a function $f:E\to {\mathbb{R}}_{\ge 0}$ satisfying the capacity constraints and flow conservation:Its flow value is the net outflow at the source,which equals the net inflow at the sink by flow conservation.

A cut of a flow network is a partition of a set $(S,V\setminus S)$ with $s\in S$ and $t\notin S$. Its cut capacity counts only directed edges leaving $S$:The net flow across the cut of a flow network subtracts flow on edges returning into $S$, and equals $|f|$.

For the following parts, a circulation with vertex demands has no exceptional source or sink in the original directed graph. Instead it satisfies net inflow minus net outflow equal to $d_v$ at every vertex. Thus positive demands consume flow, and negative demands supply flow.

Write flow balance using the positive-inflow conventionRemove the lower bounds on network flow by writing $f_{uv}={\ell }_{uv}+x_{uv}$, where only ${\ell }_{BC}=4$ is nonzero. Then $0\le x_{uv}\le c_{uv}-{\ell }_{uv}$, and its required flow balance isIn the order $A,B,C,D$, the lower-bound contribution is $(0,-4,4,0)$, soThe resulting flow network edge capacities areAdd a new source $s$ with an edge $s\to A$ of flow network edge capacity $6$, and a new sink $t$ with edges $B\to t$ and $D\to t$ of flow network edge capacities $1$ and $5$. A feasible flow saturating these new edges is equivalent to a solution for $x$: ordinary flow conservation in the enlarged flow network produces exactly the residual supplies and demands above. All source and sink edges must be saturated, requiring flow value $6$.

Start the Edmonds–Karp algorithm at zero flow. Repeated breadth-first search in the residual network permits the following shortest augmenting paths; when paths tie, choose the one through $B$ first.

The first augmenting path has three edges. Once $B\to t$ is saturated, the next shortest possibilities have four edges, so steps $2$ and $3$ respect the breadth-first search rule. Each augmentation adds the usual backward edges to the residual network, though these particular augmentations need only forward edges. Now $s\to A$ is saturated, so no further augmenting path exists. The cut of a flow network with source side $\{s\}$ has cut capacity $6$, proving that the obtained flow is a maximum flow.

The original-edge values for $x$ are $(4,2,0,3,2)$ in the order $AB,AC,BC,BD,CD$. Restore the lower bound to obtainAll original capacity constraints hold, and $f_{BC}=4$ meets its lower bound. The net inflows at $A,B,C,D$ are respectivelyThe original network therefore admits a feasible circulation with vertex demands.

For any feasible circulation with vertex demands, sum its defining flow balance over all vertices:Every directed edge $ab\in E$ contributes $+f_{ab}$ exactly once to the first sum, at its head $b$, and $-f_{ab}$ exactly once to the second, at its tail $a$. The two sums therefore contain exactly the same terms. They cancel, givingThis is global flow conservation: internal transport cannot create or destroy the total amount. Lower bounds on network flow and capacity constraints restrict which flows are feasible but do not affect the cancellation. The condition is necessary, not sufficient: insufficient flow network edge capacities can still prevent satisfying balanced demands.

Use nonnegative amounts on the original directed edges of the flow network. A feasible flow is a function $f:E\to {\mathbb{R}}_{\ge 0}$ satisfying the capacity constraints $f(u,v)\le c(u,v)$ and flow conservation at every internal vertex:Its flow value is net outflow at the source,Summing flow conservation shows that this is also net inflow at the sink. Subtracting incoming flow matters when the source has incoming edges.

An $s$–$t$ cut of a flow network is a partition of a set $(S,V\setminus S)$ with $s\in S$ and $t\notin S$. Its cut capacity is the total outward flow network edge capacity,Incoming edges do not contribute to this sum. Equivalently, one may use the antisymmetric net-flow convention, but the nonnegative arc convention above will also be used in the subsequent reductions.

Sum net outflow over all vertices in the source side $S$. An internal directed edge occurs once positively and once negatively, so it cancels. All internal vertices have zero net outflow by flow conservation, and the sink is outside $S$. ThereforeThe second sum is nonnegative, while every term in the first satisfies its capacity constraint. Consequently,This is direct accounting from flow conservation; it does not invoke the max-flow min-cut theorem.

First give $w$ the vote of every voter whose allowed set contains $w$. Let their number be $K$. This loses no possible strict victory: starting with any winning assignment, changing such a ballot to $w$ increases $w$'s score and weakly decreases an opponent's score. Thus a winning assignment exists exactly when one exists with these $K$ ballots fixed.

Every remaining voter must now be assigned to an allowed opponent, and each opponent may receive at most $K-1$ votes. If any allowed set is empty, there is no valid election assignment. With at least two candidates, $K=0$ immediately makes a unique victory impossible. With only the candidate $w$, every nonempty ballot set forces that candidate, so the answer is yes under the question's strict-comparison definition.

For the remaining case $K\ge 1$, make a flow network with a vertex for each remaining voter and each opponent. Add source-to-voter arcs of flow network edge capacity one, voter-to-opponent arcs of flow network edge capacity one for the allowed choices, and opponent-to-sink arcs of flow network edge capacity $K-1$. Compute an integral maximum flow. ThenA flow saturating all voter arcs assigns each remaining voter to exactly one allowed opponent, by integrality and flow conservation. The sink-arc capacity constraints give every opponent strictly fewer than $K$ votes. Conversely, any winning assignment with the fixed $K$ votes defines just such a saturating feasible flow. The flow network has at most $n+m+2$ vertices and $O(n+m+{\sum }_i|C_i|)$ arcs, hence the decision takes polynomial time.

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

Reinhard Diestel authored a graph-theory text developing structural and algorithmic questions about vertices, edges and connectivity. Its treatment of flows connects local capacity constraints with global cuts and routes through a network.^[ref]

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.