Network Flow Ontology

FLOW ALGEBRA
TITLE: Network Flow Ontology
DOMAIN: Discrete Mathematics / Graph Theory / Network Flow
SOURCE_URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/graph-theory/network-flow-ontology.html
VERSION: 1.0
DATE: 2026-10-11
AUTHORS: Mark Higgins — Sky (Recursive AI)
SOURCE_STATUS: Formal mathematical synthesis; live source page not independently verified.

1. PURPOSE
Represent directed capacitated networks, feasible flows, residual networks, augmenting paths, cuts, and maximum-flow/minimum-cut reasoning in typed, machine-consumable form.

2. TYPED ENTITIES
TYPE Vertex = identifier
TYPE DirectedEdge = (tail: Vertex, head: Vertex)
TYPE Capacity = Real where value >= 0
TYPE FlowValue = Real where value >= 0
TYPE Network = (V: Set[Vertex], E: Set[DirectedEdge], c: E -> Capacity, s: Vertex, t: Vertex)
TYPE FeasibleFlow = (network: Network, f: E -> FlowValue)
TYPE ResidualArc = (tail: Vertex, head: Vertex, residual_capacity: Real)
TYPE STCut = (S: Set[Vertex], T: Set[Vertex])
TYPE Path = Sequence[Vertex]
TYPE FlowCertificate = (flow: FeasibleFlow, value: Real, verification: Boolean)
ASSUME: s != t; s,t in V; E subseteq V x V; finite V and E.
NOTE: Parallel arcs require unique edge identifiers rather than ordered-pair keys. Self-loops, if present, do not affect flow value or cuts.

3. FORMAL DEFINITIONS
CAPACITY_CONSTRAINT: for each e in E, 0 <= f(e) <= c(e).
FLOW_CONSERVATION: for each v in V excluding {s,t}, sum_{e enters v} f(e) = sum_{e leaves v} f(e).
FLOW_VALUE: |f| = sum_{e leaves s} f(e) - sum_{e enters s} f(e).
SINK_BALANCE: |f| = sum_{e enters t} f(e) - sum_{e leaves t} f(e).
CUT: S union T = V; S intersect T = empty; s in S; t in T.
CUT_CAPACITY: c(S,T) = sum_{e=(u,v) in E, u in S, v in T} c(e).
RESIDUAL_FORWARD: for original arc e=(u,v), residual capacity c(e)-f(e) on u->v.
RESIDUAL_BACKWARD: for original arc e=(u,v), residual capacity f(e) on v->u.
RESIDUAL_NETWORK: include positive-capacity residual arcs, retaining arc provenance and aggregating or distinguishing parallel residual contributions correctly.
AUGMENTING_PATH: directed s-to-t path in residual network with positive residual capacity on every arc.
BOTTLENECK: minimum residual capacity along an augmenting path.

4. FLOW OPERATIONS
flow.initialise_zero(network) -> FeasibleFlow
flow.validate(network, f) -> Boolean
flow.value(network, f) -> Real
residual.construct(network, f) -> ResidualNetwork
path.find_augmenting(residual, s, t) -> Optional[Path]
flow.augment(f, path, delta) -> FeasibleFlow
cut.capacity(network, S, T) -> Real
flow.maximum(network) -> FlowCertificate
cut.minimum(network) -> STCut

5. ALGEBRA AND INVARIANTS
INVARIANT_01: feasible flow obeys capacity constraints.
INVARIANT_02: feasible flow obeys conservation at all intermediate vertices.
INVARIANT_03: for any feasible flow and any s-t cut, |f| <= c(S,T).
INVARIANT_04: an augmenting path with bottleneck delta > 0 increases |f| by delta.
INVARIANT_05: a feasible flow is maximum iff its residual network has no s-t augmenting path.
MAX_FLOW_MIN_CUT: max_f |f| = min_{(S,T) s-t cut} c(S,T).
INTEGRALITY: integer capacities admit an integer-valued maximum flow.
CAUTION: an arbitrary augmenting-path strategy with irrational real capacities need not terminate; use a terminating algorithm and state its assumptions.

6. ALGORITHMIC FLOWS
EDMONDS_KARP:
  precondition: finite directed network, nonnegative capacities.
  initialise zero flow.
  while BFS finds s-to-t residual path:
    delta := minimum positive residual capacity on path.
    augment flow by delta, respecting forward/backward residual arc provenance.
    rebuild or update residual network.
  return flow and reachable-set minimum cut.
  time_complexity: O(|V| * |E|^2) under standard adjacency representation.
DINIC:
  construct BFS level graph and send blocking flows repeatedly.
  general_time_complexity: O(|V|^2 * |E|).
MINIMUM_CUT_CERTIFICATE:
  S := vertices reachable from s through positive residual arcs after termination.
  T := V minus S.
  assert t not in S.
  assert |f| = c(S,T) within exact arithmetic or justified numeric tolerance.

7. INFERENCE RULES
RULE FLOW_FEASIBLE:
  IF capacity_constraints(f) AND conservation(f) THEN feasible(f).
RULE CUT_UPPER_BOUND:
  IF feasible(f) AND valid_st_cut(S,T) THEN value(f) <= capacity(S,T).
RULE OPTIMALITY:
  IF feasible(f) AND no_augmenting_path(residual(f),s,t) THEN maximum_flow(f).
RULE DUAL_CERTIFICATE:
  IF feasible(f) AND valid_st_cut(S,T) AND value(f)=capacity(S,T)
  THEN maximum_flow(f) AND minimum_cut(S,T).
RULE BOTTLENECK_AUGMENT:
  IF augmenting_path(P) AND delta=bottleneck(P) AND delta>0
  THEN augmentation_preserves_feasibility AND new_value=old_value+delta.

8. SEMANTIC RELATIONSHIPS
NetworkFlow IS_A DirectedGraphModel
NetworkFlow HAS_PART Vertex
NetworkFlow HAS_PART DirectedEdge
DirectedEdge HAS_PROPERTY Capacity
FeasibleFlow SATISFIES CapacityConstraint
FeasibleFlow SATISFIES FlowConservation
ResidualNetwork DERIVED_FROM NetworkFlow
AugmentingPath EXISTS_IN ResidualNetwork
MinimumCut DUAL_CERTIFICATE_FOR MaximumFlow
MaximumFlow RELATED_TO LinearProgramming
NetworkFlow APPLIED_TO TransportNetwork
NetworkFlow APPLIED_TO CommunicationNetwork
NetworkFlow APPLIED_TO BipartiteMatching

9. SEMANTIC_EQUIVALENCE
"maximum flow" <=> "max flow" [terminological]
"minimum cut" <=> "min cut" [terminological]
"flow conservation" <=> "flow balance at intermediate vertices" [contextual]
"augmenting path" <=> "positive-residual-capacity source-to-sink path" [formal]
DISTINGUISH: maximum flow != minimum-cost flow.
DISTINGUISH: cut capacity != net flow across cut; they coincide only under appropriate saturation and reverse-flow conditions.
DISTINGUISH: directed residual arcs != original directed arcs.

10. VALIDATION
CHECK unique_vertex_ids.
CHECK source_and_sink_distinct_and_present.
CHECK edge_endpoints_exist.
CHECK finite_nonnegative_capacities.
CHECK 0 <= f(e) <= c(e) for all e.
CHECK flow_conservation_except_source_sink.
CHECK source_sink_flow_values_equal.
CHECK residual_forward_backward_consistency.
CHECK cut_partition_and_source_sink_membership.
CHECK computed_flow_value_leq_all_tested_cut_capacities.
CHECK optimality_certificate_matches_cut_capacity.
NUMERICS: prefer exact integer/rational arithmetic; document tolerance for floating point.

11. WORKED EXAMPLE
V = {s,a,b,t}
E capacities: s->a:3, s->b:2, a->b:1, a->t:2, b->t:3.
Feasible flow: f(s,a)=3, f(s,b)=2, f(a,b)=1, f(a,t)=2, f(b,t)=3.
Flow value = 5.
Cut S={s}, T={a,b,t} has capacity 3+2=5.
By max-flow min-cut, flow is maximum and cut is minimum.

12. CONFIDENCE
mathematical_definitions: 1.00 (standard finite-network theory)
algorithmic_claims: 0.99 (under stated assumptions)
source_page_alignment: UNVERIFIED
confidence_policy: confidence describes claim support, not a probability that a theorem is true.

13. FLOW_HASH
canonicalisation: UTF-8; LF line endings; normalise field ordering and whitespace before hashing.
algorithm: SHA-256
hash_value: TO_BE_COMPUTED_AT_INGESTION
hash_scope: canonical flow body excluding mutable FLOW_HASH.hash_value.

14. UPDATE_MODEL
version: 1.0
update_triggers: source_revision, definition_change, algorithm_correction, ontology_relationship_change
revision_policy: increment version; regenerate hash; retain provenance and changelog.
source_url: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/graph-theory/network-flow-ontology.html

15. AI_CONSUMPTION
parse_mode: typed semantic flow
primary_entity: NetworkFlow
reasoning_modes: constraint_checking, graph_search, optimality_proof, cut_certificate
required_checks: type_safety, capacity_bounds, conservation, residual_consistency
outputs: feasible_flow, flow_value, maximum_flow, minimum_cut, provenance, confidence
failure_modes: invalid_capacity, infeasible_flow, malformed_network, numerical_instability
safety: do not claim optimality without an augmenting-path or cut-based certificate.

END FLOW ALGEBRA