Graph Terminology for Network Flows

Introduces the fundamental graph-theoretic vocabulary used in network flow problems: directed graphs, nodes, arcs, in-degree and out-degree, and the special role of source, sink, intermediate nodes, and arc capacities in a flow network.

Step 1 of 157%

Tutorial

Directed Graphs, Nodes, and Arcs

A directed graph (or digraph) is a pair $G = (N, A)$ where $N$ is a finite set of nodes (also called vertices) and $A$ is a set of arcs (also called directed edges). Each arc is an ordered pair $(i, j)$ with $i, j \in N$ , representing a directed connection from $i$ to $j$ .

The order matters: the arc $(i, j)$ is different from the arc $(j, i)$ .

For example, the digraph with

N = \{1, 2, 3, 4\}, \qquad A = \{(1,2),\ (1,3),\ (2,4),\ (3,4)\}

has $4$ nodes and $4$ arcs. The arc $(1,2)$ points from node $1$ to node $2$ , while $(2,4)$ points from node $2$ to node $4$ .

We write $|N|$ for the number of nodes and $|A|$ for the number of arcs.