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
