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:
Please contact our webadmin with
any comments or corrections. Logging and Cookies
Unless explicitly stated otherwise, all material is copyright ©
The University of Edinburgh