# 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.

## Features of Digraphs

• 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.

## Paths and Cycles in Digraphs

• 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.

## Special Digraphs

• 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.

## Applications of 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.

## Digraph Theorems

• 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.