Differences between revisions 1 and 14 (spanning 13 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:

<<latex($G=(V,E)$)>>

The size of input has two components <<latex2($|V|,|E|$)>>

In AsymptoticNotation we abuse the notation for size by writing

<<latex($O(VE)=O(|V|*|E|)$)>>

Denote the set of vertices in graph G in pseudocode as <<latex($V[G]$)>> and the edges <<latex($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 1 as of 2004-09-27 20:23:53 → 
  Size: 368
  Editor: yakko
  Comment:
+   ← Revision 14 as of 2014-11-11 16:50:02 → ⇥
  Size: 1239
  Editor: scot
  Comment:
-Deletions are marked like this.
+Additions are marked like this.
 Line 1:
 = Graph Theory =
 Line 4:
+'''See Also''' TreeStructures

== Notation ==

A graph is usually specified by:

<<latex($G=(V,E)$)>>

The size of input has two components <<latex2($|V|,|E|$)>>

In AsymptoticNotation we abuse the notation for size by writing 

<<latex($O(VE)=O(|V|*|E|)$)>>

Denote the set of vertices in graph G in pseudocode as  <<latex($V[G]$)>> and the edges <<latex($E[G]$)>>
-Line 9:
+Line 25:
+   * 22.1: RepresentingGraphs
-Line 14:
+Line 31:
-   * TopologicallySortingDAG
   * DecomposingDAGintoStronglyConnectComponents
+   * TopologicallySortingDag
   * Decomposing a graph into its StronglyConnectedComponents
-Line 18:
+Line 35:
+   * MinimumWeightSpanningTree
   * Minimum Spanning Trees are generally GreedyAlgorithms
   * KruskalAlgorithm
   * PrimAlgorithm

== Chapter 24-25 ==

   * 24: Shortest Path to all vertices from a single vertex
   * 25: AllPairsShortestPathProblem

== Chapter 26 ==

   * 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