Chapter 3: Graphs

We define a graph as a collection V of vertices, or nodes, and a collection of edges between those vertices, represented as two-element subsets: {u, v}, where u and v are nodes. For a directed graph, we consider the ordered pair (u, v), in which u is the tail of the edge, and v is the head. Then, the edge leaves u and enters v.

We see graphs everywhere:

• Transportation networks
• Communication networks
• Information networks
• Social networks
• Dependency networks (e.g. college courses and pre-requisites).

A fundamental operation involving graphs is traversing a sequence of nodes connected by edges. Specifically, we call this traversing a path of an undirected graph, defined as a sequence of nodes in which each consecutive pair is joined by an edge. A path is simple if all its vertices are distinct (i.e. if to follow it we don't visit a node twice), and a cycle is a path in which all nodes are distinct except the first and last are equal (i.e. we cycle back to where we began). Additionally, we call an undirected graph connected if there exists a path between all pairs of points. We say a directed graph is strongly connected if there is a path in both directions between each pair of points. Finally, we define the distance between two nodes to be the minimum number of edges in a path between the two. If there exists no path, we simply denote that with a symbol such as the infinity symbol.

A tree is an undirected graph that is connected and does not contain a cycle. Note that deleting any edge from a tree will make it disconnected.

Given any tree, it is useful to root it at a particular node. Thence we let the others “fall” below that root node (defined by us) and the tree is visible. Additionally, the terms parents, children, ancestors, and descendants are self-explanatory. We have the following statement:

Let G be an undirected graph on n nodes. Any two of the following statements imply the third:

1. G is connected.
2. G does not contain a cycle.
3. G has n - 1 edges.

Note that this implies that all trees of n nodes have n - 1 edges.

This was a good section which broke the ideas down to fundamentals in a manner both mathematically sound as well as illustrative: 9/10.

When considering a graph, a common question is, given two nodes s and t, is there a path between them? This is considered the question of node-to-node connectivity, or more specifically, s-t connectivity. We proceed to consider (at relatively high-level) two different natural algorithms to find such a path, or lack thereof.

A BFS consists of starting from our node s, and sequentially exploring outward in layers. Specifically,

• Layer L₁ consists of all nodes that are neighbors of s (note that sometimes we may refer to the set containing only s as L₀)
• Having defined layers L₁, …, L_j, layer L_j+1 consists of all nodes that do not belong to an earlier layer and that have an edge to a node in layer L_j.

Note that L_j is the set of all nodes exactly j from s, as well as that if a node does not appear in any layers, then there is no path from s to it. In summation by the book:

For each j >= 1, layer L_j produced by BFS consists of all nodes at distance exactly j from s. There is a path from s to t iff t appears in some layer.

Additionally, the BFS is a natural way to produce a tree T rooted at s. Then this leads to the “dropping-off” of any non-tree graph edges, which the following fact mentions:

Let T be a BFS tree from graph G, let x and y be nodes in T belonging to layers L_i and L_j respectively, and let (x, y) be an edge of G. Then i and j differ by at most 1.

The BFS algorithm yields a set R that we'll call the connected component of G containing s. Once we have this, we need simply check if t is in s to check s-t connectivity. Additionally, the path between the two is easily recoverable by recording the nodes visited along each path, then tracing backward from t. Lastly, note that the BFS is only one method of ordering the search and exploration of the connected component R. Now we proceed to explore another.

The depth-first search follows each path out to its end (a node where all nodes to which it's connected have already been explored), and then recursively follows all others (by backtracking to the last node which had one unexplored). These resulting DFS trees look very different to the BFS trees, largely because the nodes are visited in drastically different order. Thus we arrive at a similar statement, but one more focused on ancestry than levels:

Let T be a DFS tree in graph G, let x and y be nodes in T, and let (x, y) be an edge of G that is not an edge of T. Then one of x or y is an ancestor of the other.

Regardless of the search method, both find the exact same set of connected components, as stated below:

For any two nodes s and t in a graph, their connected components are either identical or disjoint.

We could think of this as illustrative of connection being transitive (at least in the undirected graph realm we're considering here).

This was also a very enjoyable section to read, clear and concise, but also covering all questions. 9/10.