derivation-mko-finite-flow-network-01 · ocme-new142-reader-adoption-20261021
Audit a complete flow network with antiparallel edges, a zero-capacity edge and a zero-flow vertex.
Only network qualification, capacity, conservation and flow value; feasibility alone does not establish maximum flow.
algebrasetsflow_defG1 — V={s,a,b,t,z}, source s and distinct sink t; ordered edges sa,sb,ab,at,bt,ba,za have capacities (3,2,1,2,3,1,0) and flows (2,1,1,1,2,0,0). z has no edge except zero-capacity za.f_e,c_e — flow and capacity per directed edge|f| — net flow valuemko_definition · cited — Use a finite loop-free simple directed graph with distinct source s and sink t. Antiparallel edges are allowed, but each ordered pair appears at most once. Valid capacities/flows are exact nonnegative rationals. Feasibility requires0≤f(e)≤c(e) and complete inflow=outflow at every internal vertex. Cross-check source net outflow against sink net inflow. Zero capacities and disconnected vertices are legal. Feasibility is not maximum flow; no min-cut equality or augmenting-path optimality is claimed ahead of its theorem. · mko-finite-flow-networkalgebra · prerequisite — Use real-field identities; division requires a nonzero denominator and multiplication by a positive number preserves inequalities.sets · prerequisite — Compute unions, intersections, complements, inclusion and preimages element by element.flow_def · prerequisite — A finite simple directed network has no self-loop or duplicate ordered pair, but permits antiparallel edges; feasible flows satisfy every capacity bound and internal conservation, with value equal to source net outflow and sink net inflow.Before
E=\{(s,a),(s,b),(a,b),(a,t),(b,t),(b,a),(z,a)\}After
|E|=7,\quad u\ne v\text{ and each ordered pair occurs once}Conditions: none
Rule: flow_def · Uses: G1
Leaf basis: flow_def
Each edge has endpoints in V, no loop and no duplicate ordered pair; ab and ba are legal distinct edges.
Before
(f_e,c_e)= (2,3),(1,2),(1,1),(1,2),(2,3),(0,1),(0,0)
After
0\le f_e\le c_e\quad\forall e\in E
Conditions: none
Rule: algebra · Uses: G1, S01
Leaf basis: algebra
Check all seven pairs for nonnegativity and capacity; the zero-capacity edge carries zero flow.
Before
\operatorname{in}(a)=f_{sa}+f_{ba}+f_{za}=2+0+0After
\operatorname{in}(a)=2=f_{ab}+f_{at}=\operatorname{out}(a)Conditions: none
Rule: algebra · Uses: G1
Leaf basis: algebra
List all three incoming and both outgoing edges of a.
Before
\operatorname{in}(b)=f_{sb}+f_{ab}=1+1After
\operatorname{in}(b)=2=f_{bt}+f_{ba}=\operatorname{out}(b)Conditions: none
Rule: algebra · Uses: G1
Leaf basis: algebra
The complete inflow and outflow of b agree.
Before
\operatorname{in}(z)=0,\quad\operatorname{out}(z)=f_{za}=0After
\operatorname{in}(z)=\operatorname{out}(z)Conditions: none
Rule: algebra · Uses: G1
Leaf basis: algebra
z has no inflow and its sole outgoing edge has zero capacity, so conservation holds; it is a zero-flow vertex, not an isolated graph vertex.
Before
|f|=\operatorname{out}(s)-\operatorname{in}(s)=2+1-0After
|f|=3=\operatorname{in}(t)-\operatorname{out}(t)=1+2-0Conditions: none
Rule: algebra · Uses: G1, S03, S04, S05
Leaf basis: algebra
Source and sink net values independently evaluate to the same result.
Before
0\le f\le c,\quad\operatorname{in}=\operatorname{out}\text{ at }a,b,zAfter
f\text{ is feasible with value }3Conditions: none
Rule: flow_def · Uses: S01, S02, S03, S04, S05, S06
Leaf basis: flow_def
Only after all edges and internal vertices are checked is feasibility concluded.
Before
f'=(3,1,1,2,2,0,0)\text{ in the same edge order}After
f'\text{ is feasible with }|f'|=4>3Conditions: none
Rule: algebra · Uses: G1, S07
Leaf basis: algebra
The alternative satisfies every capacity; a has 3 in and 1+2 out, b has 1+1 in and 2 out, and z stays zero, proving the original is not maximum.
No substeps in this guide.
S08 · premise_audit · G1, S07 — A larger feasible flow refutes maximum-value optimality without invoking the min-cut theorem.S07 · premise_audit · S01, S02, S03, S04, S05, S06 — No optimality certificate has been supplied, so it is not called maximum.S06 · premise_audit · G1, S03, S04, S05 — Net values subtract reverse-direction flow; this graph has no source in-edge or sink out-edge, so these are zero.S05 · premise_audit · G1 — A zero-capacity edge remains a graph edge: z→a→t is a graph path but carries no positive flow because of the zero capacity; z is not isolated.S04 · premise_audit · G1 — ab is incoming at b and outgoing at a.S03 · premise_audit · G1 — Do not omit ba or za merely because their flows are zero.S02 · premise_audit · G1, S01 — A small total value does not imply edge legality; each edge is separately checked.S01 · premise_audit · G1 — Antiparallel is not duplicate; both capacity and flow keys match all seven edges.Capacity and flow keys may neither omit nor add edges.
Compute both s and t independently.
reject — A simple directed graph forbids duplicate ordered pairs, not antiparallel edges.reject — Every edge and internal vertex still requires auditing.reject — S08 gives a larger feasible flow.The original flow is feasible with value 3; a value-4 feasible flow proves it is not maximum.
2 declared checks for this guide; only the listed expressions are covered.
b1b2f1dcf8c50d67a93fe52d95f8eef7b3abba9fa93c0418ecb143d4880146293689ec4965fd3d889bdf228e7d45a98a09ddfb2c9ddde2b86d73fa9084b762788ec009ac727c1ea81b32343655d29131ebaa1df4SCOPED_LEAD_AND_BILINGUAL_CONTEXT_REVIEWSame-source full JSON (formulas, ASTs, controls and revision log)