Chapter 3: Graphs

A graph represents pairwise relationships between objects and consists of nodes and edges. In order to represent asymmetric relationships between ends of a graph, we would use a directed graph, which consists of a set of nodes and a set of directed edges. It is important to note that edges have a head and a tail, positions which are not interchangeable. We can also have undirected graphs which would refer to a graph that is not directed, while we will usually just call a “graph”. The following are some examples of graphs:

  • transportation networks
  • communication networks
  • information networks
  • social networks
  • dependency networks

When working with graphs, it is frequently necessary to be able to traverse a sequence of nodes and edges. Another important term here is a path, which is a sequence of nodes such that each consecutive pair of nodes is joined by an edge. There can also be a cycle in a graph, which means the path “cycles back” to its initial node. A graph can be connected, meaning every pair of nodes are connected by paths. To find the distance between two nodes, we consider the number of edges in the path from node 1 to node 2.

An undirected graph (or simply, graph) can be a tree as well. This means that a graph is connected and does not contain a cycle. There are two important facts about trees:

1. Every n-node tree has n - 1 edges.

2. Given G, an undirected graph with n nodes, any two of the following implies the third: i.) G is connected, ii.) G does not contain a cycle, iii.) G has n - 1 edges.

There are two natural algorithms that can be used to solve the problem of determining s-t connectivity, or whether there exists a path between node s and node t in graph G. The first is a Breadth-First Search (BFS). In this algorithm, one starts at node s, looks at all possible edges extending from node s, and adds all nodes connected to these edges to a layer. This pattern is repeated for all nodes in the layer we have just created, and so on until no new nodes are discovered. The layers (L₁,…, L_j) can be characterized by these facts: 1. layer L₁ consists of all nodes which are neighbors to s 2. layer L_{j + 1} (assuming we have defined L₁,…, L_j) consists of all nodes not belonging to an earlier layer but containing an edge to a node in L_j. The number of the layer is also the distance from s to every node in that layer. A breadth-first search tree is the tree produced by running the BFS algorithm.

The second algorithm used to determine paths between nodes is the Depth-First Search (DFS). This algorithm searches from s and follows to first edge to a connected node, then searches from this node's first edge to a connected node, and so on until a “dead end” is reached. At this point you must backtrack to a node which has an unexplored edge, and you would repeat the pattern from this node. Like BFS, DFS produces a rooted tree, called a depth-first search tree, though it will likely have a very different structure due to the nature of the algorithm.

An important fact is given regarding the relationship between connected components within a graph: For any two nodes s and t in a graph, their connected components are either identical or disjoint.