International Baccalaureate · MYP 5 Extended

Networks

⌚ ~98 min ▢ 10 blocks ✓ 50 exercises

I Describing Graphs and Networks

Graphs are used to show how things are connected. They can be used to help solve problems in train scheduling, traffic flow, bed usage in hospitals, and project management.
The theory of graphs was developed centuries ago, but the application of the theoretical ideas is relatively recent. Real progress was made during and after the Second World War as mathematicians, industrial technicians, and members of the armed services worked together to improve military operations.

Report an error

Definition — Graph

A graph (or network) is a structure which shows the physical connections or relationships between things of interest.
The things of interest are represented by vertices (singular: vertex), also called nodes or points.
The connections or relationships are represented by edges, also called lines.
The number of vertices of a graph is called the order of the graph.

Example

This graph shows road connections between several towns. We can see that towns A and B are directly connected, but towns A and C are not.

Definition — Degree of a Vertex

The degree of a vertex, denoted $\deg(v)$, is the number of edges connected to it.
If a loop exists (an edge connecting a vertex to itself), it contributes 2 to the degree of that vertex.

Example

For vertex A: It has one connection to B and one connection to D. $\deg(A) =2 $.

Proposition — Handshaking Lemma

In any graph, the sum of the degrees of all the vertices equals twice the number of edges: $$\sum_{v} \deg(v) = 2 \times (\text{number of edges}).$$ As a consequence, the number of vertices of odd degree is always even.

Proof

Each edge has two endpoints, so it contributes $1$ to the degree of each of them, that is $2$ in total to the sum of all the degrees (a loop contributes $2$ to the degree of its single vertex, which is again $2$). Summing over all the edges gives $\sum_v \deg(v) = 2 \times (\text{number of edges})$, an even number. Since the degrees of the even-degree vertices already sum to an even number, the degrees of the odd-degree vertices must also sum to an even number, which forces their count to be even.

Definition — Undirected Graph

In an undirected graph, movement is allowed in either direction along the edges. The relationship is symmetric.

Adjacent vertices are vertices connected by an edge.
Adjacent edges are edges which share a common vertex.

Example

In this graph, A is connected to B and B is connected to A.

Definition — Directed Graph

A directed graph (or digraph) contains arrows indicating the direction in which we can move along the arcs.

The in-degree is the number of arcs coming into the vertex.
The out-degree is the number of arcs going out from the vertex.

A loop (an arc from a vertex to itself) counts once in the in-degree and once in the out-degree of that vertex.

Example

In this graph, there is an arc from A to B, but no arc from B to A.

Definition — Subgraph

A subgraph is a graph that is made from a subset of the vertices and edges of another graph.

Example

Consider the original graph $G$. We can create a subgraph $H$ by selecting only a subset of the vertices (for example, removing vertex C) and only a subset of the edges.

Graph $G$	Subgraph $H$

Definition — Simple Graph

A graph is called simple if it contains no loops and if there is a maximum of one edge joining any pair of distinct vertices.

Example

Simple Graph	Not Simple (loop)	Not Simple (double edges)

Definition — Complete Graph

A complete graph is a simple undirected graph in which every vertex is connected by an edge to every other vertex.
The notation $K_n$ is used to describe the complete graph with $n$ vertices.

Example

This is $K_4$. It has 4 vertices and 6 edges.

Skills to practice

Counting Degrees and Edges
Modelling and Reasoning with Graphs

II Walking through a Graph

Definition — Walk, Trail, Path, Circuit and Cycle

A walk is a sequence of vertices such that each successive pair is adjacent.
A trail is a walk in which no edge is repeated.
A path is a walk in which no vertex is repeated.
A circuit is a trail that starts and ends at the same vertex (a closed trail).
A cycle is a circuit in which no vertex is repeated except the first, which is also the last.

Example

In this graph:

$A\rightarrow B\rightarrow C$ is a walk because there is an edge between $A$ and $B$ and an edge between $B$ and $C$.
$A\rightarrow B\rightarrow A$ is not a trail because the edge between $A$ and $B$ is repeated.
$A\rightarrow B\rightarrow C\rightarrow D\rightarrow A$ is not a path because the vertex $A$ is repeated.
$A\rightarrow B\rightarrow C\rightarrow D\rightarrow A$ is a circuit (and a cycle).

Definition — Connected Graph

A graph is called connected if it is possible to travel from any vertex to any other vertex via a sequence of edges.
The separate pieces of a graph that is not connected are its connected components.

Example

Connected	Disconnected

In the graph on the right, there is no way from the left pair of vertices to the right pair: it has two connected components.

Definition — Strongly Connected Graph

A directed graph is strongly connected if it is possible to travel from any vertex to any other vertex by following the directions of the arcs.
For undirected graphs, being connected is enough; strong connectivity is the directed analogue.

Example

Strongly connected	Not strongly connected

In the digraph on the left, the arcs form the cycle $A \to B \to C \to A$, so every vertex can be reached from every other vertex: it is strongly connected.
In the digraph on the right, we can reach $C$ from $A$, but no arc leaves $C$, so there is no walk from $C$ back to $A$: it is not strongly connected.

Skills to practice

Classifying Sequences of Vertices
Identifying Graph Properties
Identifying Paths and Studying Connectedness

III Finding Shortest Paths

Definition — Weighted Graph

A weighted graph has numbers assigned to its edges. These numbers may represent the cost, time, or distance.

Example

The weight of edge AD is 15.

Definition — Weight of a Path and Shortest Path

In a weighted graph, the weight of a path is the sum of the weights of its edges. A shortest path (also called a shortest route) between two vertices is a path of least weight between them, and its weight is the distance between the two vertices. When the weights are positive, a walk of least weight never passes twice through the same vertex, so it is a path. Two vertices may be joined by several shortest paths.

Method — Finding a Shortest Path by Labelling (Dijkstra's Algorithm)

In a weighted graph whose weights are all positive, each vertex receives a label: the weight of the shortest path from the start found so far, with the vertex it comes from.

Start: give the start the label $0$ and every other vertex the label $\infty$ (not reached yet).
Fix the smallest label: among the vertices not yet fixed, fix the one with the smallest label. Its label is final: it is the distance from the start.
Update its neighbours: for each neighbour $V$, not yet fixed, of the vertex $U$ just fixed, compute the label of $U$ plus the weight of the edge $UV$. If this number is smaller than the label of $V$, it becomes the new label of $V$, and $U$ is written beside it.
Repeat steps 2 and 3 until the destination is fixed. If every vertex not yet fixed has the label $\infty$, stop: those vertices, the destination among them, cannot be reached from the start.
Read the path backwards: from the destination, go to the vertex written beside its label, then to the vertex written beside that one, and so on back to the start.

A fixed label is never improved later: any other path to that vertex leaves the fixed vertices through a vertex whose label is at least as large, and the positive weights can only add to it.

Example

The weighted graph below gives the travel times, in minutes, between six places. Use the labelling method to find a shortest path from $S$ to $T$ and its weight.

Answer

Each row gives the labels after the update of that step, the vertex written in brackets being the one each label comes from; a fixed label is in bold, and a fixed vertex is not updated again.

Step	$S$	$A$	$B$	$C$	$D$	$T$	Fixed
$0$	$\mathbf{0}$	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$	$S$
$1$		$4\ (S)$	$\mathbf{2}\ (S)$	$\infty$	$\infty$	$\infty$	$B$
$2$		$\mathbf{3}\ (B)$		$10\ (B)$	$12\ (B)$	$\infty$	$A$
$3$				$\mathbf{8}\ (A)$	$12\ (B)$	$\infty$	$C$
$4$					$\mathbf{10}\ (C)$	$14\ (C)$	$D$
$5$						$\mathbf{13}\ (D)$	$T$

Two updates carry the idea of the method. At step $2$, the label $4$ of $A$, the weight of the direct edge $SA$, is replaced by $3$: going round through $B$ costs $2 + 1 = 3$. At step $4$, the label $12$ of $D$ is replaced by $8 + 2 = 10$, through $C$. A direct edge is not always a shortest path. Reading the path backwards from $T$: $T$ comes from $D$, $D$ from $C$, $C$ from $A$, $A$ from $B$, $B$ from $S$. A shortest path is $$S \to B \to A \to C \to D \to T, \quad\text{of weight } 2 + 1 + 5 + 2 + 3 = \textcolor{colorprop}{13} \text{ minutes}.$$

Skills to practice

Analysing Paths in Weighted Graphs
Finding Shortest Paths by Labelling

IV Finding Eulerian Trails and Circuits

Discover The Bridges of Königsberg

In the eighteenth century, the town of Königsberg had four districts, $A$, $B$, $C$ and $D$, separated by the branches of a river and joined by seven bridges, as on the map below. Its inhabitants wondered whether a walk could cross each of the seven bridges exactly once.

Represent the situation by a graph: one vertex for each district, one edge for each bridge.
Find the degree of each vertex.
Each time the walk enters a district and leaves it again, it uses two of its bridges. Explain why such a walk is impossible.

Answer

The graph has the four vertices $A$, $B$, $C$, $D$ and seven edges, two of them between $A$ and $B$ and two between $A$ and $C$:
$\deg(A) = 5$, $\deg(B) = 3$, $\deg(C) = 3$ and $\deg(D) = 3$ (their sum, $14$, is twice the number of bridges, $7$).
In a district where the walk neither starts nor ends, the walk leaves as many times as it arrives, so the bridges of that district are used in pairs: its degree must be even. Only the start and the end of the walk can have an odd degree, so at most two vertices can be odd. Here all four vertices are odd: no walk crosses every bridge exactly once, as Leonhard Euler showed in 1736. The definitions and the theorem below turn this argument into a rule.

Definition — Eulerian Graphs

An Eulerian circuit is a trail which traverses every edge of the graph exactly once and starts and ends at the same vertex.
An Eulerian trail traverses every edge exactly once but starts and ends at different vertices.

Proposition — Conditions for Eulerian Graphs

A connected undirected graph has an Eulerian circuit if and only if every vertex has an even degree.
A connected undirected graph has an Eulerian trail if and only if it has exactly two vertices of odd degree.

Proof

The degrees are necessary. Follow an Eulerian circuit. Each time it passes through a vertex, it arrives along one edge and leaves along another; at the vertex where it starts and ends, the first edge and the last edge form one more such pair. The circuit uses every edge exactly once, so the edges at each vertex are grouped in pairs: every degree is even. For an Eulerian trail, the same pairing works at every vertex except the start, whose first edge is alone, and the end, whose last edge is alone; the start and the end are different, so exactly these two vertices have an odd degree. The degrees are sufficient for a circuit. Let the graph be connected, with every degree even. Start at any vertex $A$ that has an edge, and walk along edges not yet used, as long as possible. The walk can only stop at $A$: each time it enters another vertex, it has used an odd number of the edges at that vertex (two at each earlier passage, one now), and the degree is even, so an unused edge remains to leave by. The walk is therefore a circuit $C$ (a trail that ends where it starts). If $C$ uses every edge, it is an Eulerian circuit. Otherwise some vertex $B$ of $C$ still has an unused edge. Indeed, take an unused edge: if one of its ends lies on $C$, that end will do; if not, the graph being connected, a path joins one of its ends to $A$, and the first edge of that path with one end on $C$ and the other end off $C$ is unused (an edge of $C$ has both ends on $C$), and it touches $C$. At each vertex, $C$ uses an even number of edges, so among the unused edges every degree is still even: a walk from $B$ along unused edges closes at $B$, giving a circuit $C'$. Inserting $C'$ into $C$ at $B$ gives a longer circuit. Repeating, the number of edges used grows each time, and the graph has finitely many edges: the process ends with a circuit that uses every edge, an Eulerian circuit. The degrees are sufficient for a trail. Let the graph be connected with exactly two vertices of odd degree, $P$ and $Q$. Add a new vertex $X$ joined to $P$ and to $Q$. The new graph is connected, and every degree is even ($P$ and $Q$ gain one, $X$ has degree $2$), so it has an Eulerian circuit, which may be started at $X$: it reads $X \to P \to \cdots \to Q \to X$ or the reverse. Removing $X$ and its two edges leaves a trail from $P$ to $Q$ that uses every edge of the original graph exactly once: an Eulerian trail.

Example

Consider the following undirected graph (a “bowtie” shape).

The degrees of the vertices (the number of edges connected to each) are:

$\deg(A) = 2$
$\deg(B) = 2$
$\deg(C) = 4$ (connected to A, B, D, E)
$\deg(D) = 2$
$\deg(E) = 2$

Since the graph is connected and all vertices have an even degree, the graph contains an Eulerian circuit.
One possible circuit is: $C \to A \to B \to C \to D \to E \to C$.

The Chinese Postman Problem was posed by the mathematician Kwan Mei-Ko. The problem asks: how can a postman deliver mail along every road in a network and return to the depot travelling the minimum possible distance?
Mathematically, this means traversing every edge of a weighted graph at least once and returning to the start.

Report an error

Skills to practice

Identifying Eulerian Circuits and Trails

V Going further

Skills to practice

Solving Network Problems in Context
Investigating Patterns in Networks
Quiz

Step	\(S\)	\(A\)	\(B\)	\(C\)	\(D\)	\(T\)	Fixed
\(0\)	\(\mathbf{0}\)	\(\infty\)	\(\infty\)	\(\infty\)	\(\infty\)	\(\infty\)	\(S\)
\(1\)		\(4\ (S)\)	\(\mathbf{2}\ (S)\)	\(\infty\)	\(\infty\)	\(\infty\)	\(B\)
\(2\)		\(\mathbf{3}\ (B)\)		\(10\ (B)\)	\(12\ (B)\)	\(\infty\)	\(A\)
\(3\)				\(\mathbf{8}\ (A)\)	\(12\ (B)\)	\(\infty\)	\(C\)
\(4\)					\(\mathbf{10}\ (C)\)	\(14\ (C)\)	\(D\)
\(5\)						\(\mathbf{13}\ (D)\)	\(T\)

Graph \(G\)	Subgraph \(H\)