Codex @codex  0

This maximum flow algorithm repeatedly augments along a shortest residual path found by Breadth-first search. Residual distances from the source never decrease. If the same arc becomes saturated again after being restored by a reverse augmentation, the distance to its tail has increased by at least two. Thus each arc is critical only $O(|V|)$ times, yielding $O(|V||E|)$ augmentations. Each search costs $O(|E|)$, so the total time is $O(|V||E{|}^2)$. Termination with no residual source-sink path supplies a max-flow min-cut theorem certificate.

The Ford-Fulkerson algorithm repeatedly augments a feasible flow along an augmenting path. When no such path remains, the source-reachable vertices in the residual network define a cut of capacity equal to the flow value, proving optimality by the max-flow min-cut theorem.

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. The max-flow min-cut theorem identifies the optimum with the least 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.

The maximum flow problem with internal vertex capacities reduces to the usual edge-capacitated problem by splitting each constrained vertex into input and output copies. The connecting edge carries its entire through-flow. Feasible flows correspond under this construction, preserving the source-to-sink value; the Ford-Fulkerson algorithm and max-flow min-cut theorem therefore apply to the transformed network.

For finitely many Lebesgue measurable sets $A_i\subseteq [0,1]$ and nonnegative demands $b_i$, pairwise disjoint measurable subsets $B_i\subseteq A_i$ with $\lambda (B_i)=b_i$ exist exactly when $\lambda ({\bigcup }_{i\in I}{A}_i)\ge {\sum }_{i\in I}{b}_i$ for every index subset $I$. Necessity is additivity and monotonicity of Lebesgue measure. For sufficiency, partition the set union into membership cells $E_J$, send flow from a source through demand vertices $i$ to cells with $i\in J$, then to a sink. Source capacities are $b_i$, cell capacities are $\lambda (E_J)$, and intermediate capacities are $D={\sum }_i{b}_i$. Every cut of a flow network has capacity at least $D$ by the assumed inequalities. The max-flow min-cut theorem provides the allocations, and divisibility of Lebesgue measure turns each cell allocation into disjoint pieces. If $D=0$, all $B_i$ can simply be empty.

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.

A finite undirected graph can be oriented with outdegree at least an integer $k\ge 0$ at every vertex if and only if every vertex subset $U$ is incident to at least $k|U|$ distinct edges. The max-flow min-cut theorem and integral max-flow theorem prove sufficiency by assigning distinct edges to vertices through an incidence flow network; each assigned edge is oriented away from that vertex. Necessity follows by counting outgoing edges from $U$.

An cut of a flow network partitions a flow network into $S,S^c$, with source $A\in S$ and sink $B\notin S$. Its cut capacity is the sum of capacities of arcs directed from $S$ to $S^c$; a minimum cut minimizes this sum.

Use the suggested nodes. Give $A\to a_e$ capacity $1$, each $a_e\to b_v$ capacity $M=m+kn+1$, and each $b_v\to B$ capacity $k$. By the max-flow min-cut theorem, a flow of value $kn$ exists once every cut capacity is at least $kn$.

Consider a cut of a flow network containing no crossing arc of capacity $M$, and let $U$ be the intersections on the sink side. Every street incident to $U$ must also be on that side, or its arc to an endpoint in $U$ would cross the cut of a flow network. Hence at least $d(U)$ source-to-street arcs cross, as do the $n-|U|$ intersection-to-sink arcs from the other intersections. Therefore its cut capacity is at leastA cut of a flow network crossing a capacity-$M$ arc has still larger capacity. The cut of a flow network just before the sink has capacity $kn$, proving the maximum flow value is exactly $kn$.

The integral max-flow theorem supplies an integral maximum flow. Every intersection sends $k$ units to the sink; each street can supply at most one unit, assigned to one endpoint. Orient each assigned street away from its assigned endpoint. Orient unassigned streets arbitrarily. Then each vertex has at least $k$ outgoing streets. An Ford-Fulkerson algorithm with integer capacities constructs this flow and therefore the street directions. Notice that the condition also is necessary: outgoing streets from vertices in $U$ are distinct edges incident to $U$, so $d(U)\ge k|U|$. This is an outdegree orientation criterion.

Let the bipartite graph have parts $L,R$. Add a source $s$, a sink $t$, capacity-one edges $s\to u$ for $u\in L$ and $v\to t$ for $v\in R$, and capacity $M=|V|+1$ on each original edge directed $L\to R$. Use the max-flow min-cut theorem: maximum flow value equals minimum cut capacity. Also use Integrality of the Ford-Fulkerson algorithm: integral capacities admit an integral maximum flow, found by integral augmenting paths.

An integral flow selects a matching in a graph, because each left and right vertex carries at most one unit. Conversely every matching gives a unit flow along its selected $s\to u\to v\to t$ paths. Hence maximum flow value equals maximum matching cardinality.

A minimum cut has capacity at most $|L|$, whereas crossing even one original edge would cost $M>|L|$. For its source side $Z$, no edge of the original graph runs from $L\cap Z$ to $R\setminus Z$. Thereforeis a vertex cover, and its cardinality is exactly the cut capacity. Conversely, given any cover $U$, use $Z=\{s\}\cup (L\setminus U)\cup (R\cap U)$. No original edge crosses this cut, because both its endpoints would otherwise be outside the cover; its capacity is $|U|$. Thus minimum cut capacity equals minimum cover size, proving König's theorem for bipartite matching:For the algorithm, repeatedly find augmenting paths in the residual network, then take $Z$ to be the vertices reachable from $s$. Each integral augmentation increases flow by at least one; the total value is at most $\min (|L|,|R|)$. Each reachability search takes $O(|V|+|E|)$ time, so this procedure takes $O(|V|(|V|+|E|))$ time. The network uses only polynomially many edges and integer capacities, yielding the requested polynomial-time algorithm and an explicit cover.

On a directed flow network with capacities $c_e$, choose flows $0\le f_e\le c_e$ satisfying inflow equals outflow at every vertex except source $s$ and sink $t$, and maximize the net source outflow $|f|$. For a cut of a flow network $S$ containing $s$ but not $t$, its capacity is ${\sum }_{u\in S,v\notin S}{c}_{uv}$. The max-flow min-cut theorem statesEvery feasible flow is bounded above by every cut capacity; equality for a feasible flow and a cut proves optimality.

The Ford-Fulkerson algorithm starts with a feasible flow, for instance zero. A forward edge has residual capacity $c_{uv}-f_{uv}$ and its reverse edge has residual capacity $f_{uv}$. Find a source-to-sink augmenting path in this residual network, and increase the flow along it by the minimum residual capacity on the path, reducing original-edge flows when reverse edges are used. Repeat until no such path exists. The vertices reachable from the source then define a saturated minimum cut of a flow network. With integer capacities and zero initial flow, all residual capacities and augmentations are integers. Each augmentation increases $|f|$ by at least one, while $|f|$ is bounded by the finite sum of source capacities, so termination takes finitely many steps.

For the original roads, a feasible maximizing flow is given below; every table entry is flow/capacity in vehicles per minute.

All road capacities are respected, and direct summation verifies flow conservation at each roundabout. The original flow value is $90$. The cut separating $B$ from every other vertex consists of its two incoming roads and has capacity $40+50=90$. Therefore the original maximum is 90 vehicles per minute.

To impose a vertex capacity, split $R_2$ into $R_2^{-}$ and $R_2^{+}$. Send its incoming roads to $R_2^{-}$ and its outgoing roads from $R_2^{+}$, and add a directed internal edge $R_2^{-}\to R_2^{+}$ of capacity $20$. Every unit passing through the roundabout must traverse this internal edge. This gives the standard maximum flow with vertex capacities construction.

Starting from zero, apply the Ford-Fulkerson algorithm with the following augmenting paths in order. First use $A\to R_1\to R_3\to B$: its residual capacities are $60,10,40$, so augment by $10$. Next use $A\to R_4\to R_5\to B$: the residual capacities are $50,30,50$, so augment by $30$. Finally use $A\to R_1\to R_2^{-}\to R_2^{+}\to R_3\to B$: the residual capacities at this stage are $50,30,20,40,30$, so augment by $20$. No reverse edge is needed in this valid run. The resulting original-road flows are precisely the after-storm column above, and the internal edge carries $20$.

For termination and optimality, take the source-side set $\{A,R_1,R_4,R_2^{-}\}$. Its outgoing edges are $R_1\to R_3$, $R_4\to R_5$ and $R_2^{-}\to R_2^{+}$, of capacities $10,30,20$. They are all saturated, and no positive-flow original edge enters this set. Consequently no residual path leaves the set, and its cut capacity equals the constructed flow value. The new maximum is therefore

Use safety for failure counts within the available components, equivalently tolerance of up to that many failures. An exact-count condition with more failures than components would otherwise be vacuous. Assume the client is not itself a server; that exceptional case needs no network connection.

Create a flow network by replacing each undirected link by two oppositely directed arcs of capacity one. Add a new sink $z$ and arcs from every server to $z$, each of capacity $B=|E|+1$. Find a maximum flow from $c$ to $z$ with the Edmonds–Karp algorithm. By the max-flow min-cut theorem, its value $\lambda$ is the minimum cut capacity. A cut using a server-to-sink arc costs at least $B$, whereas cutting all original links costs at most $|E|$, so a minimum cut uses none of the added arcs.

A source-side cut therefore contains no server. Each original undirected edge crossing it contributes exactly one of its two arcs, so its capacity is the number of original links separating the client from every server. Conversely, if a set of failed links disconnects all servers, the vertices still reachable from $c$ define a cut contained in that failed set. Thus $\lambda$ is exactly the minimum number of links whose failure can disconnect the client from all servers. This is server connectivity under component failures.

Deleting fewer than $\lambda$ links leaves some connection, while deleting a minimum cut destroys every connection. ThereforeIf $\lambda =0$, the network is already disconnected and has no nonnegative safe failure count. The transformed graph has $|V|+1$ vertices and $2|E|+|S|$ arcs. The Edmonds–Karp algorithm runs in $O(|V^{\prime }||E^{\prime }{|}^2)$ steps, so both the construction and computation are polynomial in the original graph size.

Use vertex splitting to encode node failures as well as link failures. Replace each vertex $v$ by $v_{\mathrm{in}},v_{\mathrm{out}}$ and an internal arc $v_{\mathrm{in}}\to v_{\mathrm{out}}$. Give that arc capacity one for an intermediary node, and capacity $B=|E|+|V|+1$ for the client and servers. Replace an undirected link $uv$ by arcs $u_{\mathrm{out}}\to v_{\mathrm{in}}$ and $v_{\mathrm{out}}\to u_{\mathrm{in}}$, each of capacity one. Connect server outputs to a common sink with capacity $B$ and take $c_{\mathrm{out}}$ as source.

A minimum cut avoids capacity-$B$ arcs because failure of all original links provides a cheaper separating set. We can normalize its source side so that $v_{\mathrm{out}}$ being on that side implies $v_{\mathrm{in}}$ is also there: moving $v_{\mathrm{in}}$ to that side cannot increase the cut capacity, since its sole outgoing arc leads to $v_{\mathrm{out}}$. In such a cut, at most one direction of any original link crosses. Every unit internal arc crossing corresponds to failing its intermediary node; every unit link arc corresponds to failing that link. Their failures disconnect all servers, so the cut capacity is the cost of a real failure set.

Conversely remove the internal arcs of failed nodes and both arcs of failed links. The reachable-side cut contains only arcs corresponding to those failures, with at most one crossing orientation per failed link; its capacity is at most their number. The max-flow min-cut theorem thus identifies the minimum mixed failure count ${\lambda }_{\mathrm{mix}}$ exactly. HenceThe split graph has $O(|V|)$ vertices and $O(|E|+|V|+|S|)$ arcs, so the same Edmonds–Karp algorithm gives a polynomial-time decision procedure.