• Graph: encodes pairwise relationships among a set of objects; consists of a collection V of nodes and a collection E of edges
• Directed Graph: consists of a set of nodes V and a set of directed edges E' (each e' is an ordered pair - u (tail) and v (head) are not interchangeable)

Graph Examples:

• Transportation Networks: airport nodes, flight path edges
• Communication Networks: connection of computers
• Information Networks: World Wide Web and links to various pages
• Social Networks: people nodes, friendships edges
• Dependency Networks: interdependencies among a collection of objects (i.e.-course offerings w/prerequisites

Paths and Connectivity:

• Simple Path: all vertices are distinct from one another
• Cycle: the sequence of nodes “cycles back to where it begins
• Directed Path/Cycle: the sequence of nodes in the path or cycle must respect the directionality of edges
• Connected Undirected Graph: for every pair of nodes u and v, there is a path from u to v
• Strongly Connected Directed Graph: for every two nodes, there is a path in both directions
• Short Path: route with as few “hops” as possible

Trees:

• Connected undirected graph that does not have a cycle
• w is a descendant of v if v lies on the path from the root to w
• x is a leaf if it has no descendants
• Hierarchical
• Every n-node tree has exactly n-1 edges
• Any two of the following statements implies the third
  1. G is connected
  2. G does not contain a cycle
  3. G has n-1 edges