Digraphs

Understanding Digraphs

  • A digraph or directed graph is a type of graph that is made up of vertices and directed edges often called arcs.
  • Unlike an edge in an undirected graph, an arc has an orientation, meaning it goes from one vertex, known as the initial vertex, to another vertex, the terminal vertex.
  • If a vertex has arcs directed away from it, those arcs are called outgoing arcs, and the vertex is the initial vertex for those arcs.
  • Conversely, if a vertex has arcs directed towards it, those arcs are called incoming arcs, and the vertex is the terminal vertex for those arcs.
  • The outdegree of a vertex is the number of outgoing arcs from it, while the indegree is the number of incoming arcs to it.

Special Types of Digraphs

  • A simple digraph is a digraph which has no loops (arcs starting and ending at the same vertex) and at most one arc between any ordered pair of vertices.
  • An acyclic digraph or DAG(Directed Acyclic Graph) is a digraph with no directed cycles. That is, it is impossible to start at a vertex v and follow a consistently-directed sequence of arcs that eventually loops back to v again.
  • A weighted digraph is a digraph where each arc has a weight, or numerical value, associated with it. This weight could represent a variety of different things, for example, the cost to move from one vertex to another.

Traversals in Digraphs

  • Euler paths and cycles are possible in digraphs just as in undirected graphs. An Eulerian circuit in a digraph is a directed circuit that uses every arc exactly once.
  • For a strongly-connected digraph to contain an Euler circuit, every vertex must have equal indegree and outdegree.
  • Traversing a directed graph is done using algorithms such as depth-first search (DFS) and breadth-first search (BFS).

Properties of Digraphs

  • The sum of the indegrees of all of the vertices in a digraph is equal to the sum of the outdegrees, which is also equal to the number of arcs.
  • A strongly connected digraph is a digraph where there is a directed path from any vertex to every other vertex.
  • In a digraph, the shortest path from a vertex to another (based on the sum of weights, if it is a weighted digraph) can be found using algorithms like the Dijkstra’s algorithm.