Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |||
| courses:cs211:winter2011:journals:david:chapter6 [2011/04/06 03:23] – margoliesd | courses:cs211:winter2011:journals:david:chapter6 [2011/04/06 03:26] (current) – [6.10 - Negative Cycles in a Graph] margoliesd | ||
|---|---|---|---|
| Line 63: | Line 63: | ||
| ====6.10 - Negative Cycles in a Graph==== | ====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, | + | 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, |
| + | |||
| + | Readability: | ||
