Chapter 3.1: Graphs - Basic Definitions and Applications

A graph G is simply a way of encoding pairwise relationships among a set of objects. A directed graph G consists of a set of nodes V and a set of directed edges E. Each e that is an element of E is an ordered pair (u, v); in other words, the roles of u and v are not interchangeable, and we call u the tail of the edge and v the head.

A few examples of graphs:

• Transportation networks (subways)
• Communication networks (computer networks)
• Information networks (the internet)
• Social Networks (facebook)
• Dependency Networks (food web)

Paths and Connectivity

A path is a sequence of nodes with the property that each consecutive pair is joined by an edge. A path is called simple if all its vertices are distinct from one another. A cycle is a path in which the first k-1 nodes are distinct, with the kth node being the first node. In this way the path “cycles back.”

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 that 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.

Trees

We say that an undirected graph is a tree if it is connected and does not contain a cycle.

(3.2)  Let G be an uundirected graph on n nodes.  Any two of the following statements implies the third.
 (i) G is connected.
 (ii) G does not contain a cycle.
 (iii) G has n-1 edges.
 

This section of chapter 3 will be good review when going over graphs. 9/10.