IB Mathematics AI – Topic 3

Key Terms:

• Graph: A set of vertices (nodes) connected by edges (lines)
• Vertex (node): A point in the graph
• Edge: A line connecting two vertices
• Simple graph: No loops (edges from vertex to itself) and no multiple edges between same vertices
• Weighted graph: Edges have numerical values (weights) representing cost, distance, time, etc.
• Directed graph (digraph): Edges have direction (arrows)

Degree of a Vertex:

Number of edges connected to that vertex

Notation: deg(v) or degree of vertex v

Important Properties:

• Handshaking Lemma: Sum of all degrees = 2 × (number of edges)
• Connected graph: Path exists between any two vertices
• Complete graph: Every vertex connected to every other vertex
• Cycle: Closed path (starts and ends at same vertex)
• Tree: Connected graph with no cycles

Maximum Edges in Simple Graph:

For n vertices:

\[ \text{Maximum edges} = \binom{n}{2} = \frac{n(n-1)}{2} \]

⚠️ Common Pitfalls & Tips:

• Don't confuse vertices (points) with edges (connections)
• In weighted graphs, edge values matter for calculations
• Directed graphs: arrows show direction of travel
• Always check if graph is connected before applying algorithms

Definitions (in order of restrictiveness):

1. Walk:

A sequence of vertices where each adjacent pair is connected by an edge

Can repeat vertices and edges

2. Trail:

A walk with no repeated edges

Can repeat vertices but NOT edges

3. Path:

A trail with no repeated vertices

No repeated edges AND no repeated vertices

4. Circuit (Cycle):

A trail that starts and ends at the same vertex

Forms a closed loop

Summary Table:

⚠️ Common Pitfalls & Tips:

• Path is most restrictive - no repeats at all
• Trail allows repeated vertices but not edges
• Walk is least restrictive - anything goes
• Circuit = closed trail (starts and ends at same place)

Definitions:

Eulerian Circuit:

A trail that uses every edge exactly once and returns to starting vertex

Eulerian Trail:

A trail that uses every edge exactly once but doesn't return to start

Conditions for Eulerian Circuit:

A connected graph has an Eulerian circuit if and only if:

• ALL vertices have EVEN degree

Conditions for Eulerian Trail:

A connected graph has an Eulerian trail if and only if:

• EXACTLY TWO vertices have ODD degree
• Trail starts at one odd-degree vertex and ends at the other

Summary:

• 0 odd vertices → Eulerian circuit exists
• 2 odd vertices → Eulerian trail exists (but not circuit)
• More than 2 odd vertices → Neither exists

⚠️ Common Pitfalls & Tips:

• Count vertex degrees first - this tells you if Eulerian path exists
• Even degrees = circuit possible
• Two odd degrees = trail only (not circuit)
• More than 2 odd degrees = impossible

Definitions:

Hamiltonian Path:

A path that visits every vertex exactly once

Hamiltonian Cycle:

A cycle that visits every vertex exactly once and returns to start

Key Differences from Eulerian:

Important Note:

There is NO simple condition to determine if a Hamiltonian path/cycle exists

Must check by inspection or trial

⚠️ Common Pitfalls & Tips:

• Hamiltonian focuses on VERTICES, Eulerian on EDGES
• No degree-counting trick for Hamiltonian
• Must find path/cycle by trial or systematic search
• Used in Travelling Salesman Problem

Spanning Tree:

A subgraph that:

• Connects all vertices
• Contains no cycles
• Is a tree

Minimum Spanning Tree (MST):

A spanning tree with minimum total edge weight

For n vertices, MST has exactly (n - 1) edges

Kruskal's Algorithm:

1. Sort all edges by weight (smallest to largest)
2. Select smallest edge that doesn't create a cycle
3. Repeat until (n - 1) edges selected

Focus: Choose edges in order of weight

Prim's Algorithm:

1. Start at any vertex
2. Add smallest edge connecting a connected vertex to an unconnected vertex
3. Repeat until all vertices connected

Focus: Grow tree from one vertex

⚠️ Common Pitfalls & Tips:

• Kruskal: edges first (sort by weight)
• Prim: vertices first (grow from one point)
• Both give same total weight (may differ in edge selection)
• Must avoid cycles - check before adding edge

Solution:

Step 1: List edges in order of weight

AB(3), BC(4), AC(5), CD(6), BD(7), AD(8)

Step 2: Apply Kruskal's algorithm

Add AB(3): Connects A-B ✓

Add BC(4): Connects B-C, no cycle ✓

Add AC(5): Would create cycle A-B-C-A ✗ Skip

Add CD(6): Connects C-D, no cycle ✓

We now have 3 edges for 4 vertices → MST complete

Step 3: Calculate total weight

\[ \text{Total} = 3 + 4 + 6 = 13 \]

Answer: Order: AB, BC, CD. Total weight = 13

Problem Statement:

Find the shortest route that:

• Traverses every edge at least once
• Returns to the starting point
• Minimizes total distance

Solution Method:

Case 1: Graph has Eulerian circuit (all even degrees)

Solution = Total weight of all edges

No edges need to be repeated

Case 2: Graph has odd-degree vertices

1. Identify all odd-degree vertices
2. Find shortest paths between all pairs of odd vertices
3. Pair up odd vertices to minimize total repeated distance
4. Total = Sum of all edges + Sum of repeated edges

Formula:

\[ \text{Chinese Postman solution} = \sum \text{(all edges)} + \sum \text{(repeated edges)} \]

⚠️ Common Pitfalls & Tips:

• First check: count odd-degree vertices
• If all even degrees, just add all edge weights
• If odd vertices exist, must repeat some edges
• Pair odd vertices optimally to minimize repeats

Problem Statement:

Find the shortest route that:

• Visits every vertex exactly once
• Returns to the starting point
• Minimizes total distance

Finding Upper Bound:

Method 1: Nearest Neighbour Algorithm

1. Start at any vertex
2. Go to nearest unvisited vertex
3. Repeat until all visited
4. Return to start

Gives upper bound (may not be optimal)

Method 2: Use MST

1. Find MST using Kruskal's or Prim's
2. Double all edges in MST
3. Upper bound = 2 × (MST weight)

Finding Lower Bound:

Deleted Vertex Algorithm

1. Delete a vertex and its edges
2. Find MST of remaining graph
3. Add two smallest edges from deleted vertex
4. Lower bound = MST + two smallest edges

Result:

\[ \text{Lower bound} \leq \text{Optimal TSP} \leq \text{Upper bound} \]

⚠️ Common Pitfalls & Tips:

• TSP is about visiting VERTICES (Hamiltonian cycle)
• Nearest neighbour gives approximate solution quickly
• Use deleted vertex to find lower bound
• Try different starting vertices for better upper bound

Solution:

Step 1: Start at A

From A: nearest unvisited is B (distance 10)

Route so far: A → B (10)

Step 2: From B

From B: unvisited are C(12) and D(18)

Nearest is C (distance 12)

Route so far: A → B → C (22)

Step 3: From C

From C: only D unvisited (distance 14)

Route so far: A → B → C → D (36)

Step 4: Return to A

From D to A: distance 20

Complete cycle: A → B → C → D → A

Step 5: Calculate total

\[ \text{Total} = 10 + 12 + 14 + 20 = 56 \]

Answer: Upper bound = 56

Eulerian vs Hamiltonian

• Eulerian: Every EDGE once
• Hamiltonian: Every VERTEX once
• Different problems entirely!

Eulerian Test

• 0 odd vertices: Circuit exists
• 2 odd vertices: Trail only
• More than 2: Neither

MST Algorithms

• Kruskal: Sort edges first
• Prim: Grow from vertex
• Both give same total weight

Classic Problems

• Chinese Postman: All edges
• TSP: All vertices
• Know which is which!