Finite flow network

Mathematical statement

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.

Representative formula (exact TeX)

V(f,s,t)=z

Assumptions

• Vertices, edges, capacity and flow keys correspond completely one-to-one; no loops or duplicate directed edges.
• Every sum uses exact rational arithmetic.

Symbol scope

• V — flow-value operator
• f — finite edge flow
• s — source vertex
• t — sink vertex
• z — exact flow value

Intuition, definition, and misconceptions

Network qualification fixes the directed-edge convention first.

Capacity and conservation are separate feasibility obligations.

Source and sink flow-value calculations must agree.

A total flow value alone does not check each edge or internal vertex, and a feasible flow is not automatically maximum.

Adopted derivation guide

The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.

Prerequisites

• Finite directed graph — Fix the network carrier.
• Function mapping — Capacities and flows map edges to values.
• Linear programming — Capacity and conservation are constraints.

Verification boundary

This slice does not build max-flow/min-cut, residual networks or an optimality proof.

not_formalized

This does not mean the content is false; it means no replayable computational or formal evidence is registered yet.

Next obligation

Add the max-flow min-cut theorem.

Same-source structured data

This page and the interactive view use the same object and existing language edition; this adds no proof or human review.