pseudodigraph

A pseudodigraph, also called a directed pseudograph or multidigraph, is a directed graph that allows multiple arcs between the same ordered pair of vertices and may include loops (edges from a vertex to itself). It is defined by a pair (V, E) where V is a set of vertices and E is a multiset of arcs, with each arc having an ordered pair (tail, head) of vertices. A loop is an arc with tail equal to head.

If a pseudodigraph has no loops and no parallel arcs, it reduces to a simple directed graph. If it allows multiple arcs but not loops, it is a directed multigraph without loops. Conversely, a directed graph with both parallel arcs and loops is a typical pseudodigraph.

Common representations include adjacency matrices and adjacency lists. In an adjacency matrix A, the entry A[u][v] equals the number of arcs from vertex u to vertex v, so loops contribute to A[u][u]. The out-degree of a vertex u is the sum over all v of A[u][v], and the in-degree of u is the sum over all v of A[v][u]. A loop contributes one to both the in-degree and the out-degree, and thus increases the total degree by two.

Pseudodigraphs are used to model networks with parallel connections and self-connections, such as transportation networks with multiple routes between locations, electrical or transportation circuits, and communication networks with redundant channels. Related concepts include multigraphs (undirected) and directed graphs (without parallel edges or loops). The underlying undirected graph of a pseudodigraph can be obtained by ignoring edge directions and preserving the existence of at least one arc between vertex pairs.