Differences between revisions 6 and 15 (spanning 9 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 <<latex($|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 6 as of 2004-10-25 22:46:21 → 
  Size: 1218
  Editor: yakko
  Comment:
+   ← Revision 15 as of 2014-11-11 16:50:17 → ⇥
  Size: 1238
  Editor: scot
  Comment:
-Deletions are marked like this.
+Additions are marked like this.
 Line 4:
+'''See Also''' TreeStructures
-Line 9:
+Line 11:
-{{{
     G = (V,E)
}}}
+<<latex($G=(V,E)$)>>
 Line 13:
-The size of input has two components

{{{
     |V|, |E|
}}}
+The size of input has two components <<latex($|V|,|E|$)>>
-Line 21:
+Line 17:
-{{{
     O(VE) = O(|V|*|E|)
}}}
+<<latex($O(VE)=O(|V|*|E|)$)>>
-Line 25:
+Line 19:
-To denote the set of vertices in graph G in pseudocode as 
{{{
     V[G] and the edges E[G]
}}}
+Denote the set of vertices in graph G in pseudocode as  <<latex($V[G]$)>> and the edges <<latex($E[G]$)>>
-Line 59:
+Line 50: