# Graphs and Networks: Digraphs

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