HL AI – Graph Theory

Definitions

Hamilton Graphs

Adjacency Matrices

Graphs

Spanning Trees

Graph review

Eulerian Graphs

Travelling Salesman

Traffic Light Coding for Unit

Make your own copy and share with your students.

Learning Outcomes
Definitions of graphs: vertices, edges, degree, adjacency.
Draw and understand simple graphs, weighted graphs and connected graphs.
Draw and understand trees, subgraphs, directed graphs, degree in and degree out graphs.
Understand walks, trials, paths and circuits.
Understand Eulerian trails and circuits.
Understand Hamiltonian paths and cycles.
Use and understand the minimum spanning tree, including Kruskal’s and Prim’s algorithms.
Solve Chinese Postman Problems (Eulerian).
Using the nearest neighbour algorithm.
Using vertex deletion to find lower bounds for the travelling salesman problem (Hamiltonian).
Adjacency matrices for walks and graphs.
Using weighted adjacency tables for construction of transition matrices.