# 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. |