Prerequisites & Notation

Before You Begin

This chapter moves from single-hop to multi-hop communication. The setting is noiseless networks, so the focus is on graph theory and algebraic coding rather than probabilistic arguments. We assume the following background.

Basic graph theory: directed graphs, paths, cuts
Self-check: Can you define a directed graph, a path from source to sink, and a cut separating source from sink?
Finite fields: $\mathbb{F}_q$ , addition and multiplication
Self-check: Can you perform arithmetic in $\mathbb{F}_2$ (binary XOR) and $\mathbb{F}_4$ ?
Linear algebra over finite fields
Self-check: Can you determine the rank of a matrix over $\mathbb{F}_q$ and solve a linear system?
Channel capacity and the coding theorem (for context)(Review ch09)
Self-check: Can you explain why channel coding matters — what does reliable communication over a noisy channel require?
Entropy and mutual information (for rate bounds)(Review ch01)
Self-check: Can you state the chain rule for entropy and the data processing inequality?

Notation for This Chapter

This chapter uses graph-theoretic notation alongside information-theoretic symbols.

Symbol	Meaning	Introduced
$G = (V, E)$	Directed graph with vertex set $V$ and edge set $E$	s01
$s$	Source node	s01
$t$ (or $t_1, \ldots, t_K$ )$	Sink node(s) / destination(s)	s01
$c(e)$	Capacity of edge $e$ (integer, in symbols per time unit)	s01
$\text{maxflow}(s, t)$	Maximum flow from $s$ to $t$	s01
$\text{mincut}(s, t)$	Minimum cut capacity separating $s$ from $t$	s01
$\mathbb{F}_q$	Finite field with $q$ elements	s02
$\mathbf{M}$	Transfer matrix of a linear network code	s02
$h$	Multicast rate (symbols per time unit to each sink)	s02

← Ch 20 Max-Flow Min-Cut for Single Unicast