Core Module 6: Graph Fundamentals Part II

This is a two-week module with 3 class meetings (2/28, 3/1, and 3/6). The 3/8 class meeting is for the Elective Module (Graph Applications).

There are two parts of required readings for this module, each corresponding to a prepare quiz. This post covers the second part.

• Reading Part II: MCS Chapter 10 (broadly) – corresponding to CM6: Graph Fundamentals Prepare Quiz II. We are now at the point where we start to see the ideas connecting with each other. This chapter is long, but a lot of it is old material in disguise. Read the following guide before the textbookEmphasized parts are bolded and optional parts are italicized.
• 10.1 (re-)introduces the basic terms of graph theory again but strictly for digraphs. You may skip if you are confident that you now have a solid grasp on the terminologies. Beware of notational inconsistencies; for example, AIDMA uses G=(V,E) to describe a graph, while MCS goes with G=(V(G), E(G)). They also have slightly different notations for things such as in-degrees and out-degrees.
• 10.2 and 10.3 are some known ideas (adjacency matrices) plus some newer ideas (shortest path, path counting from matrices). You may skip as long as you have a solid idea of what a shortest path mean.
• 10.4, 10.5, and 10.6 connect directed acyclic graphs (DAGs) with partial orders. You should focus on the interconnection between these two concepts (why can we represent one with the other) more than the tedious details. Most of 10.6 can be skipped because we have already learned partial orders in Core Module 4: Sets, Functions, and RelationsBeware of the discrepancy in the definition of partial orders (see CM4: Overview and Required Reading (Important) and the class notes for CM4 for details).
• 10.7 connects partial orders with subset relations. This part is optional.
• 10.8 introduces linear orders as a special case of partial orders.
• 10.9 introduces product orders. This part is optional.
• 10.10 (re-)introduces equivalence relations again. You probably don’t need to read it once more.
• 10.11 is a summary/review of all relational properties in both set theory and graph theory terms. It is a great resource to examine your comprehension of these two topics!

• If you are also taking CS201 right now, you might want to read about Depth-First Search (DFS) and Breadth-First Search (BFS) on general graphs.
• For 230 purposes, you do NOT need to know the implementation (recursive or iterative) in Java. What is important for CS230 is you know how conceptually these two search algorithms differ, and that they can be performed on general graphs instead of only trees.

To earn a satisfactory completion for CM6: