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:

latex2( $G = (V, E)$ )

The size of input has two components [[latex2( $| V |, | E |$ )]]

In AsymptoticNotation we abuse the notation for size by writing

[[latex2( $O (V E) = 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

TopologicallySortingDag
Decomposing a graph into its StronglyConnectedComponents

Chapter 23

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