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.