Recall from Chapter 1 that a graph G is simply a way of encoding pariwise relationships among a set of objects: it consists of a collection V of nodes and a collection E of edges, each of which “joins” two of the nodes. We thus represent an edge e ∈ E as a two-element subset of V: e = {u,v} for some u,v ∈ V, where we call u and v the ends of e. Edges indicated a symmetric relationsihp between their ends. WE use a directed graph when we want to show asymmetric relationships. A directed graph G' consists of a set of nodes V and a set of directed edges E'. Each e' ∈ E' is an ordered pair (u,v). We call u the tail of the edge and v the head. We also say that the edge leaves node u and enters node v. By default, graph will mean an undirected graph. Two notes: an edge should be written as a set of nodes {u,v}, but will frequently be written as (u,v); a node is often called a vertex.

We define a path in an undirected graph G = (V,E) to be a sequence P of nodes v_1, v_2, …, v_(k-1), v_k with the property that each consecutive pair v_i, v_(i+1) is joined by an edge in G. P is often called a path from v_1 to v_k, or a v_1 - v_k path. A path is called simple if all its vertices are distinct from one another. A cycle is a path v_1, v_2, …, v_(k-1), v_k, in which k > 2, the first k - 1 nodes are all distinct and v_1 = v_k (it “cycles” back to where it began).

All of these definitions carry over naturally to directed graphs with the following change: in a directed path or cycle, each pair of consecutive nodes has the property that (v_i, v_(i+1)) is an edge. In other words, the sequence of nodes in the path or cycle must respect the directionality of edges.

We say that an undirected graph is connected if, for every pair of nodes u and v, there is a path from u to v. We say a directed graph is strongly connected if, for every two nodes u and v, there is a path from u to v and a path from v to u. In addition to simply knowing about the existence of a path between some pair of nodes u and v, we may also want to know whether there is a short path. Thus we define the distance between two nodes u and v to be the minimum number of edges in a u-v path.

We say that an undirected graph is a tree if it is connected and does not contain a cycle. For thinking about the structure of a tree T, it is useful to root it at a particular node r. We “orient” each edge of T away from r; for each other node v, we declare the parent of v to be the node u that directly precedes v on its path from r; we decalre w to be a child of v if v is the parent of w. More generally, we say that w is a descendant of v if v lies on the path from the root to w; and we say that a node x is a leaf if it has no descendants.

• Every n-node tree has exactly n - 1 edges.
• Let G be an undirected graph on n nodes. Any two of the following statements implies the third.
  • G is connected.
  • G does not contain a cycle.
  • G has n - 1 edges.