Chapter 3

This chapter introduces us the basic knowledge of graph.

The section first introduces some basic concepts and notations of graph, such as vertex, edge, and orientation of graphs.

Then several examples are illustrated: transportation networks that are tangible, though in practice directed, can be viewed as indirected graph, since the traffic normally comes both ways; Communication networks-basically just connecting computers together and sharing information-are directed graphs, since sometimes computer U hears V's signal but not conversely; information networks have very useful examples such as the WWW internet, where websites are nodes and hyperlinks are edges; social networks display the interactions among people; dependency networks are used in important biological ways such as the food web.

The geometric perspective of the communication networks further interest me-is it like a shortest path problem in nature? In addition, regard WWW as a graph is new to me: I never thought of individual websites as vertices, and hyperlinks to be edges. The directness of the information networks also play a vital rule, such as in prioritizing websites for search engines. How exactly does it work?

Next several more important definitions in graph theories are introduced, such as Paths&Connectivity (simple, cycle; strongly connected, distance), trees (child, parent, descendant, ancestor, leaf…). The text also addresses the importance of trees since they indicate hierarchy. The important theorem (3.2) is also stated.

I'd like to know more about trees, spanning trees, minimum spanning trees, etc.

Readability is 7, since most of the materials are not unfamiliar.

This section describes two natural algorithms for maze-solving problem (s-t connectivity problem).

BFS: The general idea is to fix a node s, and then find all nodes 1 distance away denoted as layer 1, 2 distances away as layer 2, etc… Notice that the BFS tree has some edges of the original graph G erased, such as those edges connecting nodes in the same layers. s and t are connected iff t is in some layer of s and the number of the layer would be the distance between s and t. An important observation is that if a and b constitute an edge, then a and b are either in the same layer or differs by one layer. The text also states a theorem we talked in class, but in a different way: the set produced at the end of the BFS algorithm is precisely the connected component containing the root node.

Question: what are some applications of BFS?

DFS: The basic idea is to list out the first layer as BFS, but then explore specifically at the first node in the layer, list out the second layer from that node, then keep on looking at the first node of that layer, etc… Notice that the DFS tree has some edges erased, in fact the theorem “ let x,y be nodes in T, if (x,y) be anedge of G that is not anedge of T, then one of x or y is an ancestor of the other” generalizes such edges.

Question: what are some applications of DFS?

The end of the section states an important theorem that is an extension, as well as an application, of the last theorem in BFS: For any 2 nodes s and t in a graph, their connected components are either identical or disjoint.

Readability: 7

This section starts with introducing and comparing the adjacency matrix and the adjacency list. The big trade off of the adjacency matrix is the amount of space it takes O(n^2), but when the graph is far away from complete, it becomes a waste of space. In addition to that, many algorithms that require to go over all the edges will take at O(n^2) time. However, if implementing with the adjacency list, the space it takes is only O(n+m), so is the running time of those algorithm. Therefore, the book uses adjacency list to implement graphs.

Note: from now on, refer O(m+n) as the linear time for graph.

Next the section introduces queue (fifo) and stack (filo), which are important tools to implement algorithm in which orders are important.

Implementing BFS: It is basically the same as we talked about in class. However, the text suggested that instead of using a list of list (where it does not matter with a queue or stack), we can use a single queue and enqueue the nodes, which is what I thought where we were heading to in class. The implementation takes O(m+n) time.

Implementing DFS: The book introduces an algorithm to implement DFS using a stack. It does the same thing as mentioned in previous section, except that instead of choosing the first one of each layer, we select the last one, because the nature of a stack-which is essentially the same idea. The running time of the algorithm is O(m+n).

Lastly, an application of DFS or BFS algorithm is exemplified: finding the set of all connected components. And its running time, a constant times the running time of DFS or BFS-still O(m+n).

Readability: 8

The section first states the Bipartiteness problem, which is essentially equivalent to the 2-colorable problem (if all nodes in a graph G can be colored in two colors with no two nodes 1 distance away from each other sharing the same color). Then an algorithm makes use of the BFS is presented, as shown in lecture. The running time of the algorithm is the running time of BFS, O(m+n) plus the running time of checking the edges and nodes O(m+n), which ends up with, still, O(m+n). Also, thanks to the algorithm, we can prove that a graph G is bipartite if and only if it does not contain an odd cycle. The only if direction is quite straight forward. The if direction is not hard either if seeing through the algorithm. If there is an odd cycle, then the cycle has to contain two nodes from the same layer (otherwise the cycle would be even), then there is an edge with the two end nodes sharing the same color, contradiction with it is 2-colorable.

Question: at a math conference, a grad student tried to show me how to prove the 4-colorable problem, but I failed following him :p so I am curious about how to prove any graph can be colored by 4 colors.

Readability: 8

To store the information of a directed graphs we normally need two adj. lists: 1st recording “to which nodes” for each node; 2nd recording “from which nodes” for each node. For two nodes in a directed graph to be connected, they have to be mutually reachable. Running the BFS or DFS of a node s on the “to which” list help us build the trees showing all the nodes that are reachable from s, but not from where one can get to s.

For a strong connected graph, every two nodes are connected. Running the BFS twice from both “to which” and “from which” direction , together with theorem 3.16, can easily test if a graph is strongly connected. Further more, similar to undirected graphs, for any two nodes s and t in a directed graph, their strong components are either identical or disjoint.

I thought about how to compute the strong component of directed graph, but not sure if it is right: 1, find a random node s, run BFS twice from both “to which” and “from which” direction, chose the overlap part, denote as the first strong component. Mark every node in the component. 2, Find an unmarked graph and do the same thing.

This section first introduces the definition of DAG. Then a very important application of DAG follows the definition: dependencies, that is, in order to complete certain tasks, what are the pre-requisite tasks to be finished first. This application is closely related to the topological ordering of DAG. Also a theorem assures that a graph has a topological ordering if and only if it is a DAG. The only if direction of the proof is more or less easy to see. The if direction can be proved by showing an algorithm that computes out the topological order of DAG. We can basically sum up the algorithm as recursively find a node that has no incoming edges, then place the node in the corresponding position (depending on how many recursive loops has been processed) and deleting its outcoming edges, then continue the recursive algorithm till all nodes are scanned through. The running time is O(m+n).

DAG and topological ordering has important practical applications. At the same time, it is not hard to conceptually understand them well.

The readability of the section is 7.