Travelling a Network Revision Notes for HSC SSCE Mathematics Standard

Travelling a Network

Introduction to travelling networks

When working with networks and graphs, we often need to find routes between different locations. Think of this like finding your way through a park or navigating city streets. Understanding the different ways to travel through a network helps us solve practical problems involving travel routes, delivery paths, and navigation.

infoNote

A network consists of two fundamental components:

Vertices: The points or locations in the network (shown as dots or labeled points)
Edges: The connections between vertices (shown as lines)

When we move through a network, we can travel in different ways depending on whether we allow repeated edges or repeated vertices. Let's explore the five main types of routes.

Types of routes

Walk

A walk is the most flexible type of route through a network.

Definition: A walk is a connected sequence of edges showing a route between vertices. Both edges and vertices may be visited multiple times.

Key features:

Can repeat edges
Can repeat vertices
Simply needs to show a connected path from one location to another

lightbulbExample

Worked Example: Identifying a Walk

In the forest network below, the walk $G1-B-F-G2-T-G2-F$ starts at gate 1, travels through various locations, and visits gate 2 twice.

Notice how this route revisits both gate 2 and uses the path between gate 2 and the fern gully twice. This is perfectly acceptable in a walk.

Trail

A trail is more restricted than a walk.

Definition: A trail is a walk with no repeated edges.

Key features:

Cannot repeat edges
Can repeat vertices
Each connection can only be used once

lightbulbExample

Worked Example: Identifying a Trail

The trail $G1-B-F-G2-T-W-B-G2$ shows a route through the forest where no edge is used twice.

Even though the bridge $(B)$ and gate 2 $(G2)$ are visited twice, this is still a trail because no edge is repeated.

Path

A path is even more restrictive.

Definition: A path is a walk with no repeated vertices.

Key features:

Cannot repeat vertices
Cannot repeat edges (this follows automatically from not repeating vertices)
Each location is visited exactly once

chatImportant

Important distinction:

Open path: Starts and finishes at different vertices
Closed path: Starts and finishes at the same vertex (also called a circuit)

lightbulbExample

Worked Example: Identifying a Path

The path $G1-F-B-W-T-G2$ shows a route where each location is visited only once.

Notice that because we don't repeat any vertices, we automatically don't repeat any edges either.

Circuit

A circuit is a special type of closed trail.

Definition: A circuit is a walk with no repeated edges that starts and ends at the same vertex.

Key features:

Starts and ends at the same vertex (closed route)
Cannot repeat edges
Can repeat vertices (except the start/end vertex which is naturally visited twice)
Also called a closed trail

lightbulbExample

Worked Example: Identifying a Circuit

The circuit $G1-F-B-W-T-G2-B-G1$ starts at gate 1 and returns to gate 1.

The bridge $(B)$ is visited twice, but this is allowed in a circuit. No edge is used twice.

Cycle

A cycle is the most restrictive type of closed route.

Definition: A cycle is a walk with no repeated vertices that starts and ends at the same vertex.

Key features:

Starts and ends at the same vertex (closed route)
Cannot repeat vertices (except the start/end vertex)
Cannot repeat edges (this follows from not repeating vertices)
Also called a closed path

lightbulbExample

Worked Example: Identifying a Cycle

The cycle $G2-B-W-T-G2$ starts and ends at gate 2.

Apart from gate 2 being the start and end point, no other vertex is repeated. This makes it a cycle.

Comparing route types

Here's a helpful summary table showing what's allowed for each route type:

Type of route	Are repeated edges permitted?	Are repeated vertices permitted?
Walk	Yes	Yes
Trail	No	Yes
Path	No	No
Circuit	No	Yes
Cycle	No	No (except first and last)

bookmarkSummary

Key Relationships to Remember:

All trails, paths, circuits, and cycles are types of walks
A path is more restrictive than a trail
A cycle is more restrictive than a circuit
Circuits and cycles are "closed" versions (same start and end vertex)

Worked example: identifying route types

Let's practice identifying different types of routes. For each graph below, we need to identify whether the route shown is a trail, path, circuit, cycle, or walk only.

lightbulbExample

Worked Example: Classifying Different Route Types

Graph a:

Starts and ends at the same vertex (so could be circuit or cycle)
No repeated edges
Vertex $C$ is visited twice
Answer: Circuit (repeated vertex means it cannot be a cycle)

Graph b:

Starts and ends at the same vertex (so could be circuit or cycle)
No repeated edges
No repeated vertices
Answer: Cycle (no repeated vertices makes this a cycle, not just a circuit)

Graph c:

Starts at one vertex, ends at a different vertex (so not circuit or cycle)
Repeated vertex $(B)$ but no repeated edges
Answer: Trail (no repeated edges means it's a trail, not just a walk)

Graph d:

Starts at one vertex, ends at a different vertex (so not circuit or cycle)
Has repeated vertices $(C$ and $E)$
Has repeated edges (the edge between $C$ and $E$ is used twice)
Answer: Walk only (repeated edges mean it cannot be a trail, path, circuit, or cycle)

Traversable graphs

Some graphs have a special property called traversability.

Definition: A traversable graph has a trail that includes every edge. You can trace the entire graph without repeating any edge or lifting your pen from the paper.

Example of a traversable graph

The graph on the left is traversable. The trail $A-B-C-A-C$ visits every edge exactly once. Notice how we can draw this path without lifting our pen and without going over the same edge twice.

Example of a non-traversable graph

The graph on the right (a complete square with diagonals) is not traversable. It's impossible to find a trail that includes every edge without repeating at least one edge.

infoNote

Why this matters: Traversable graphs are important for real-world problems like:

Planning delivery routes
Designing street sweeping paths
Creating inspection routes that cover every connection once

Remember!

bookmarkSummary

Key Points to Remember:

Walk: The most general route - allows repeated edges and vertices
Trail: No repeated edges, but vertices can repeat
Path: No repeated vertices (which means no repeated edges either)
Circuit: A closed trail - starts and ends at same vertex with no repeated edges
Cycle: A closed path - starts and ends at same vertex with no repeated vertices
A traversable graph has a trail that includes every edge exactly once
When identifying routes, first check if it's closed (same start/end), then check for repeated edges and vertices

Travelling a Network (HSC SSCE Mathematics Standard): Revision Notes