Differences

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

--- courses:cs211:winter2018:journals:beckg:ch3 [2018/02/07 03:22] – [3.3: Implementing Graph Traversal Using Queues and Stacks] beckg
+++ courses:cs211:winter2018:journals:beckg:ch3 [2018/02/07 04:26] (current) – beckg
@@ Line 112: / Line 112: @@
 Additionally, we can find the set of //all// connected components using either algorithm, and this takes //O(m + n)// time as well. This is because doing one connected component removes those nodes from the next group of nodes in the graph //G// that must be searched next.
+This section explained the algorithms very well, I would give it a 9/10.
 ===== 3.4: Testing Bipartiteness with Breadth-First Search =====
+Recall that a bipartite graph is one that can have its nodes partitioned into sets //X// and //Y// such that each edge has one end in //X// and the other in //Y//.
+A graph is bipartite if and only if it contains no odd cycles.
+We can implement an algorithm for testing this using the BFS search tree. We simply create an array ''Color'' in which each node is assigned a color red or blue, alternating with each subsequent level. If ever there is an edge for which both ends have the same color at the end, then it is not bipartite. This runs in //O(m + n)// time as well, a nice recurring theme it seems. The proof for this algorithm hinges simply on the fact that if there is ever an edge in //G// between nodes in the same layer, then there is an odd length cycle, and therefore it is not bipartite.
+Obviously brief, this section complemented our class discussion of the process very well, though I do think it could have been a little more concise in the order of its claims; an 8/10.
+===== 3.5: Connectivity in Directed Graphs =====
+Directed graphs simply mean that edge //(u,v)// indicates an edge //from// //u// //to// //v//. To represent these, we simply give each node two lists: one which contains the nodes //to which// it has edges, and the other which has all the nodes //from which// edges are incident to it.
+DFS and BFS run essentially the exact same way with these, simply following the edges "out" from the source node. However, the crucial distinction is in //what// these search trees represent. The "connected component" of //s// then is all of the nodes that can be reached //from// it. Note that BFS still gives us the shortest path if one exists. Additionally, we can define a new graph //G<sup>rev</sup>// as the same //G// but with all the directions reversed. Then, running a BFS or DFS in this reversed graph, we know if we reach node //n// //from// //s// in //G<sup>rev</sup>//, then that indicates that it has a path //to// //s// in //G//.
+===Strong Connectivity===
+This above function becomes useful in determining strong connectivity of a given graph. First, we define two nodes to be //mutually reachable// if there is a path from //u// to //v// and from //v// to //u//. Additionally, note that this property is transitive.
+If every pair of nodes in a graph is mutually reachable, then we call the graph //strongly connected//. To determine whether a given graph is strongly connected, we run the search mentioned above from //s// in //G// and in //G<sup>rev</sup>//, and if either fails to reach every node, then //G// is not strongly connected.
+So, we can define the //strong component// of a given node to be the set of all other nodes to which it is strongly reachable. This is similar to the connected components of undirected graphs. Then, we have that:
+For any two nodes //s// and //t// in a directed graph, their strong components are either identical or disjoint.
+Just as with the connected components, we can determine all of the strong components of a directed graph in, wait for it, //O(m + n)// time.
+This was a lovely chapter that expounded on strong connectivity very smoothly; 10/10.
+===== 3.6: Directed Acyclic Graphs Topological Ordering =====
+A directed graph with no cycles is //directed acyclic graph// or //DAG//. We define a //topological ordering// of a directed graph to be an ordering of all of its nodes as //v<sub>1</sub>, v<sub>2</sub>, ..., v<sub>n</sub>// so that for every edge //(v<sub>i</sub>, v<subj</sub>)//, we have that //i < j//. This immediately leads to the fact that if //G// has a topological ordering, then //G// is a //DAG//.
+From the fact that a //DAG// must have a node with no incoming edges, we then find the stronger statement that:
+//G// is a //DAG// iff it has a topological ordering.
+==Algorithm to compute topological ordering of G==
+''Find a node //v// with no incoming edges and order it first\\
+Delete //v// from //G//
+Recursively compute topological ordering of //G-{v}// and append this after //v//''
+Thanks to the above theorem, we know that there will always be such a node //v// to compute. The total running time is //O(n<sup>2</sup>)//, and if //G// is very dense (//Theta(n<sup>2</sup>// edges) then this is linear in the size of the input. If the graph is more sparse though, then the //O(m + n)// could be a very good improvement.
+We can actually achieve this //O(m + n)// time if we are more efficient in finding the nodes that have no incoming edges. We simply maintain for each node the number of incoming edges that it has. Then that number iterates downwards when one its incoming neighbor is deleted, to where we are aware of which node has zero.
+This section also did a great job of explaining, and I am a big fan of the giving us the general algorithm, and then a method to make it more efficient. This will prove very beneficial in developing/analyzing them in the future as they grow more complex; 9/10.