# DMMR: Study guide for Chapter 10 of the textbook by K. Rosen

## STUDY ALL SECTIONS EXCEPT SECTION 10.7

#### Key concepts. (This is not a complete list of all the content.)

• 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).

#### Parts of Chapter 10 that were NOT covered in this course

Section 10.7 on "Planar Graphs";

 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