IB Maths AI 3.13 Definitions
This page contains our IB Maths AI definitions for 3.13. By learning each one of these definitions, you will fully cover the content for IB Maths AI 'Algorithms & problems'.
HL
Chinese postman problem
Finding the shortest closed route that uses every edge of a weighted graph at least once.
HL
deleted vertex algorithm
Produces a lower bound for the travelling salesman problem by deleting one vertex, finding a minimum spanning tree on the remaining vertices, then adding the two smallest edges that connect the deleted vertex to the tree.
HL
Eulerian circuit
A walk that uses every edge exactly once and starts and ends at the same vertex.
HL
Eulerian trail
A walk that uses every edge exactly once.
HL
Hamiltonian cycle
A path that visits every vertex exactly once and returns to the starting vertex.
HL
Hamiltonian path
A path that visits every vertex exactly once.
HL
Kruskal’s algorithm
Finds a minimum spanning tree by adding edges in increasing weight order, skipping any edge that would create a cycle, until all vertices are connected.
HL
minimum spanning tree
A spanning tree with the smallest possible total weight.
HL
nearest neighbour algorithm
Produces a travelling salesman tour by repeatedly going to the nearest unvisited vertex and then returning to the start, giving an upper bound for the optimum tour.
HL
Prim’s algorithm
Finds a minimum spanning tree by starting at a vertex and repeatedly adding the smallest edge that connects the current tree to a new vertex, until all vertices are included.
Next Up
You have completed the topic 3 definitions for IB Maths AI - continue with related resources below or explore the full IB Maths AI course from the IBO.
Other topic 3 resources