Exploring and Travelling Revision Notes for VCE SSCE General Mathematics

Exploring and Travelling

Introduction to travelling problems

Graphs provide powerful tools for modelling and analysing travelling and exploring problems. These problems involve finding optimal routes between locations, such as minimising travel distance or time. Real-world examples include:

A courier planning the shortest delivery route
A tour guide finding the quickest path through multiple attractions without backtracking
A road inspector checking all roads in a region

To solve these problems, we need to understand different ways of navigating through graphs. Each type of movement has specific rules and properties.

infoNote

Graph theory transforms real-world navigation problems into mathematical models. By representing locations as vertices and connections as edges, we can systematically analyze and solve complex routing challenges.

Walks, trails, paths, circuits and cycles

When moving through a graph from one vertex to another, we can describe our journey in different ways. The graph below illustrates these concepts:

Walks

A walk represents a sequence of edges that connects successive vertices in a graph.

Walks have no restrictions - you can:

Start at any vertex and finish at any other vertex
Repeat edges as many times as you want
Visit the same vertex multiple times

The diagram below shows a walk traced in red:

This walk follows the route $A - C - A - D - G$ and demonstrates how edges and vertices can be repeated.

Trails

A trail is a walk where no edge is repeated.

Trails allow you to:

Visit vertices more than once
Never use the same edge twice

The diagram below shows a trail:

This trail follows the route $B - E - F - C - B - A$ . Notice that vertex $B$ appears twice, but no edge is used more than once.

Paths

A path is a walk where neither edges nor vertices are repeated.

Paths have the strictest rules:

Each edge is used at most once
Each vertex is visited at most once

The diagram below shows a path:

This path follows the route $A - D - C - F - E - B$ . No edges or vertices are repeated throughout the journey.

infoNote

Paths represent the most restrictive type of movement through a graph. Think of it as exploring a maze where you can never return to a previously visited location or retrace your steps along any corridor.

Circuits

A circuit is a trail that begins and ends at the same vertex. Circuits are also called closed trails.

Circuits must:

Start and finish at the same vertex
Not repeat any edges
May visit other vertices more than once

The diagram below shows a circuit:

This circuit follows the route $A - C - F - G - D - C - B - A$ . The journey starts and ends at vertex $A$ . While vertex $C$ is visited twice, no edge is repeated. The start and end vertex is necessarily repeated by the definition of a circuit.

Cycles

A cycle is a path that begins and ends at the same vertex. Cycles are also called closed paths.

Cycles must:

Start and finish at the same vertex
Not repeat any edges
Not repeat any vertices (except the start/end vertex)

The diagram below shows a cycle:

This cycle follows the route $F - E - B - C - F$ . The journey forms a closed loop with no repeated edges or vertices, except for the starting and ending point.

chatImportant

Key Distinction - Circuits vs Cycles:

A circuit is a closed trail - it can repeat vertices but not edges.

A cycle is a closed path - it cannot repeat vertices or edges (except returning to the start).

bookmarkSummary

Summary of Walk Types:

Walk: A sequence of edges linking successive vertices in a graph. No restrictions on repeating edges or vertices.
Trail: A walk with no repeated edges. Vertices may be repeated.
Path: A walk with no repeated edges and no repeated vertices.
Circuit: A trail that starts and ends at the same vertex. This is a closed trail.
Cycle: A path that starts and ends at the same vertex. This is a closed path.

lightbulbExample

Worked Example: Identifying Types of Walks

For each graph below, determine whether the traced route is a trail, path, circuit, cycle, or just a walk.

Solution:

Part a:

The route starts and ends at the same vertex, so it must be either a circuit or a cycle.

Examining the path, vertex $C$ is visited twice.

Since a vertex is repeated (but no edges are repeated), this is a circuit.

Part b:

The route starts and ends at the same vertex, so it must be either a circuit or a cycle.

Examining the path carefully, no vertices are repeated (except the start/end vertex) and no edges are repeated.

This is a cycle.

Part c:

The route starts at one vertex and ends at a different vertex, so it cannot be a circuit or cycle.

Checking for repeated elements, vertex $B$ appears twice in the route, but no edges are repeated.

Since there is one repeated vertex but no repeated edges, this is a trail.

Part d:

The route starts at one vertex and ends at a different vertex, so it cannot be a circuit or cycle.

Examining the path, both vertices $C$ and $E$ are repeated.

Additionally, the edge between $C$ and $E$ is used twice.

Since both vertices and edges are repeated, this is a walk only (not a trail, path, circuit, or cycle).

Eulerian trails and circuits

Special types of trails and circuits that cover every edge exactly once are called Eulerian trails and Eulerian circuits. These are named after the mathematician Leonhard Euler.

Why Eulerian trails and circuits matter

Eulerian trails and circuits have important real-world applications:

Mail delivery: A postal worker can plan a route that covers every street exactly once
Road inspection: Checking the condition of all roads without repeating any
Snow ploughing: Clearing all streets in a neighbourhood efficiently

In these situations, we represent towns as vertices and roads as edges. An Eulerian trail or circuit ensures every road is travelled exactly once.

Conditions for Eulerian trails

An Eulerian trail follows every edge of a connected graph exactly once.

chatImportant

Conditions for Eulerian Trail Existence:

An Eulerian trail will exist if and only if the graph satisfies these conditions:

The graph is connected
The graph has exactly zero or two vertices with odd degree

Starting and ending points:

If there are no odd-degree vertices, the Eulerian trail can start at any vertex and will end where it started (this is actually an Eulerian circuit)
If there are two odd-degree vertices, the Eulerian trail must start at one odd-degree vertex and finish at the other

Conditions for Eulerian circuits

An Eulerian circuit is an Eulerian trail that starts and ends at the same vertex.

chatImportant

Conditions for Eulerian Circuit Existence:

An Eulerian circuit will exist if and only if the graph satisfies these conditions:

The graph is connected
All vertices have even degree

An Eulerian circuit can start at any vertex in the graph.

infoNote

Important: If a graph has more than two odd-degree vertices, neither an Eulerian trail nor an Eulerian circuit exists.

Hamiltonian paths and cycles

While Eulerian trails focus on covering all edges, Hamiltonian paths and Hamiltonian cycles focus on visiting all vertices. These are named after mathematician William Rowan Hamilton.

Definitions

A Hamiltonian path visits every vertex of a graph exactly once.

A Hamiltonian cycle is a Hamiltonian path that starts and ends at the same vertex.

Real-world applications

Hamiltonian paths and cycles are useful when every vertex must be visited, but the specific route doesn't matter:

Message broadcasting: Ensuring every person in a network receives a message
Visiting multiple locations: A salesperson visiting all clients once
Tournament scheduling: Ensuring all teams play each other

How to identify Hamiltonian paths and cycles

Unlike Eulerian trails and circuits, there is no simple rule to determine if a Hamiltonian path or cycle exists. You must examine the graph through inspection.

chatImportant

Key Difference to Remember:

Memory aid: Eulerian refers to edges, and both words start with 'e'. Hamiltonian refers to vertices.

Eulerian trails and circuits: Do not repeat edges
Hamiltonian paths and cycles: Do not repeat vertices

lightbulbExample

Worked Example: Eulerian and Hamiltonian Travel

The map below shows several towns in the Yarra Valley region of Victoria: St Andrews, Kinglake, Yarra Glen, Toolangi, and Healesville.

Consider only the yellow routes shown. Note that St Andrews and Yarra Glen are connected, although this route is not fully visible in the image.

Part a: Draw a graph with vertices representing towns and edges representing direct road connections.

Part b: Explain why an Eulerian trail (but not an Eulerian circuit) is possible through this graph.

Part c: Write down an Eulerian trail beginning at Toolangi.

Part d: Write down a Hamiltonian cycle beginning at Healesville.

Solution:

Part a:

First, identify all direct road connections between towns:

St Andrews connects to Kinglake
St Andrews connects to Yarra Glen
Kinglake connects to Yarra Glen
Kinglake connects to Toolangi
Yarra Glen connects to Toolangi
Yarra Glen connects to Healesville
Healesville connects to Toolangi

The resulting graph is:

Part b:

To determine if an Eulerian trail or circuit exists, count the degree of each vertex:

St Andrews: degree $2$ (even)
Kinglake: degree $3$ (odd)
Yarra Glen: degree $4$ (even)
Toolangi: degree $3$ (odd)
Healesville: degree $2$ (even)

The graph is connected and has exactly two vertices with odd degree (Toolangi and Kinglake).

Therefore, an Eulerian trail exists (it will start at one odd-degree vertex and end at the other).

Since not all vertices have even degree, an Eulerian circuit does not exist.

Part c:

An Eulerian trail must start at one of the two odd-degree vertices. Starting at Toolangi (an odd-degree vertex), one possible Eulerian trail is:

$\text{Toolangi} - \text{Healesville} - \text{Yarra Glen} - \text{Toolangi} - \text{Kinglake} - \text{Yarra Glen} - \text{St Andrews} - \text{Kinglake}$

This trail covers every edge exactly once and ends at the other odd-degree vertex (Kinglake).

Part d:

A Hamiltonian cycle must visit every vertex exactly once before returning to the start. Beginning at Healesville, one possible Hamiltonian cycle is:

$\text{Healesville} - \text{Yarra Glen} - \text{St Andrews} - \text{Kinglake} - \text{Toolangi} - \text{Healesville}$

This cycle visits all five towns exactly once before returning to Healesville.

bookmarkSummary

Key Points to Remember:

A walk is any sequence of edges connecting vertices. Edges and vertices can be repeated freely.
A trail is a walk where no edge is repeated, but vertices may be repeated.
A path is a walk where neither edges nor vertices are repeated.
A circuit is a trail that starts and ends at the same vertex (a closed trail).
A cycle is a path that starts and ends at the same vertex (a closed path).
Eulerian trails exist in connected graphs with exactly zero or two odd-degree vertices. They cover every edge exactly once.
Eulerian circuits exist in connected graphs where all vertices have even degree. They cover every edge exactly once and return to the start.
Hamiltonian paths visit every vertex exactly once. Hamiltonian cycles visit every vertex exactly once and return to the start. There is no simple rule to identify them - you must inspect the graph.
Memory aid: Eulerian refers to edges (both start with 'e'), while Hamiltonian refers to vertices (no repeated vertices).

Exploring and Travelling (VCE SSCE General Mathematics): Revision Notes