Chapter 3

A graph is a structure that represents relationships between two elements. They consists of nodes or vertices V and edges E which join the nodes to one another. An edge can be represented as a two-element subset of V: e = {u,v} where u and v are nodes at either end of e. The edges of some graphs have an order, meaning that the relationship moves in one direction but not the other. The edges in such a graph are represented by and ordered pair (u,v) where u is the head and v is the tail.

Graphs serve as important models for lots of different types of networks. Some examples from the book are listed below:

• Transportation networks with airports as nodes and non-stop flights as edges
• Lan networks with computers as nodes and physical links as edges
• Networks with all the machines using one ISP as nodes and ISPs with peering relationships as edges
• The internet, with webpages as nodes and hyperlinks as edges
• Social networks with people as nodes and relationships between them as edges

Essential to the concept of graphs is the idea of paths and connectivity. A path is a sequence of connected nodes from one vertex to another. A cycle is a special case of a path that occurs when the path begins and ends at the same vertex. An undirected graph is connected if there is a path from every vertex u to v. A directed graph is strongly connected if for every node u and v there is an edge (u,v) and an edge (v,u). The distance of a path is the number of edges in the path. A tree is a special case of a graph that occurs when the undirected graph is connected and there are no cycles. Since there are no cycles in a tree, it is a good way to represent a hierarchy. Additionally, since there are no cycles, each vertex is only connected to its parent and therefore in a tree with n nodes, there are n-1 edges.

This chapter was a breeze to read since it was mostly just term definitions and little uppper-level conceptual analysis.

Breadth-First Search is a method of search through a graph to assemble the connected component. It does this by adding a “layer,” or the set of nodes connected to the root node s, and then recursively calling itself on each node in the layer. A few interesting properties of the breadth-first search and its resultant tree are that for any nodes x and y in layers L_i and L_j joined by an edge (x,y), i and j can differ by at most 1. Additionally, the nodes returned by a BFS started at node n are precisely those in the connected component of the graph containing n.

The Depth-First Search is another method for finding all the nodes reachable from the starting node. Instead of visiting all the nodes layer by layer, however, this algorithm follows edges to unexplored nodes along one path until it reaches a dead end, at which point it will backtrack through all of its explored nodes until it finds one with an edge to an unexplored node. Now it will take that advance along the unexplored nodes in that direction until it again reaches a dead end and has to repeat the process. The algorithm will continue this until all the nodes are visited. As opposed to a Breadth-First Search where all the nodes connected by an edge must be no more than one layer apart, the Depth-First search can create trees with whose nodes are separated by more than one edge, but one of these must be a descendant of the other.

Qualitatively, these two algorithms will have roughly the same running times and efficiency since they will both be traversing the same number of nodes and edges. This is due to the fact that for two nodes in a graph, their connected components are either completely identical or disjoint (KT p. 86).

I found this chapter easily readable although a few of the proofs took a few minutes of digestion to fully comprehend.

Breadth-First Search and Depth-First search often produce quite different trees, but their mechanics are very similar and in fact their essential difference is one's using a queue versus the other's using a stack.

Breadth-First Search works in O(m+n) time to assemble the Breadth-First search tree. It does this by making a List L[i] with i = 0, so tjis only contains the root node s. It then makes an empty list L[i + 1] and adds the undiscovered nodes enumerated in adjacency lists of each node in L[i] and marks those nodes as discovered. Finally, it increments i to advance the loop. This runs in O(n+m) because besides setting up the lists in n time, a for loop runs in m time considering each edge. It runs in m time because it must consider to degree of each node, or 2m.

Depth-First Search makes a stack which initially only contains the root node s. It then enters a loop which takes the first item off the stack, marks it as explored, adds all its adjacent nodes to the stack and repeats the loop until the stack is empty. This algorithm also runs in O(n+m) time since everything within the loop runs in constant time and the loop executes as many times as the sum of the degree of all the nodes in the graph, which is 2m.

The one thing I didn't understand about this chapter is the how a BFS could be implemented using a queue. The chapter promised that this was true but didn't really explain how, at least in my eyes.