Ch 9. Graphs
9.3 Directed Graphs
In Section 4.2, you were introduced to direct graphs (or digraphs) as a means of visualizing binary relations. In that context, each element of a set was represented as a vertex, and each ordered pair [latex](a, b)[/latex] in a relation was represented as a directed edge from vertex [latex]a[/latex] to vertex [latex]b[/latex]. This section builds on that foundation by exploring additional concepts essential to analyzing and applying directed graphs in IT.
A directed graph is a graph where each edge has a direction. Instead of simply connecting two vertices, a directed edge goes from one vertex to another, indicating a one-way relationship. Vertices (or nodes) represent entities. Directed edges (or arcs) represent relationships from one vertex to another. An edge from vertex [latex]A[/latex] to vertex [latex]B[/latex] is written as [latex](A, B)[/latex] and is visually represented by an arrow pointing from [latex]A[/latex] to [latex]B[/latex].
Because the edges in our graphs now have a direction, we must introduce notation for the incoming and outgoing degrees of the vertices. The indegree of a vertex [latex]v[/latex], denoted [latex]\text{in}(v)[/latex], is the number of edges coming into it. The outdegree of a vertex, denoted [latex]\text{out}(v)[/latex], is the number of edges going out from it.
Example 9.19
Consider the following directed graph [latex]G[/latex] with five vertices.
The indegree and outdegree for each vertex are as follows:
[latex]\text{in}(A) = 1[/latex], [latex]\text{in}(B) = 2[/latex], [latex]\text{in}(C) = 2[/latex], [latex]\text{in}(D) = 2[/latex], [latex]\text{in}(E) = 0[/latex]
[latex]\text{out}(A) = 2[/latex], [latex]\text{out}(B) = 1[/latex], [latex]\text{out}(C) = 1[/latex], [latex]\text{out}(D) = 1[/latex], [latex]\text{out}(E) = 2[/latex]
A cycle in a directed graph is a path that starts and ends at the same vertex, following the direction of edges. A directed Euler cycle is a cycle that visits every edge exactly once, respecting the direction of each edge.
Example 9.20
Define a directed graph [latex]G[/latex] as shown below.
If we try to construct a cycle that uses every edge exactly once, starting at vertex [latex]A[/latex], it will always fail. This suggests that [latex]G[/latex] may not have a directed Euler cycle.
The suggestion that the directed graph in Example 9.20 does not have a directed Euler cycle is correct. You can check that for any graph to have a directed Euler cycle, its vertices must have equal indegrees and outdegrees. The next theorem formally states and proves this condition.
Theorem 9.5: Directed Euler Cycle Condition
A directed graph [latex]G[/latex] contains a directed Euler cycle if and only if the underlying undirected graph is connected and for every vertex [latex]v[/latex], [latex]\text{in}(v) = \text{out}(v)[/latex].
Proof
We first prove the following statement: A directed graph [latex]G[/latex] contains a directed Euler cycle if
-
- the underlying undirected graph is connected
- for every vertex [latex]v[/latex], [latex]\text{in}(v) = \text{out}(v)[/latex]
- Suppose [latex]G[/latex] contains a directed Euler cycle. Then the directed Euler cycle visits every edge exactly once and returns to the starting vertex. Therefore, every vertex must be reachable, and the underlying undirected graph must be connected.
- Every time the cycle enters a vertex via a directed edge, it must leave via a directed edge. Thus, the number of incoming edges must equal the number of outgoing edges for each vertex.
We next prove the converse statement: A directed graph [latex]G[/latex] that has an underlying undirected graph that is connected, and for every vertex [latex]v[/latex], [latex]\text{in}(v) = \text{out}(v)[/latex], contains a directed Euler cycle.
We will prove this using mathematical induction. The undirected graph is obtained by ignoring the directions of the edges of [latex]G[/latex].
Basis Step: Consider a directed graph with [latex]m = 0[/latex] edges. Then [latex]\text{in}(v) = \text{out}(v) = 0[/latex] and an empty cycle is an Euler cycle.
Inductive Step: Assume that any directed graph with [latex]m[/latex] edges, where the underlying undirected graph is connected and [latex]\text{in}(v) = \text{out}(v)[/latex] for all vertices, has a directed Euler cycle. Let [latex]G[/latex] be a directed graph with [latex]m + 1[/latex] edges satisfying the same conditions.
Since [latex]\text{in}(v) = \text{out}(v)[/latex] at every vertex, there must be at least one directed cycle [latex]C[/latex] in [latex]G[/latex]. Let the directed graph[latex]G’ = G - E(C)[/latex], where [latex]E(C)[/latex] denotes the edges of [latex]C[/latex]. Then, at every vertex, we still have [latex]\text{in}(v) = \text{out}(v)[/latex], and while some vertices may become isolated, the connectedness of the underlying undirected graph ensures that any remaining edges form a connected component. From the inductive hypothesis, each connected component of [latex]G’[/latex] satisfies the conditions with [latex]\leq m[/latex] edges, and thus each component has a directed Euler cycle. Since the original graph is connected, the cycle [latex]C[/latex] shares vertices with other components, and at shared vertices, we can insert the Euler cycles of components into [latex]C[/latex], forming a larger Euler cycle.
[latex]\square[/latex]
Example 9.21
Returning to Example 9.20, we compute the indegree and outdegree for each vertex as follows:
[latex]\text{in}(A) = 1[/latex], [latex]\text{in}(B) = 3[/latex], [latex]\text{in}(C) = 2[/latex], [latex]\text{in}(D) = 2[/latex]
[latex]\text{out}(A) = 2[/latex], [latex]\text{out}(B) = 3[/latex], [latex]\text{out}(C) = 2[/latex], [latex]\text{out}(D) = 2[/latex]
Only [latex]A[/latex] has unequal indegree and outdegree, so this graph does not have a directed Euler cycle.
We now look at a specific types of diagraph with no cycles, referred to as a directed acyclic graph (DAG). In a DAG, the absence of cycles ensures that there is a clear topological ordering of tasks or components. This is demonstrated in the next example.
Example 9.22
Define a DAG [latex]G[/latex] with the following vertices and directed edges.
The vertex labels represent [latex]A =[/latex] Start, [latex]B =[/latex] Task 1, [latex]C[/latex] = Task 2, [latex]D =[/latex] Task 3, and [latex]E =[/latex] Final Task. [latex]G[/latex] is a DAG because all edges have a direction and there are no cycles. This DAG could represent a task dependency graph in a project. [latex]A[/latex] is the starting point, [latex]B[/latex] and [latex]C[/latex] are parallel tasks that can begin after [latex]A[/latex], [latex]D[/latex] depends on both [latex]B[/latex] and [latex]C[/latex] being completed, and [latex]E[/latex] is the final task that depends on [latex]D[/latex].
The last theorem for this section is important because it enables topological sorting (ordering the vertices of a DAG), guarantees termination in recursive algorithms, supports efficient graph traversal and analysis, and is critical in modelling real-world systems.
Theorem 9.6: Terminal Vertex Theorem
A DAG contains at least one vertex with outdegree zero.
Proof
For the purposes of contradiction, suppose all vertices have outgoing edges, that is, an edge leaves every vertex. Then, when travelling between vertices, you will eventually revisit a vertex, which is a cycle. This is a contradiction.
[latex]\square[/latex]
Real-World Example 9.3: Task Management System in a Software Company
Suppose you work for a software company that uses a task management system to coordinate work across teams. The tasks for each team are represented as vertices, and a directed edge from one task to another indicates that the first task must be completed before the next can begin. The software company has been assigned the following tasks:
- Set up development environment
- Design database schema
- Implement backend Application Programming Interface (API)
- Build frontend interface
- Integrate frontend with backend
- Perform testing
- Deploy to production
The directed graph is as follows:
Computing the indegrees and outdegrees gives
[latex]\text{in}(A) = 0[/latex], [latex]\text{in}(B) = \text{in}(C) = \text{in}(D) = \text{in}(F) = \text{in}(G) = 1[/latex], [latex]\text{in}(E) = 2[/latex]
[latex]\text{out}(A) = 2[/latex], [latex]\text{out}(B) = \text{out}(C) = \text{out}(D) = \text{out}(E) = \text{out}(F) = 1[/latex], [latex]\text{out}(G) = 0[/latex]
This graph is a DAG because all edges have direction and there are no cycles. If someone mistakenly adds an edge [latex]GA[/latex], it will create a cycle. This graph does not have a directed Euler cycle, because not all vertices have equal indegree and outdegree.
