Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2011:journals:wendy:chapter3 [2011/02/02 04:06] – [Section 3: Implementing Graph Traversal Using Queues and Stacks] shangw
+++ courses:cs211:winter2011:journals:wendy:chapter3 [2011/02/15 07:33] (current) – [Section 5: Directed Acyclic Graphs and Topological Ordering] shangw
@@ Line 48: / Line 48: @@
 Readability: 8
+===== Section 4: Testing Bipartiteness: an Application of BFS =====
+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
+===== Section 5: Connectivity in Directed Graphs =====
+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:
+, 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.
+, Find an unmarked graph and do the same thing.
+===== Section 5: Directed Acyclic Graphs and Topological Ordering =====
+ 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.