Differences between revisions 2 and 7 (spanning 5 versions)

Graph Theory

This page contains over view information and links to concepts covered in "Intro to Algorithms" by Cormen, Leiserson & Rivest.

See Also TreeStructures

Notation

A graph is usually specified by:

     G = (V,E)

The size of input has two components

     |V|, |E|

In AsymptoticNotation we abuse the notation for size by writing

     O(VE) = O(|V|*|E|)

To denote the set of vertices in graph G in pseudocode as

     V[G] and the edges E[G]

MaxFlowNetwork
This general problem arises in many forms and a good algorithm for computer MaxFlow can be used to solve a variety of related problems

-  ⇤ ← Revision 2 as of 2004-09-27 20:35:50 → 
  Size: 1131
  Editor: yakko
  Comment:
+   ← Revision 7 as of 2004-10-25 23:51:12 → ⇥
  Size: 1251
  Editor: yakko
  Comment:
-Deletions are marked like this.
+Additions are marked like this.
 Line 4:
+'''See Also''' TreeStructures
-Line 34:
+Line 36:
+   * 22.1: RepresentingGraphs
-Line 40:
+Line 43:
-   * DecomposingDagIntoStronglyConnectComponents
+   * Decomposing a graph into its StronglyConnectedComponents
-Line 46:
+Line 49:
+   * KruskalAlgorithm
   * PrimAlgorithm