Chapter 3 - Graphs

Summary: Section 3.1 is Basic Definitions and Applications. Graphs consist of nodes and edges, where the edges join two nodes. Graphs can be undirected or directed, and graphs are assumed to be undirected unless stated otherwise. Technically, an edge between nodes u and v in an undirected graph is represented as the set {u,v}, but the authors warn that the notation for a directed edge, (u,v), will sometimes be used even for undirected edges. The directed edge (u,v) is an edge from u to v. Transportation, communication, information, social, and dependency networks are examples the authors provide for where graphs are used. The section also addresses paths (simple or cyclical), connectivity (including strong connectivity for directed graphs), and shortest path/distance between two nodes. Trees are connected graphs that have no cycles - they're “the simplest kind of connected graph: deleting any edge from a tree will disconnect it” (p77). While on the topic of trees, the authors state that “rooted trees are fundamental objects in computer science, because they encode the notion of a hierarchy” (p78). The section closes with a list of three statements about undirected graphs with n nodes, such that if any two are true so also is the third.

My Questions: Not exactly a question, but I wonder why the authors introduced trees in this section after we've already seen balanced binary trees when talking about the heap implementation of the priority queue. For example, it's an information repeat to tell us about parents and children.

Second Time Around: Honestly, everything in this chapter I'd seen before in MATH301 (except the Note to Self) and/or it was crystal clear in class.

Note to Self: In the information networks example (p75), it says that search engines use hyperlink edges between webpage nodes to determine what webpages are the most important. I didn't know that, but makes sense and it's certainly cool.

Readability: 10 - super straightforward. A relief after section 2.5.

Summary: Section 3.2 is Graph Connectivity and Graph Traversal. Given two nodes s and t of a graph G = (V,E), connectivity is defined as there being a path from s to t. There are two algorithms for answering this question: breadth-first search (BFS) and depth-first search (DFS). BFS starts with node s, and then adds nodes in layers based on them being connected to the node(s) in the previous layer. Layer zero, then, is just node s. Layer one consists of all nodes connected to s. Layer two consists of all nodes connected to the nodes connected to s. And so on until there are no nodes left that aren't already in a layer. Because the distance between two nodes is defined as the “minimum number of edges on a path joining them” and a node will be absent from all layers “if and only if there is no path to it” (p 80), then BFS not only determines if there is a path between nodes s and t, but it also determines the shortest path. BFS is a method for finding a connected component, which is the set of all nodes reachable from starting node. Another method for finding a connected component is DFS. In DFS, you traverse as deeply as possible and only backtrack when you hit a dead end. While the BFS tree shows the shortest path from s to t and ends up being short and bushy, the DFS tree will usually be long and spindly.

My Questions:

Second Time Around: Theorem 3.4, which says that if (x,y) is an edge in the graph, then the layers in which they appear for BFS differ by at most 1, made more sense the second time around. In class I was a little lost, but now that I've seen it twice I think I've got it.

Note to Self:

Readability: 7. I think the u's and v's running around the section were hard to keep track of at times.

Summary: Section 3.3 is Implementing Graph Traversal Using Queues and Stacks.

Problem Motivations:

About the Algorithms:

My Questions:

Second Time Around:

Note to Self:

Readability:

Summary: Section 3.4 is Testing Bipartiteness: An Application of Breadth-First Search.

Problem Motivations:

About the Algorithms:

My Questions:

Second Time Around:

Note to Self:

Readability:

Summary: Section 3.5 is Connectivity in Directed Graphs.

Problem Motivations:

About the Algorithms:

My Questions:

Second Time Around:

Note to Self:

Readability:

Summary: Section 3.6 is Directed Acyclic Graphs and Topological Ordering.

Problem Motivations:

About the Algorithms:

My Questions:

Second Time Around:

Note to Self:

Readability: