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.