Directed Graphs
Contents
7.2. Directed Graphs#
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 graphs is 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).
Fig. 7.52 A directed graph with \(7\) vertices and \(8\) directed edges.#
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:
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 connected if 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.52 is 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.
Fig. 7.53 A strongly connected graph.#
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 two separate 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 graphs have 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?
Fig. 7.56 A directed graph on \(\{1,2,\ldots,6\}\).#
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:
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 of Hasse 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?
Fig. 7.57 A Hasse diagram for \(\mathcal{P}(A)\).#
Solution
Yeah… this is incredibly ugly. That’s why Hasse diagrams are so much better!
Fig. 7.58 A directed graph for the partial order induced by \(\subseteq\).#
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.
Fig. 7.59 A very simple DAG.#
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 that all edges point in the same direction. Consider the below DAG. It is a mess of edges.
Fig. 7.60 A more complicated DAG with \(8\) vertices.#
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 randint
x = randint(0,10)
if (x < 5) :
print("Foo");
else:
print("Bar");
print("Done");
x = 10
y = 5
r = 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 same reachability from every node as the original.
Specifically, if \((u,v)\) is an edge in a DAG and 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 reduction of 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) \} \)