Chapter 3: Graphs

This chapter was very easy to read, and I would score it about a 7 on a scale from 1-10 on readability. This section defined graphs and outlined some common uses for them. A graph is made up of a collection V of nodes and a collection E of edges, which “joins” two of the nodes. Edges represent a symmetric relationship between their ends. Directed graphs are used for asymmetric relationships and contain a set of nodes V and a set of directed edges E'. Each element n E' is an ordered pair, (u, v). u is the tail of the edge and v is the head of the edge. Edge e' leaves node u and enters node v. If a graph is not directed, it is considered an undirected graph, and it is written as a set of nodes {u, v}.

There countless applications of graphs. The book lists five useful applications of graphs and what they can represent: transportation networks, communication networks, information networks, social networks, and dependency networks.

There are several other terms regarding graphs that were defined in this chapter. A path is a sequence P of nodes where each consecutive pair is joined by an edge in G. A path is simple if all of its vertices are distinct from one another. A cycle is a path where the sequence of nodes “cycles back” to where it began. The sequence of nodes in the path or cycle must respect the directionality of edges. A connected graph is a graph where every pair of nodes u and v has a path from u to v. It is strongly connected if, for every, two nodes u and v, there is a path from u to v and a path from v to u. Furthermore, an undirected graph is considered a tree if it is connected and does not contain a cycle and is the simplest kind of connected graph. Trees can be used to represent a hierarchy.

This section discussed two main methods to determine if there is a path from the starting node, s, to another node, t, in graph G. This is known as s-t connectivity. This section reinforced what I had learned not only in class but what we had done in CS 112. Overall, on a scale from 1-10 regarding readability, this section was about a 7.

The first main method to determining connectivity is the Breadth-First Search (BFS). This method goes outward from s in all possible directions, adding nodes one “layer” at a time. It can only visit nodes that s can reach. The layer that the node is indicates the point in time the node is reached, and therefore the distance between s and t. There is only a path from s to t if and only if t appears in one of the layers. This BFS will result in a tree, T, rooted at s, called a BFS tree. Only nodes reachable from s can be added to T, therefore, this allows us to answer the connectivity question.

The second method to determining connectivity is the Depth-First Search (DFS). The way I am able to best distinguish BFS from DFS is to think of DFS as the way to solve a maze. You start at s and take the first edge leading out, continuing until a dead-end is reached. In general, DFS explores G by going as deep as possible and only retracing when necessary. Because of this functionality, DFS must maintain global knowledge of which nodes have already been explored.

This section addressed the methodology of using lists and arrays to represent graphs. There are two basic ways to represent a graph, an adjacency matrix and adjacency list. Every graph G = (V,E) has two inputs- the number of nodes |V| and the number of edges |E|. We assign n=|V| and m=|E| for simplicity. The number of edges can be at most n^2, with connected graphs having at least m>= n-1 edges. The search algorithms are in O(m+n), which is linear time. For connected graphs, O(m+n) = O(m) since m>= n-1.

An adjacency matrix is an nxn matrix where A[u,v] is 1 if the graph contains that edge. While this allows check if this edge is present in constant time, there are two major setbacks. First, the adjacency matrix takes Θ(n^2) space. Second, checking to see whether A[v,w] to see whether that edge is present takes Θ(n) time.

An adjacency list presents a better option for representing graphs. The adjacency list records for each node v, containing a list of the nodes to which v had edges. On an undirected graph each edge will occur on two adjacency lists. This representation requires only O(n+m) space, and the total lenth of all lists is 2m = O(m).

There are also two data structures which we can use to help implement the adjacency list. The first is a queue, which adds items in first-in, first-out order. The other is a stack, which adds items in a last-in, first-out order. An adjacency list is good for BFS and is more efficient to manage with a queue. DFS would be more efficient to process in a stack rather than a queue as there is a large distinction in discovering a node (BFS) and exploring a node (DFS).

Overall this section helped to clarify the use of adjacency lists and was also about a 7 on readability.

A bipartite graph is one where the set of the nodes can be partitioned into sets X and Y in such a way that every edge has one of its ends in X and the other in Y. As we discussed in class, it helps to imagine that the nodes in set X are red and the nodes in set Y are blue. This allows us to imagine a bipartite graph as one with red and blue nodes where every edge has one red end and one blue end.

In this chapter we look to find natural examples of a non-bipartite graph where no partition of V (the set of nodes) is possible. It is easy to identify that a triangle isn't bipartite, or any cycle of odd length. because every odd number node would be colored red and every even node would be colored blue, and the cycle starts and ends with an odd node, it would not be bipartite.

We can test for bipartitness by doing the following: first, assume that the graph, G, is connected. Then, pick any node s∈V and color it red. All of its neighbors are then colored blue. Next, all of the neighbors of those nodes are colored red, until the entire graph has been colored. This allows us to visualize whether or not we have a bipartite graph. This description is the same as the process for BFS. Just like BFS, the runtime for the coloring algorithm is O(n+m).