Overview Revision Notes for Leaving Cert Applied Maths

Overview

Networks and graphs are fundamental mathematical structures that help us model and solve real-world problems involving connections and relationships. This topic covers the essential vocabulary, matrix representations, and key algorithms needed to work with these important mathematical tools.

Basic terminology

Understanding the fundamental language of graph theory is essential for working with networks effectively. Let's start with the building blocks of any graph.

Graphs and their components

A graph consists of points called nodes (also known as vertices) that are connected by lines called edges (sometimes called arcs). Think of nodes as locations on a map and edges as the roads connecting them.

infoNote

The terms "nodes" and "vertices" are used interchangeably in graph theory, as are "edges" and "arcs". Different textbooks may prefer different terminology, but they refer to the same concepts.

Degree and valency

The degree (or valency) of a vertex tells us how many edges meet at that particular node. For example, if a node has three edges connected to it, its degree is 3. This concept is crucial for understanding how well-connected different parts of a network are.

Weighted graphs and direction

Sometimes edges can be assigned numerical values called weights, which might represent distances, costs, or other measurable quantities. When edges have arrows showing a specific direction of travel, we call this a directed graph or digraph.

Walks, paths and cycles

These terms describe different ways of moving through a graph:

A walk of length $n$ involves moving along $n$ edges, where you can revisit the same nodes multiple times
A path is a special type of walk where all nodes visited are different (no backtracking)
A cycle is a path that starts and ends at the same vertex, forming a loop

chatImportant

Hand-shaking lemma

This important principle states that the sum of all degrees in a graph equals twice the number of edges. Mathematically: $\sum \text{degrees} = 2 \times \text{number of edges}$

This makes sense because each edge contributes 1 to the degree of each of its two endpoints.

Matrix operations in graph theory

Matrices provide a powerful way to represent and analyse graphs mathematically. Understanding basic matrix operations is essential for working with graph representations.

Addition and subtraction

When adding or subtracting matrices, we combine corresponding elements. For $2 \times 2$ matrices, we add each position separately. The same principle applies to larger matrices - we work element by element in corresponding positions.

lightbulbExample

Worked Example: Matrix Addition

For matrices $A = \begin{pmatrix} 1 & 2 \ 3 & 4 \end{pmatrix}$ and $B = \begin{pmatrix} 5 & 6 \ 7 & 8 \end{pmatrix}$ :

$A + B = \begin{pmatrix} 1+5 & 2+6 \ 3+7 & 4+8 \end{pmatrix} = \begin{pmatrix} 6 & 8 \ 10 & 12 \end{pmatrix}$

Multiplication

Matrix multiplication is more complex than addition. For $2 \times 2$ matrices, each element in the result comes from multiplying rows of the first matrix with columns of the second matrix. This operation is fundamental for analysing paths and connections in graphs.

lightbulbExample

Worked Example: Matrix Multiplication

For matrices $A = \begin{pmatrix} 1 & 2 \ 3 & 4 \end{pmatrix}$ and $B = \begin{pmatrix} 5 & 6 \ 7 & 8 \end{pmatrix}$ :

$A \times B = \begin{pmatrix} (1×5 + 2×7) & (1×6 + 2×8) \ (3×5 + 4×7) & (3×6 + 4×8) \end{pmatrix} = \begin{pmatrix} 19 & 22 \ 43 & 50 \end{pmatrix}$

Adjacency matrices

An adjacency matrix uses numbers (typically 0s and 1s) to represent which nodes in a graph are directly connected to each other.

Reading adjacency matrices

We read adjacency matrices from left to top, similar to reading coordinates. A '1' in position $(i,j)$ means there's an edge from node $i$ to node $j$ , while a '0' means no direct connection exists.

Properties of adjacency matrices

For directed graphs (digraphs), the adjacency matrix may not be symmetrical because connections might only go one way. This is different from undirected graphs where connections work both ways.

chatImportant

Powers of adjacency matrices

A remarkable property is that when $M$ is an adjacency matrix, $M^n$ gives us the number of walks of length n between any two nodes in the network. This allows us to count indirect connections and analyse network connectivity.

This means $M^2$ shows 2-step connections, $M^3$ shows 3-step connections, and so on.

Trees and spanning trees

Trees are special types of graphs with unique properties that make them extremely useful for optimisation problems.

What makes a tree

A tree is a connected graph that contains no cycles. This means you can travel between any two nodes, but there's exactly one path connecting them - no alternative routes exist.

infoNote

Trees have several equivalent defining properties:

Connected with no cycles
Connected with exactly $n-1$ edges for $n$ vertices
Any two vertices are connected by exactly one path
Connected, but removing any edge disconnects the graph

Spanning trees

A spanning tree of a graph $P$ is a subgraph that includes all the vertices from P and forms a tree structure. It's like finding the minimum road network needed to connect all towns without creating any circular routes.

Minimum spanning trees

For weighted graphs, a minimum spanning tree is the spanning tree where the total weight of all edges is as small as possible. This is incredibly useful for problems like designing efficient transportation networks or minimising costs.

Algorithms for minimum spanning trees

Two main algorithms help us find minimum spanning trees efficiently. Both algorithms are guaranteed to find the optimal solution.

Prim's algorithm

This algorithm builds the minimum spanning tree gradually:

lightbulbExample

Worked Example: Prim's Algorithm Steps

Step 1: Start at any node in the graph Step 2: Choose the edge with the smallest weight that connects to a new node Step 3: Continue choosing the smallest weight edges that add new nodes without creating cycles Step 4: Stop when all nodes are included

Prim's algorithm can be implemented using distance matrices, making it practical for computational applications.

Kruskal's algorithm

This algorithm takes a different approach:

lightbulbExample

Worked Example: Kruskal's Algorithm Steps

Step 1: List all edges in order from smallest to largest weight Step 2: Select edges one by one, starting with the smallest Step 3: Only include an edge if it doesn't create a cycle Step 4: Continue until you have a spanning tree

The key difference is that Kruskal's algorithm considers all edges globally, while Prim's algorithm builds locally from a starting point.

infoNote

Exam tips

Always check your matrix dimensions before performing operations
When drawing adjacency matrices, double-check that directed graphs may not be symmetrical
For minimum spanning tree problems, clearly show your working by listing edge weights and explaining why you accept or reject each edge
Remember that both Prim's and Kruskal's algorithms will give you the same minimum weight, though the actual tree structure might differ if multiple solutions exist

bookmarkSummary

Key Points to Remember:

Graphs consist of nodes (vertices) connected by edges (arcs)
The hand-shaking lemma states that the sum of all degrees equals twice the number of edges
Adjacency matrices represent graph connections using 0s and 1s, and $M^n$ counts walks of length $n$
Trees are connected graphs with no cycles, and spanning trees connect all vertices with minimum edges
Both Prim's and Kruskal's algorithms find minimum spanning trees but use different approaches - Prim's builds locally, Kruskal's considers all edges globally

Overview (Leaving Cert Applied Maths): Revision Notes

Overview

Basic terminology

Matrix operations in graph theory

Adjacency matrices

Trees and spanning trees

Algorithms for minimum spanning trees

Explore Leaving Cert Applied Maths Model Answers by Topics

Real-World Applications

Networks & Graphs

Explore Leaving Cert Applied Maths Quizzes by Topics

Real-World Applications

Networks & Graphs

Explore Leaving Cert Applied Maths Flashcards by Topics

Real-World Applications

Networks & Graphs

Join 100,000+ Leaving Cert students studying Revision Notes with us.