D1 Spanning trees 27/09/11

• Spanning trees
• Minimum spanning trees
• Kruskal's algorithm
• Prim's algorithm
• Using a distance matrix with Prim's algorithm

https://docs.google.com/viewer?a=v&pid=explorer&chrome=true&srcid=0B2J1T-insOmpOGIxMjFjOTYtNGE0NS00MDdlLTk3YTItZTI0MmY4NmNiZmQ0&hl=en_US

D1 More graphs 20/09/11

• Digraphs (directed graphs)
• Modelling situations with graphs
• Moving around graphs
• Defining path, cycle, tree
• Traversing graphs - Eulerian & Semi-Eulerian graphs
• Odd/even vertices

https://docs.google.com/viewer?a=v&pid=explorer&chrome=true&srcid=0B2J1T-insOmpNDQ1YjQwMWUtMDRlZi00ZjljLWIyZTUtMDhmY2U2ODAzNDY3&hl=en_US

D1 Introduction to graphs 13/09/11

• Defining terms relating to graphs
• - nodes, vertices, arcs, edges, isomorphic, connected, disconnected, complete
• - subgraph, loops, multiple edges, bipartite, complete bipartite, degrees
• Relationship between edges and sum of degrees
• Describing a graph using a vertex set and edge set
• Describing a graph using an adjacency matrix
• Network (weighted graph) and distance matrix

https://docs.google.com/viewer?a=v&pid=explorer&chrome=true&srcid=0B2J1T-insOmpMTY4ODQ1MmUtZjlmNi00MjQ2LWIxZDYtZWI2Y2JkMzAwMzk1&hl=en_US

• Homework set - revision of Algorithms (past exam questions)

https://docs.google.com/leaf?id=0B2J1T-insOmpZThkMWU2ZDItNGYyNC00ZWEwLThkYjEtMGY2NjliODc3NjM1&hl=en_US