5Network problems
IB Optimisation
5.1 Definitions
We are going to look into several problems that involve graphs. Unsurprisingly,
we will need some definitions from graph theory.
Definition
(Directed graph/network)
.
A directed graph or network is a pair
G
= (
V, E
), where
V
is the set of vertices and
E ⊆ V × V
is the set of edges. If
(u, v) ∈ E, we say there is an edge from u to v.
Definition
(Degree)
.
The degree of a vertex
u ∈ V
is the number of
v ∈ V
such that (u, v) ∈ E or (v, u) ∈ E.
Definition
(Walk)
.
An walk from
u ∈ V
to
v ∈ V
is a sequence of vertices
u
=
v
1
, · · · , v
k
=
v
such that (
v
i
, v
i+1
)
∈ E
for all
i
. An undirected walk allows
(v
i
, v
i+1
) ∈ E or (v
i+1
, v) ∈ E, i.e. we are allowed to walk backwards.
Definition (Path). A path is a walk where v
1
, · · · , v
k
are pairwise distinct.
Definition
(Cycle)
.
A cycle is a walk where
v
1
, · · · , v
k−1
are pairwise distinct
and v
1
= v
k
.
Definition
(Connected graph)
.
A graph is connected if for any pair of vertices,
there is an undirected path between them.
Definition (Tree). A tree is a connected graph without (undirected) cycles.
Definition
(Spanning tree)
.
The spanning tree of a graph
G
= (
V, E
) is a tree
(V
0
, E
0
) with V
0
= V and E
0
⊆ E.