Graphs and Networks: Digraphs

Fundamentals of Digraphs

A digraph, or directed graph, is a graph where each edge has a direction. The edges are displayed as arrows.
The direction of an edge indicates a specific pairwise connection between the vertices.
Vertices are also known as nodes, while edges can be referred to as arcs.
Digraphs can be used to model a bewildering number of phenomena, including traffic flows, social networks, and the structure of the internet, among many others.

A directed edge, or arc, is an ordered pair of vertices. The functions source() and target() return where the edge starts and where it ends, respectively.
In weighted digraphs, each edge has a numerical value associated with it. These values are often referred to as the ‘weights’ of the edges.
In a simple digraph, each pair of distinct vertices is connected by at most one edge in a specific direction.
There are no loops (arcs that start and end on the same node) in a simple digraph.

A path in a digraph is a sequence of vertices where each vertex is connected to the next by an edge with the correct orientation.
A path becomes a cycle if the first node and last node are the same, forming a loop.
A digraph is strongly connected if for every pair of vertices u and v, there is a path from u to v and a path from v to u.
A digraph is weakly connected if it becomes connected when the edge orientations are ignored.

A complete digraph is a strongly connected digraph where every pair of different vertices is connected by a pair of positive directed edges (edges in both directions).
An acyclic digraph (DAG) is a digraph with no directed cycles.
Trees and forests are special cases of acyclic digraphs.

Digraphs are applied in numerous fields, including computer science, where they can represent ordered sequences of events in a computer network, and economics, where they can represent preferences or dominance relations.
Understanding the principles of digraphs will provide a solid foundation for moving onto more complex network theory topics.

The Handshaking Lemma: In any digraph, the sum of the out-degrees of all vertices is equal to the sum of the in-degrees.
The Degree Sequence Theorem: The degree sequence of a digraph is a list of non-negative integers which is the sequence of its vertex degrees. You have to list the in-degree sequence and the out-degree sequence separately.
The Directed Version of Euler’s Theorem: If a digraph has an Eulerian circuit (a circuit that traverses each edge exactly once), then every vertex has equal in-degree and out-degree. And if every vertex in a connected digraph has equal in-degree and out-degree, then the graph has an Eulerian circuit.
The Directed Version of Hamilton’s Theorem: A directed graph may contain a Hamiltonian cycle (a cycle that passes through each vertex exactly once). However, unlike the undirected version, a complete digraph has a Hamiltonian cycle.