pseudographs

A pseudograph is a generalized graph in graph theory that may contain loops and multiple edges between the same pair of vertices. This distinguishes it from a simple graph, which has neither loops nor parallel edges. Some authors distinguish between pseudographs and multigraphs, while others use the terms interchangeably; in practice, a pseudograph explicitly allows both loops and parallel edges.

Formally, a pseudograph G is a pair (V, E) where V is a set of vertices and E is a multiset of unordered pairs of vertices from V. A pair {u, v} with u ≠ v represents an edge between u and v, and a pair {v, v} represents a loop at v. Repeated occurrences of the same pair correspond to parallel edges.

Key properties include the degree concept. The degree of a vertex v, denoted deg(v), counts the number of edge-ends incident to v. A loop at v contributes 2 to deg(v). The Handshaking Lemma holds in pseudographs: the sum of the degrees of all vertices equals twice the number of edge-ends, which equals 2|E| when |E| counts each edge as one, including loops.

Representations of pseudographs include the adjacency matrix and adjacency lists. In an adjacency matrix A, the entry A[i][j] equals the number of edges between vertices i and j, and the diagonal entry A[i][i] counts loops at i. In adjacency lists, parallel edges appear as repeated entries, and loops appear as a reference to the vertex itself.

Applications of pseudographs arise in networks with multiple connections or self-connections, such as transportation systems with several routes between locations or models that include feedback loops. They provide a flexible framework for analyzing complex relational structures.