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 network circulation is a flow with zero net supply at every vertex. A feasible residual network circulation changes one feasible flow into another with the same prescribed supplies. It decomposes into directed cycles, giving the negative-cycle optimality test for minimum-cost flow.

On $\{0,\dots ,m{\}}^2$, give an adjacent edge capacity equal to the larger endpoint distance $|i_1-i_2|$ from the diagonal. The set $S=\{i_1<i_2\}$ has $2m$ outgoing edges: two at each interior diagonal vertex and one at each endpoint. Every such edge has capacity one. Thus any flow from above to below the diagonal is at most $2m$; a feasible path decomposition attaining this value certifies optimality by weak duality.

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 directed edge capacity is the upper bound $c_{ij}\ge 0$ on the feasible nonnegative flow through that edge. In a residual network, its forward residual capacity is $c_{ij}-f_{ij}$ and its backward residual capacity is $f_{ij}$. Increasing every edge capacity need not increase the maximum flow by that same amount, because a cut of a flow network can contain several edges.

A fluid flow is motion described by a velocity field $\mathbf{u}(\mathbf{x},t)$. The trajectories of fluid elements satisfy $d\mathbf{x}/dt=\mathbf{u}(\mathbf{x},t)$; the mass density and other fields obey their conservation laws and constitutive equations. This physical motion differs from a flow on a flow network.

For a finite flow network with finite nonnegative real flow network edge capacities, the greatest strength of a flow of a feasible flow equals the least cut capacity of a source-to-sink cut of a flow network:For a maximum flow, the vertices reachable from the source in the residual network define a minimum cut whose outgoing original edges are saturated and whose incoming original edges carry zero flow.^[ref]

Why is a cut of a flow network an upper bound? Sum flow conservation on its source side $S$. Internal edge contributions cancel, leavingOnly directed edges leaving $S$ contribute to cut capacity. Directed edges entering $S$ are subtracted in net flow, so adding their capacities to the upper bound would lose the intended bottleneck. This inequality is weak duality; the theorem says the bound is attained, an instance of strong duality. Its beauty is that a routing plan and a separating boundary independently witness each other's optimality.

In the running flow network, the two internal vertices give four possible source sides. For $S=\{s\}$, the cut capacity is $c_{sa}+c_{sb}=3+2=5$. For $S=\{s,a\}$ it is $c_{sb}+c_{ab}+c_{at}=2+1+2=5$. For $S=\{s,b\}$ it is $c_{sa}+c_{bt}=3+3=6$; the incoming edge $a\to b$ contributes nothing to that cut capacity. Finally, $S=\{s,a,b\}$ gives $c_{at}+c_{bt}=2+3=5$. Thus the minimum cut has cut capacity $5$, matching the explicitly computed maximum flow.

Ford and Fulkerson's 1956 paper opens with a railway-capacity question attributed there to T. Harris and proves a minimal-cut theorem as Theorem 1. Its original formulation uses graph paths carrying nonnegative amounts; the residual reachability certificate for maximum flow below gives the finite directed flow network proof used here.^[ref]

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]

A cut of a flow network of minimum cut capacity among cuts separating the prescribed source and sink. The max-flow min-cut theorem identifies this capacity with the maximum possible flow value.

Consider a finite directed flow network with source $s$, sink $t$, and nonnegative finite flow network edge capacities $c_e$. A feasible flow assigns $0\le f_e\le c_e$ to each arc and satisfies flow conservation at every vertex except $s,t$. Its value $|f|$ is net outflow from $s$, equivalently net inflow to $t$. A maximal flow here means a flow of greatest value, also called a maximum flow. A source–sink cut of a flow network is a partition $(S,S^c)$ with $s\in S$, $t\notin S$; its cut capacity is $c(S,S^c)={\sum }_{u\in S,v\notin S}{c}_{uv}$, summing directed arcs from $S$ to its complement.

The max-flow min-cut theorem statesFor any feasible flow and cut, summing flow conservation over vertices in $S$ cancels internal arcs and gives $|f|={\sum }_{S\to S^c}{f}_e-{\sum }_{S^c\to S}{f}_e\le c(S,S^c)$. This proves the upper bound by every cut.

For the reverse bound, a maximum exists: the feasible set is a nonempty closed subset of the bounded product ${\prod }_e[0,c_e]$, hence compact, and $|f|$ is continuous. Choose a maximizing flow $f$. Its residual network has a forward arc for unused capacity $c_e-f_e$ and a reverse arc for cancellable flow $f_e$, retaining original-arc identities if necessary. If a residual path joined $s$ to $t$, the minimum of its positive residual capacities would be positive. Increasing forward flows and cancelling reverse flows by this amount would preserve all constraints while increasing $|f|$, a contradiction.

Let $S$ consist of vertices reachable from $s$ through positive residual arcs. Then $t\notin S$. An original arc from $S$ to $S^c$ must be saturated, since otherwise its forward residual arc would make its endpoint reachable. An original arc from $S^c$ to $S$ must carry zero flow, since a positive reverse residual arc would again extend reachability. ThusThe upper bound and this equality prove the theorem and exhibit a residual reachability certificate for maximum flow. The argument works for real capacities and does not assume that an arbitrary augmenting-path algorithm terminates in finitely many steps.

A global bifurcation joins two mechanisms: a long passage near a hyperbolic equilibrium point and a finite excursion returning the unstable manifold to its neighborhood. Eigenvalue ratios control the local passage, while the geometry of the global return decides reinjection, folding and trapping. In the real symmetric case there are two returning branches and a power-law cusp. In the saddle-focus case rotation adds infinitely many oscillations to that cusp. The following maps display both mechanisms explicitly.

For the Lorenz configuration, enter on $z=h$ at $(x,y,h)$ and leave on $x=sh$, where $s=\mathrm{sgn}(x)$. Solving the linear flow gives a flight timePut $\gamma =-\hat{\lambda }/{\lambda }_{+}>\delta =-{\lambda }_{-}/{\lambda }_{+}$. The outgoing coordinates areThe smooth global map from each outgoing section to the incoming section has, to leading order,up to the choice of which unstable branch carries the sign of $\nu$. Reflection symmetry makes the offsets opposite and the leading coefficients equal. Since the stable transverse coordinate is multiplied by the higher power $|x{|}^{\gamma }$, it contributes only subleading terms to the leading scalar map. Absorbing powers of $h$ into a positive constant gives the Lorenz power return mapThe line $x=0$ lies on the stable manifold and has no finite return; the discontinuity is therefore a genuine missing return, not an arbitrary value to assign at zero.

If $\delta >1$, the derivative $A\delta |x{|}^{\delta -1}$ tends to zero. For $\mu <0$, there are two attracting fixed points, $x=\pm s$ with $s=-\mu +A{s}^{\delta }\simeq -\mu$. They describe two symmetry-related one-lobe attracting flow periodic orbits. For $\mu >0$, the orbit alternates between $s$ and $-s$, where $s=\mu -A{s}^{\delta }\simeq \mu$; its multiplier is $(A\delta s^{\delta -1}{)}^2<1$. This represents one attracting flow periodic orbit traversing both lobes. At $\mu =0$ the two homoclinic loops meet: this is the contracting gluing scenario, with diverging flow period at the connection.

If $\delta <1$, the local derivative is unbounded, and the small periodic orbits are repelling in the expanding return direction. For $\mu >0$, the small positive fixed point has $s\simeq (\mu /A{)}^{1/\delta }$, with a multiplier tending to infinity; there is a symmetry-related negative fixed point as well. More complex motion follows from the two branches, not merely from a large derivative at one fixed point. Choose $I=[-c\mu ,c\mu ]$ with $0<c<1$. The inverse branches areFor sufficiently small positive $\mu$, both lie inside $I$, their images are disjoint, and their derivatives are $O({\mu }^{1/\delta -1})\to 0$. Nested inverse images for every infinite sign sequence therefore define a Cantor invariant set. Iterating the forward map shifts the sequence. This constructs periodic itineraries of every symbolic period and nonperiodic itineraries; transverse contraction in the full return turns the expanding two-strip mechanism into a horseshoe.

This is the local chaotic Lorenz mechanism. A robust attracting Lorenz set additionally needs a global trapping region and the appropriate return properties. The scalar asymptote and $\delta <1$ alone do not prove that every nearby orbit is attracted to one chaotic set; periodic windows, escaping orbits and other global returns must be distinguished. Symmetry is crucial to obtaining the two homoclinic branches together in a single parameter variation.

In cylindrical coordinates the saddle-focus linearization isUse a small incoming neighborhood of the stated section point $(\rho ,0,-\mu )$. A nearby incoming cylinder $r=\rho$ is smoothly equivalent to that section for this calculation. Denote the positive unstable passage coordinate by $x=z_{\mathrm{in}}>0$ and leave at $z=h$. ThenThe global map is smooth in the outgoing Cartesian coordinates $r_{\mathrm{out}}\cos {\theta }_{\mathrm{out}}$ and $r_{\mathrm{out}}\sin {\theta }_{\mathrm{out}}$. Its returned unstable coordinate therefore has the leading formCombining the two trigonometric terms, absorbing the fixed scales into the amplitude and phase, and using the evenness of cosine givesThe returned radial section coordinate is $\rho +O(x^{\delta })$, supplying the thin transverse direction of the full two-dimensional return. In particular its determinant has order $x^{2\delta -1}$; the exponent is also obtained by integrating the flow divergence ${\lambda }_{+}+2{\lambda }_{-}$ over the local flight. Thus $\delta >1/2$ is the volume-contracting range. Corrections from the returned radial deviation enter at order $x^{2\delta }$, smaller than the fixed-point term $x$ in this range. Only positive returned $x$ on the chosen branch belong to the scalar return domain.

For $\delta >1$,For small $\mu <0$, there is one small attracting fixed point $x=-\mu +O(|\mu {|}^{\delta })$, representing a stable long-period periodic orbit. It ends in the homoclinic connection at $\mu =0$; for $\mu >0$ there is no sufficiently small positive fixed point. The oscillations alone do not create expanding chaos when their derivative tends to zero.

For $1/2<\delta <1$, there is both net volume contraction and a positive saddle equilibrium value ${\lambda }_{+}+{\lambda }_{-}>0$. At the connection, fixed points satisfyThe right side tends to zero, while the phase runs through infinitely many rotations. There are therefore infinitely many positive fixed points accumulating at zero near successive cosine zeros. Their successive size ratios tend to $e^{-\pi /q}$ and their derivative magnitudes diverge. In the full return they are saddle equilibrium periodic orbits: one multiplier expands and the thin transverse direction contracts. Their flow periods grow as ${\lambda }_{+}^{-1}\log (h/x)$.

The oscillatory graph also supplies the complicated itineraries. Take a sufficiently small positive return interval. Near successive zero crossings, narrow monotone subintervals map across that interval with arbitrarily large slope. Two or more inverse branches contract into it, so repeated inverse choices give symbolic invariant sets just as in part (a); lifting the strips to the thin two-dimensional return gives horseshoes and infinitely many periodic orbits. This explains the Shilnikov chaotic mechanism rather than only naming it.

For nonzero splitting, the graph shifts vertically. Fixed-point tangencies with slope $+1$ create saddle-node bifurcations of periodic orbits; crossings of slope $-1$ give period doubling. Near an oscillatory extremum the derivative can be small, allowing stable periodic windows. Such thresholds accumulate geometrically toward the homoclinic parameter, interspersed with expanding returns. Hence the unfolding can contain complicated switching, arbitrarily long periods and chaos, rather than a single attracting periodic branch. This is log-periodic accumulation of Shilnikov cycles. The conclusion concerns invariant sets and possible attractors allowed by the return geometry; it does not assert that a homoclinic connection alone makes all nearby trajectories chaotic.