Chapter 3

This chapter, as the name suggests, deals with graphs. Some examples of graphs are:

• Transportation Networks
• Communication Networks
• Information Networks
• Social Networks
• Dependency Networks

For now, we just talk about undirected graphs, where the edges of the graphs have no particular direction.

Path is a sequence of nodes with the property that each consecutive pairs is joined by an edge in the graph. It may be 'simple', if all the vertices are distinct or 'cycle', if an edge goes back to one of its previous nodes.

Connected graph is a one where all the nodes are connected to each other via some path.

An undirected graph is called a tree if it is connected and is not cyclical. Rooting a tree makes it look simpler (Figure 3.1 in the book, page 77).

• Take a node
• All the nodes that are directly connected to it would be in Layer 1
• For each nodes in layer 1, find all the nodes that are not already a part of the tree and put them in Layer 2
• And so on

Proof on page 81.

Exploring a connected component algorithm on page 82 and proof on page 83.

Using this method, you take a node and find a node it connects to and find another node that connects to it and so on, without pointing to a node that is already connected, until the node that is not connected to any other node is reached, and then you backtrack up to find the other nodes.

Algorithm on 84 and proof on page 86.

“For any two nodes s and t in a graph, their connected components are either identical or disjoint.” (Page 86, with proof)

A graph can be represented by an adjacency matrix or an adjacency list.

• Takes Θ(n^2) space
• Takes Θ(n) time to examine all the edges incident to a given node

Not all graphs have n^2 edges, so the adjacency list would be more convenient in these cases.

• Takes O(m + n) space

Queues use FIFO and Stack use LIFO.

Implemented using an array of discovered nodes (Algorithm on page 90, proof on page 91).

Implemented using a stack (Algorithm on page 92).

Both BFS or DFS can be used to find the set of all connected components. These methods do not see any of the nodes which are not connected to the starting node at all. Thus, the runtime is still O(n+m).

A bipartite graph is one where a set of nodes can be split into sets X and Y such that every edge in the graph has one end in X and the other in Y. In other words, the components in X cannot be connected to the other components in X itself, and the same goes for Y.

Problem: If a graph is bipartite, then it cannot contain an odd cycle.

Designing the Algorithm: We can use BFS for this problem. We simply use BFS and color the even layered nodes in one color and the odd layered nodes in another. At the end, we just need to make sure that none of the edges have the same color on both ends.

Analysis of the Algorithm: If there is an edge with both sides of the same color, then the graph contains an odd-length cycle and cannot be bipartite. This also means, a graph with no edge with both sides of the same color is bipartite (Proof on page 96).

In a directed graph, the relationship between node u and v may or may not be symmetric due to the fact that the edge has a direction now.

Directed graphs can be represented in an adjacency list matrix like the undirected graphs. The only catch to it is that each of the nodes will now have two lists each, one for the nodes they point to and the other one for the nodes that point to this node.

BFS and DFS are almost the same for Directed Graphs as they are for undirected graphs. For BFS, we just use layers to find out the nodes layer by layer as the graph is moving outward from the root. The runtime would be O(m + n). This graph would give us a path from the root s to and end note, let's say x. However, there may or may not be a path back from x to s.

To get a set of nodes that have a path to s, we could define a new directed graph called Grev that can be defined by reversing the direction of every edge and run either BFS or DFS.

A graph is strongly connected if, for every two nodes u and v, there is a path from u to v and also one from v to u. This relation between these two nodes u and v is known as mutually reachable. Thus, a graph is strongly connected if all of the nodes are mutually reachable.

“If u and v are mutually reachable, and v and w are mutually reachable, then u and w are mutually reachable.” (Proof: Page 98)

“For any two nodes s and t in a directed graph, their strong components are either identical or disjoint.” (Proof: Page 99)

An undirected graph with no cycle is a very simple structure, but a directed graph with no cycle can be a very complex structure. A directed graph with no cycles is called a directed acyclic graph, or a DAG (pronounced as a word and not spelled out).

DAGs can be used to represent dependencies or precedence relations. An example would be the different prerequisites required to take a class: i must be done before j. If there had been a cycle, there would be no way to be able to do this. You would need to have taken CSCI 111 and CSCI 112 to take CSCI 209. But if you require CSCI 209 to take CSCI 111, it is impossible.

A topological ordering of a graph G is an ordering of its nodes in such a way that all the edges point forward.

“If G has a topological ordering, then G is a DAG.” (Proof: Page 101)

“In ever DAG G, there is a node v with no incoming edges.” (Proof: Page 102)

“If G is a DAG, then G has a topological ordering.” (Algorithm: Page 102)

Identifying a node v with no incoming edges and deleting it from G can be done in O(n) runtime. Since this algorithm runs a total of n iterations, the total runtime for the algorithm would be O(n^2). This is not that bad considering the fact that some of the graphs might be very dense. But O(m + n) is much better. This runtime can be achieved using an algorithm that iteratively deletes nodes with no incoming edges. (Algorithm: Page 103)

This chapter isn't hard to understand, probably because we have discussed this in class already. No questions either. And it is definitely very easily readable, again, probably because of the class discussion.