Chapter 3

This chapter introduces basic graph definitions and algorithms.

A graph consists of a collection of nodes (V) and edges (E). Directed graphs have “one-way” edges to indicate asymmetric relationships while undirected graphs have “two-way” edges to indicate symmetric relationships. Some examples of graphs include transportation, communication, information and social networks.

A path in a graph is a sequence of nodes where each consecutive pair is connected by an edge. A path is simple if all the vertices are distinct. A path is a cycle if the first and last node are the same. We say a graph is connected if there is a path from one node to every other. The distance from one node to another is the length of the shortest path between them, measured in number of edges.

A graph is a tree if it is connected and does not contain a cycle. Trees represent hierarchies.

Theorem: Any two of the following imply the third (i) G is connected, (ii) G does not contain a cycle, (iii) G has n-1 edges

Readability: 8

This section explains how to express the growth rate of running times.

Definitions of O, Ω, and Θ

Upper bounds: T(n) is O(f(n)) if T is bounded above by a constant multiple of f, that is T(n)⇐ c*f(n) eventually.

Lower bounds: T(n) is Ω(f(n)) if T is bounded below by a multiple of f, that is T(n)>= e*f(n) eventually.

Tight bounds: T(n) is Θ(f(n)) if T is O(f(n)) and Ω(f(n)).

Properties of O, Ω, and Θ

Transitivity: If f is O(g) and g is O(h), then f is O(h). This property also holds for lower and tight bounds.

Sums of Functions: If i is an integer, f1, f2, …, fi, h are functions and each fi = O(h), then f1 + f2 + … + fi = O(h)

Common Functions

Polynomial, logarithmic and exponential functions are commonly seen. A polynomial's rate of growth is determined by its highest order term. log n is bounded by every function n^x as long as x>0. Every exponential grows faster than every polynomial.

Readability: 7