Define Flow Network

A flow network is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in representations of flow networks, the source (where all flow originates) and the sink (where all flow ends) are labeled as s and t, respectively.

Here are the steps to define a flow network:

1. Identify the directed graph: A flow network is a directed graph, which means that the edges (lines connecting the nodes) have a direction. This direction is usually represented by an arrow.

2. Assign capacity to each edge: Each edge in the flow network has a capacity. This capacity is a non-negative number that represents the maximum amount of flow that the edge can carry.

3. Assign flow to each edge: Each edge in the flow network also has a flow. This flow is a non-negative number that represents the amount of flow that is currently being carried by the edge. The flow on an edge cannot exceed the capacity of the edge.

4. Identify the source and the sink: In a flow network, there is a single source node (often labeled as s) where all flow originates, and a single sink node (often labeled as t) where all flow ends.

5. Flow conservation: Except for the source and sink, the amount of flow into a node equals the amount of flow out of it.

This is the basic definition of a flow network. There are more complex versions of flow networks that include things like multiple sources and sinks, but this is the most basic version.