|
Size: 1238
Comment:
|
← Revision 16 as of 2020-01-23 22:56:28 ⇥
Size: 1193
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 11: | Line 11: |
| <<latex($G=(V,E)$)>> | $$G=(V,E)$$ |
| Line 13: | Line 13: |
| The size of input has two components <<latex($|V|,|E|$)>> | The size of input has two components $$|V|,|E|$$ |
| Line 17: | Line 17: |
| <<latex($O(VE)=O(|V|*|E|)$)>> | $$O(VE)=O(|V|*|E|)$$ |
| Line 19: | Line 19: |
| Denote the set of vertices in graph G in pseudocode as <<latex($V[G]$)>> and the edges <<latex($E[G]$)>> | Denote the set of vertices in graph G in pseudocode as $$V[G]$$ and the edges $$E[G]$$ |
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(VE)=O(|V|*|E|)$$
Denote the set of vertices in graph G in pseudocode as $$V[G]$$ and the edges $$E[G]$$
Chapter 22
Concepts
Applications
Decomposing a graph into its StronglyConnectedComponents
Chapter 23
Minimum Spanning Trees are generally GreedyAlgorithms
Chapter 24-25
- 24: Shortest Path to all vertices from a single vertex
Chapter 26
This general problem arises in many forms and a good algorithm for computer MaxFlow can be used to solve a variety of related problems