Chapter 3 - Graphs

This section offers a very broad introduction to graphs themselves. We are offered a definition of graphs: a collection of both edges and nodes, where the edges connect the nodes. There are also both directed and undirected graphs. In a directed graph, the edges actually have a tail and a head. The author then walks through various examples of graphs so that we can have a better sense for exactly how and what they represent.

The author then walks through the concept of connectivity. This brings into play the idea of paths between nodes which can be represented as a series of nodes, which are connected by edges. Additionally, there must not always be a finite distance between two nodes.

Following this, the author briefly covers trees, and the role they play in the graphing world. Having just covered heaps in Chapter 2, these seem very similar with some small variations. This section offered a strong introduction to graphs and was both understandable and concise. I would rate the readability of this section at 9/10.

The section by laying out the problem of connectivity. For two nodes s and t, we want to be able to determine if they are connected. We do this by defining a set of nodes called the connected component. This connected component of a node s contains all nodes which are connected to s.

The section then goes on to illustrate a few different ways to generate the connected component - the first being the breadth-first search (BFS). The BFS starts at a node, call it 's', and then branches out from that node s to create a layer, L_1 (layer 1). That layer contains all of the nodes to which s is directly connected. The process is then done again, but L_2 contains all of those nodes that are connected to all nodes in L_1, but does not add any nodes which are already in the set. This process continues until we reach an empty layer. The book also walks through the fact that for any node in L_i, that node is exactly a distance of i away from 's'. And that the structure of a BFS can be represented as a tree rooted at the start node.

The section then moves on to the concept of exploring a connected component. It lays forth an algorithm to seek out the connected component in a vague manner. It just continually adds nodes to a set R which are connected to nodes in the component, R, until it cannot any longer. The set R begins as just the start node, 's'. I found the proof that this algorithm works slightly confusing, but I agree with the intuition behind it.

The section continues on to the depth-first search (DFS). This starts at a node s, and rather than defining layers, it continues to one node, then adds it to the component, then recursively calls itself. Eventually, when it reaches a stopping point, the algorithm backtracks to previous calls, and recalls itself to see if there was a different, deeper, path it could have explored. I found the proof of (3.6) to be very helpful, as I found the concept slightly confusing in class.

The section ends by outlining the set of all connected components and proves that for any two nodes, their connected component is either identical or disjoint. I found this proof very straight-forward. I enjoyed reading this section and found it to be a helpful refresher from class. I would rate the readability at 9/10.