Chapter 3

A graph is a collection of V nodes and E edges where an edge e is represented as a two-element subset {u, v}. Directed graphs represent an edge e in ordered pairs (u, v), which are not interchangeable. An undirected graph is essentially a default graph. Examples of graphs include transportation, communication, information(e.g. world wide web), social, and dependency networks. An important operation in graphs is traversing a sequence of nodes connected by edges. Traversal requires that a path, a sequence of of connected nodes, exist. An undirected graph is corrected if there exists a path between every pair of nodes. Interestingly, trees are undirected graphs that do not contain a cycle (the sequence of nodes does not cycle back to where it begins). Overall the section was a basic overview of graphs, and it's readability is an 8/10.

Chapter begins with introduction to the problem of determining connectivity between two nodes, s and t. One algorithm for determining connectivity is Breadth-First Search (BFS), which explores outwards from s layer by layer. BFS outputs a tree. Another natural way of determining connectivity between s and t is Depth-First Search (DFS). Unlike BFS, DFS explores outward from s following a path of connected edges until it reaches a dead end. It then backtracks to a node with an unexplored neighbor and tries another route. DFS also outputs a tree, but of a very different shape. Another important subject in this section is a Connected Component. The connected component of a node s is the set of nodes reachable from s. For any two nodes s and t in a graph, their connected components are either identical and disjoint. Overall, the readability of this section is 8/10.

There are two ways to represent a graph: an adjacency matrix and an adjacency list. When discussing nodes and edges, n represents the number of nodes and m the number of edges. The goal run time for graph search algorithms is O(n+m), which is technically referred to as linear time. An adjacency matrix allows us to check in O(1) time if an edge (u, v) is present. However, the representation takes O(n^2) space and checking all incident edges to a node takes O(n) time. An adjacency list requires only O(m + n) list. However, checking if an edge is present takes O(n) time. Returning to the BFS and DFS, BFS effectively uses a queue to select which node to consider next, while DFS uses a stack. A BFS algorithm implementing a queue runs in O(m + n) time, as does a DFS algorithm implementing a stack. Overall, the readability of this section was 6/10.

A bipartite graph is one where its nodes can be separated into sets of either “red” or “blue” nodes such that every edge has a red and blue end. A bipartite graph cannot contain an odd cycle. So, an algorithm that tests for bipartiteness of graphs need only check for odd cycles. This test for bipartiteness algorithm is essentially BFS with the additional step of coloring each layer of nodes and checking whether there is any edge has two ends of the same color. Thus, the run time of this algorithm is O(m + n). Overall, the readability was 7/10.