A graph,G is simply a way of encoding pairwise relationships among a set of objects (Data structure). Consists of two sets, a set of nodes, and another for edges. An edge joins two nodes, it is denoted as e={u,v}, where u and v are nodes. There are two types of graphs: directed and undirected graphs. Directed graphs are those in which an ordered pair of nodes, lets say (u,v), the roles of u and v are interchangeable. u being the “tail” and v the “head” of the edge. We shall normally consider undirected graphs. These are those in which a pair of ordered nodes has edges to and from each of them.

Examples of graphs: Transportation networks, such as airports(nodes) and a nonstop flight from one airport to another is considered an edge. The graph is directed but in practice we would think of airports having routes to and fro other airports, thus being an example of an undirected graph. Communication networks, such as computers(nodes) joined by a direct physical link connecting them, information networks, social networks, dependency networks and many others are all examples of graphs Page74-76.

Paths and Connectivity One of the fundamental operations in a graph is that of traversing a sequence of nodes connected by edges. For example a user using hyperlinks to access webpages. A path in an undirected graph, G is a sequence P of nodes v1,v2,…,vk with the property that each consecutive pair is joined by an edge in G. A path is called simple if all its vertices are “distinct” from one another. A cycle is a path where k>2 and all first k-1 nodes are distinct and v1=vk. All these definitions carry over to directed graphs, with the following change: in a directed path or cycle, each pair of consecutive nodes has the property that (vi, vi+1) is an edge. We say an undirected graph is connected if, for every pair of nodes u and v, there is a path from u to v. And a 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. Qestion: we may also want to know whether there is a short path from u to v. We define the distance between two nodes u and v to be the minimum number of edges in a u-v path.

Trees We say that an undirected graph is a tree if it is connected and does not contain a cycle. Trees are the simplest kind of connected graphs. Deleting any edge from the tree would disconnect it. We can root a tree, T at node r, by grabbing r and letting all other nodes hang from it. A node w is the child of node v if v is the parent of w. A node x is a leaf if it has no descendants. This entails a notion of hierarchy. A tree can be employed in organizing a company in terns of which employers have priority over the others. Rooting a tree can make certain questions about trees easy to answer conceptually.

For example, how many edges does a tree of n nodes have? Each node except the root has a single edge leading “upward” to its parent, and conversely, each edge leads upward from precisely one non-root node. Every n-node tree has exactly n-1 edges. Proof on Page 78.

The scale of readability of this section is 8.5/10.