Differences

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

--- courses:cs211:winter2011:journals:david:chapter6 [2011/04/06 03:05] – margoliesd
+++ courses:cs211:winter2011:journals:david:chapter6 [2011/04/06 03:26] (current) – [6.10 - Negative Cycles in a Graph] margoliesd
@@ Line 60: / Line 60: @@
 Readability: 7/10.
+====6.10 - Negative Cycles in a Graph====
+If we augment a graph by adding a sink node that has a path from every other node leading to it and the augmented graph has a negative cycle, then the original graph must have a negative cycle too. If we have a negative cycle and we are looking for a path from one node to the sink that passes through the cycle, as we increase the number of allowable edges, the cycle tends toward negative infinity. However, if there are no negative cycles, then opt(i,v)=opt(n-1,v) as long as i is greater than or equal to n. So as long as this holds true for all nodes, there are no negative cycles in the graph. We can use a pointer graph that starts off having no cycles and add edges to it until we find a cycle.
+Readability: 5/10. The last part confused me.