- Section 10.1: notions of graphs: directed and undirected, simple graphs, and multigraphs, etc.
- Section 10.2: degree of vertices and the handshake theorem, indegree and outdegree for directed graphs; special classes of graphs: complete graphs, hypercubes; Bipartite Graphs; Matchings in Bipartite graphs, and Halls Marriage Theorem
- Section 10.3: representing graphs: adjacency list and adjacency matrix representations of graphs, Isomorphism of graphs; using simple graph invariants to help determine non-isomorphism of graphs.
- Section 10.4: paths, simple paths, directed paths, circuits, simple circuits; Connectivity, connectedness in undirected graphs, strong connectedness in directed graphs;
- Section 10.5: Euler paths and circuits; Euler's theorem; Hamiltonian paths and circuits;
- Section 10.6: edge-weighted graphs; shortest paths; Dijkstra's single-source shortest path algorithm;
- Section 10.7: NOT COVERED.
- Section 10.8: Graph coloring, and the chromatic number of a graph, application (e.g., exam scheduling).

Informatics Forum, 10 Crichton Street, Edinburgh, EH8 9AB, Scotland, UK
Tel: +44 131 651 5661, Fax: +44 131 651 1426, E-mail: school-office@inf.ed.ac.uk Please contact our webadmin with any comments or corrections. Logging and Cookies Unless explicitly stated otherwise, all material is copyright © The University of Edinburgh |