====== Chapter 3.1: Graphs - Basic Definitions and Applications ======
A **graph** //G// is a way of encoding pairwise relationships among a set of objects. It has a collection //V// of nodes and a collection //E// of edges, each of which joins 2 nodes together. We represent an edge //e// in //E// as a two-element subset of //V//, i.e. //e = {u,v}// for //u// and //v// in //V//. We can encode asymmetric relationships with a **directed graph**. In these graphs an edge //e'// in //E// is written as //e' = (u,v)// where //u// and //v// are in //V// and cannot be interchanged. The edge //e'// points from node //u// to node //v//.

A **path** in an undirected graph //G=(V,E)// is a sequence //P// of nodes //v_1,v_2,...,v_k// with the property that each consecutive pair //v_i,v_i+1// is joined by an edge in //G//. A path is **simple** if all its vertices are distinct from one another. A **cycle** is a path //v_1,v_2,...,v_k// in which k>2, the first k-1 nodes are all distinct and //v_1=v_k//. These definitions hold for directed graphs, except each pair of consecutive nodes has the property that //(v_i,v_i+1)// is an edge.

An undirected grpah is **connected** if for every pair of nodes //u// and //v//, there is a path from //u// to //v//. A directed graph is **strongly connected** if for every 2 nodes //u// and //v//, there is a path from //u// to //v// and a path from //v// to //u//.
The distance between two nodes //u// and //v// is the length of the shortest path between //u// and //v//.

An undirected graph is a **tree** if it is connected and does not contain a cycle. Trees are rooted at a particular node, //r//, and each edge of the tree //T// is oriented away from //r//. For every other node //v// in //T//, the **parent** of //v// is the node //u// that directly precedes //v// on its path from //r//. The node //w// is the **child** of //v// if //v// is the parent of //w//. More generally we can say that //w// is a **descendant** of //v// or //v// is an **anscestor** of //w//. A node //x// is a **leaf** if it has no descendants.
Rooted trees are useful in encoding the notion of a hierarchies. Rooted trees can tell us several things. We know that every n-node tree has exactly n-1 edges. We also know that if //G// is an undirected graph on n nodes, then any two of the following statments implies the third:
  - //G// is connected
  - //G// does not contain a cycle
  - //G// has n-1 edges