Course contentsShow
← Computer Science
Lesson 1025 of 2,87224. Minimum Spanning Trees and Network FlowFree lesson

Valid Flows and Flow Value

Define what constitutes a valid flow and how to calculate the total flow value leaving the source.

Valid Flows and Flow Value

What You'll Learn

You'll learn what makes a flow "valid" in a network and how to measure the total amount flowing from source to sink.

What Is a Valid Flow?

A valid flow in a flow network is an assignment of flow values to each edge that obeys two critical rules you've already learned:

  1. Capacity Constraints: The flow on each edge cannot exceed that edge's capacity
  2. Flow Conservation: At every intermediate vertex (not the source or sink), incoming flow equals outgoing flow

Think of it like a water pipe system: water can't exceed pipe capacity, and water can't magically appear or disappear at junctions—whatever flows in must flow out.

Flow Value

The flow value (often denoted |f|) is the total amount of "stuff" successfully pushed from the source vertex to the sink vertex.

To calculate it, you have two equivalent methods:

  • At the source: Sum all flow leaving the source minus any flow entering the source
  • At the sink: Sum all flow entering the sink minus any flow leaving the sink

In most flow networks, nothing flows back into the source or out of the sink, so the calculation simplifies to just the outgoing flow from the source (or incoming flow to the sink).

Why This Matters

Determining whether a flow is valid is the first step in network flow algorithms. The flow value tells you how "good" your solution is—the goal of maximum flow problems is to find a valid flow with the largest possible flow value.

Key Takeaway: A valid flow respects capacity and conservation constraints, and the flow value measures the total throughput from source to sink.