Differences between revisions 1 and 12 (spanning 11 versions)
Revision 1 as of 2004-09-27 20:23:53
Size: 368
Editor: yakko
Comment:
Revision 12 as of 2014-11-11 16:49:08
Size: 1247
Editor: scot
Comment:
Deletions are marked like this. Additions are marked like this.
Line 1: Line 1:
= Graph Theory =  = Graph Theory =
Line 4: 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 [[latex2($$V[G]$$)]] and the edges [[latex2($$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

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 latex2($$V[G]$$) and the edges latex2($$E[G]$$)

Chapter 22

Concepts

Applications

Chapter 23

Chapter 24-25

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

GraphTheoryPage (last edited 2020-01-23 22:56:28 by scot)