Differences between revisions 12 and 16 (spanning 4 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 (V E) = O (| V | * | E |)$

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 12 as of 2014-11-11 16:49:08 → 
  Size: 1247
  Editor: 216
  Comment:
+   ← Revision 16 as of 2020-01-23 22:56:28 → ⇥
  Size: 1193
  Editor: 68
  Comment:
-Deletions are marked like this.
+Additions are marked like this.
 Line 11:
-<<latex($G=(V,E)$)>>
+$$G=(V,E)$$
 Line 13:
-The size of input has two components [[latex2( $| V |, | E |$ )]]
+The size of input has two components  $| V |, | E |$
 Line 17:
-<<latex($O(VE)=O(|V|*|E|)$)>>
+$$O(VE)=O(|V|*|E|)$$
 Line 19:
-Denote the set of vertices in graph G in pseudocode as  [[latex2( $V [G]$ )]] and the edges [[latex2( $E [G]$ )]]
+Denote the set of vertices in graph G in pseudocode as   $V [G]$  and the edges  $E [G]$