Directed Network¶

Definition¶

A directed network is a network whose edges have specified orientations. An edge $i\to j$ allows traversal or flow from $i$ to $j$ ; reverse traversal is not implied by its existence.

Interpretation¶

Direction represents asymmetric connections, such as one-way streets, pipes that carry flow one way, or activities that must happen in a given order. An edge $i\to j$ says that one can go from $i$ to $j$ , and nothing about going back.

A network of vertices A to F with arrows giving each edge a direction; the edge from E to D exists, but not the reverse.

Every edge in the figure carries an arrow. The red edge $E\to D$ allows the move from $E$ to $D$ , but no edge leads from $D$ to $E$ ; since the only edge leaving $D$ is $D\to F$ and $F$ has no outgoing edge, $E$ cannot be reached from $D$ at all.

So every route must follow the arrows, and a two-way connection needs two opposite edges $i\to j$ and $j\to i$ $i$ . Direction is essential in the maximum flow problem, where each capacity belongs to one directed edge.

Key Results¶

Incoming and outgoing edges have different roles at a vertex.
Maximum-flow constraints respect the original edge directions.
A backward residual edge cancels assigned flow; it is not necessarily an original directed edge.

Examples¶

The red edge permits $E\to D$ $D$ , but there is no edge permitting $D\to E$ $E$ . Such orientations can represent one-way streets, pipe flows or activity precedence.

The maximum-flow network has outgoing edges at the source and incoming edges at the sink.
An activity edge $i\to j$ points from its preceding event to its following event.

Prerequisites¶

Network

Sources¶

OR Modelling · Week 4

Aliases: directed graph, digraph

Last updated: 20 October 2026 03:02