In a graph, we only care about whether vertices are connected or not; an edge is a set \(\{u,v\}\), indicated that the vertices \(u\) and \(v\) are adjacent.

If we want the connection to be *ordered*, then we arrive at *directed graphs* or *digraphs*. The only difference from simple graphsis that edges are now *ordered pairs* \((u,v)\).

Definition (directed graph)

A *directed graph* is a pair \((V,E)\) consisting of a non-empty set of *vertices* \(V\) and a set of *directed edges* \(E\) with \(E \subseteq V \times V\).

A

*directed edge*is sometimes called an**arc**.A directed edge \((u,v)\)

*starts at*\(u\) and*ends at*\(v\). In other words, the directed edge has**initial vertex**\(u\) and**terminal vertex**\(v\).Our previous graph definition is also called a

**undirected graph**.Note that “simple directed graphs”, “directed multigraphs”, “simple (undirected) graphs”, and “(undirected) multigraphs” are all different.

All of our previous definitions and terminologies extend natrually to the directed case. The only difference now is that edges are tuples of size \(2\) rather than sets of size \(2\) (or \(1\) for loops).

Definition (in-degree)

The *in-degree* of a vertex \(v\) in a directed graph is the number of edges which terminate at \(v\). It is denoted \(deg^-(v)\).

Definition (out-degree)

The *out-degree* of a vertex \(v\) in a directed graph is the number of edges which start at \(v\). It is denoted \(deg^+(v)\).

In Fig. 7.52, vertex \(6\) has in-degree \(2\), and out-degree \(0\). Vertex \(1\) has in-degree \(0\) and out-degree \(2\). Vertex \(7\) has in-degree \(1\) and out-degree \(2\). That is, a loop contributes one to both in-degree and out-degree.

When a vertex in a directed graph has out-degree \(0\), we call that vertex a

**sink**.When a vertex in a directed graph has in-degree \(0\), we call that vertex a

**source**.

Similar to the Handshake Theorem of undirected graphs, we have a theorem related in- and out-degree with the number of edges.

Theorem

Let \(G = (V,E)\) be a directed graph. Then:

\[|E| = \sum_{v \in V} deg^-(v) = \sum_{v \in V} deg^+(v)\]

*Proof:* Every edge in the graph has an initial vertex and a terminating vertex. Therefore, the total number of incoming edges in the graph is equal to the sum of the in-degrees of all vertices.The total number of outgoing edges is also equal to the sum of the out-degrees of all vertices. \(\blacksquare\)

## 7.2.1. Directed Connectivity#

From undirected graphs, we say two vertices \(u\) and \(v\) are connectedif the edge \(\{u,v\}\) exists in the graph. And a graph is connected when a path exists from every vertex to every other vertex.

For directed graphs, we have two notions of connectivity, since a vertex connected to an edge may be the initial vertex or the terminal vertex. In particular, the notion of a *path* changes.

Definition (directed path)

A *directed path* (or simply *path*) of a directed graph \(G = (V,E)\) is a sequence of vertices \((v_n)\) where \((v_i, v_{i+1}) \in E\) for for \(1 \leq i < n\).

In a directed graph you must “follow the arrows”. Edges can only be traversed *from* its initial vertex *to* its terminal vertex.We thus have the first kind of connectivity for a directed graph, which is the same definition (although different meaning) for a directed graph.

Definition (strongly connected)

A directed graph is *strongly connected* if there is a *directed path* from every vertex to every other vertex.

Therefore, our previous directed graph in Fig. 7.52is *not* strongly connected. For example, there is no directed path which starts at vertex \(6\).

In particular, as a corollary of this definition, a strongly connected directed graph cannot have any sink vertices or any source vertices. This is a natural consequence of the definitions. The proof is left to the reader.

The graph shown above is strongly connected since a path exists from every vertex to every other vertex. It may be a rather complex path, a path exists nonetheless. For example, the path \((3,4,2,1)\) connects \(3\) to \(1\), the path \((1, 2, 3)\) connects \(1\) to \(3\), etc.

To existence of strong connectivity suggests the existence of weak connected.For that, we need one more definition first: the *underlying graph*.

Definition (underlying graph)

Given a directed graph \(G = (V,E)\), its *underlying graph* is the undirected graph obtained by replacing every directed edge with an undirected edge.

Definition (weakly connected)

A directed graph is *weakly connected* if its underlying graph is connected.

By this definition, Fig. 7.54 is not weakly connected.Indeed, we can see in its underlying graph that there are twoseparate connected components: \(\{2,4\}\) and \(\{1,5,6,7,3\}\).

Speaking of connected components, these two definitions of connectivity yield two definitions of a connected component.

Definition (strongly connected component)

An induced subgraph \(H = (W,F)\) of a directed graph \(G = (V,E)\) is a *strongly connected component* if \(H\) is a strongly connected directed graph and adding any other vertex \(v \in V \setminus W\) would make \(H\) not strongly connected.

Definition (weakly connected component)

A weakly connected component of a directed graph is the directed subgraph induced by a connected component of its underlying graph.

Therefore, Fig. 7.54 has two weakly connected components but no strongly connected components.

Finding Connected Components

Find all the weakly and strongly connected components of the above graph

Finding Connected Components

The entire graph is weakly connected.

A strongly connected component is \(\{1,2,3,4\}\).

A strongly connected component is \(\{5,6,7,8\}\).

## 7.2.2. Binary Relations as Graphs#

Recall Relations.Let \(\mathcal{R}\) be a binary relation on a set \(A\).We know that \(\mathcal{R}\) is a subset of \(A \times A\).

We also saw in the previous section that directed graphshave the set of edges \(E\) be a subset of \(V \times V\), for the vertex set \(V\).Thus, the set of edges in a directed graph actually indues a binary relation on the set of vertices.

If you can describe the edges of a directed graph as pairs of vertices, then you can describe the binary relation induced on the vertex set.

Consider the following graph on the vertex set \(\{1,2,3,4,5,6\}\).What is the binary relation that it encodes?

Solution

\(\mathcal{R} = \{ (1,5), (2,4), (3,4), (4,1), (5, 6), (6,1), (6,2) \}\)

Let’s try the opposite direction now.

The Graph of a Binary Relation

Consider the binary relation \(\mathcal{R}\) on \(A = \{1,2,3,\ldots,8\}\) defined as:

\[\mathcal{R} = \{ (1,2), (1,3), (2,4), (3,4), (4,1), (4,6), (5,6), (6,2), (6,7), (7,8), (8,5)\}\]

Can you draw the corresponding graph?

Finding Connected Components

Attention

When drawing a graph representing a binary relation on a large or infinite set, it is fine to only draw the vertices directly part of the relation. You do not need “floating” vertices connected to nothing.

Drawing graphs representing binary relations may feel reminiscent ofHasse Diagram.And it’s not that much different. Hasse diagrams are just graphs with some additional conditions:

The vertex representing \(a\) is drawn

*above*any other element \(b \in A\) such that \(a \preceq b\).“Transitive” edges are omitted.

For \(A = \{a,b,c\}\),consider the binary relation induced on \(\mathcal{P}(A)\) and the subset partial ordering \(\subseteq\).We have seen its Hasse diagram in Hasse Diagram.It is repeated below. Now, can you draw the graph which would explicitly encode the binary relation?

Solution

Yeah… this is incredibly ugly. That’s why Hasse diagrams are so much better!

## 7.2.3. Directed Acyclic Graphs#

A very important class of directed graphs is *directed acyclic graphs*. As the name suggests, they are directed graphs with no loops!

Definition (directed acyclic graph)

A *directed acyclic graph* (DAG) is a directed graph with no directed cycles.

So far, every directed graph we have seen (except the hidden solution of Fig. 7.58) have *not* been DAGs.Go back and check. Can you find cycles in all of those directed graphs?

Indeed, DAGs have certain properties as a simple consequence of having no cycles:

DAGs have no strongly connected components (other than single vertices). Only through cycles can a directed path exist from a vertex \(u\) to a vertex \(v\) and from \(v\) to \(u\).

DAGs have at least one source vertex.

DAGs have at least one sink vertex.

DAGs are incredibly important for describing scheduling problems,program structure, data processing, machine learning, version control, and much more.

The most useful property of DAGs, and why they are so useful in practice, is that they can *always* be *topologically ordered*.That is, they can be drawn in such a way thatall edges point in the same direction.Consider the below DAG. It is a mess of edges.

A topological ordering of this DAG has all edges oriented in the same direction. Not necessarily parallel lines or anything,but more or less “flowing” in the same direction. Typically, left to right, or top to bottom. Below is Fig. 7.60 topologically ordered.

### Control-Flow Graphs#

(*This section isn’t testable. It’s just for fun.*)

So why are DAGs so useful in practice?Consider what the topological ordering of the DAG above suggests.It gives an explicit “prerequisite structure”:

\(6\) comes before \(2\) and \(7\).

\(2\) comes before \(4\) and \(1\).

\(4\) comes before \(1\) and \(3\).

\(1\) comes before \(3\).

\(3\) comes before \(7\).

\(7\) comes before \(8\) and \(5\).

\(8\) comes before \(5\).

This has natural applications to scheduling and data processing.

DAGs are also very good at representing the *control flow* of programs. In particular, they can be used to represent control-flow graphs.Control-flow graphs are essential to compiler theory and program optimization.

In general, control-flow graphs can have cycles, and are thus described best by directed graphs.However, *loop management* is particularly challenging. So let’s consider only acyclic control-flow graphs. Thus, DAGs.

from random import randintx = randint(0,10)if (x < 5) : print("Foo");else: print("Bar");print("Done");

x = 10y = 5r = f(x,y)g(x)print("g")h(y)print("h")

Transitive Reductions

For many directed graphs, it is possible that some edges are *redundant*. From a particular starting point, there may be multiple paths from that vertex to another vertex.If, by removing an edge \((u,v)\), the same set of vertices are still reachable from \(u\), then \((u,v)\) is “redundant”.

The *transitive reduction* of a directed graph is the graph with the subgraph with the fewest edges that still have the samereachability from every node as the original.

Specifically, if \((u,v)\) is an edge in a DAGand there is another path from \(u\) to \(v\) which does not include the edge \((u,v)\), then remove that edge.

We have already seen transitive reductions before. Indeed,A Hasse diagram is just the transitive reductionof the graph explicitly encoding the partial order.

## 7.2.4. Exercises#

Exercise 7.5

Find the strongly connected components of the below directed graph.

Solution to Exercise 7.5

The one strongly connected component is \(\{1,5,6,2,4\}\).

Exercise 7.6

Draw the directed graph encoding the following binary relation:

\(\mathcal{R} = \{(a,b) \in \mathbb{Z}^+ \times \mathbb{Z}^+ \ \mid\ a < 7, \ 2a = b\}\)

Solution to Exercise 7.6

\(V = \{1, 2, 3, 5, 6, 8, 10, 12\}\)\(E = \{(1,2),(2,4),(3,6),(4,8),(5,10),(6,12)\}\)