HL AI – Graph Theory

Definitions

Adjacency Matrices

Hamilton Graphs

Graphs

Trees

Graph review

Routes

Eulerian Graphs

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.