pseudograph

A pseudograph is a type of graph that may contain loops and multiple edges between the same pair of vertices. It is a generalization of a simple graph, which has neither loops nor parallel edges.

Formally, a pseudograph G is given by G = (V, E), where V is a set of vertices and E is a multiset of edges. Each edge is either a pair {u, v} with u ≠ v, representing a standard edge between distinct vertices, or a loop {v, v} at a vertex v. Multiple edges between the same vertices are allowed, and a vertex may have more than one loop if loops are permitted.

Key properties include the degree of a vertex, which in a pseudograph counts incidences with all incident edges. A loop contributes 2 to the degree of its incident vertex, while each ordinary edge incident to the vertex contributes 1. Concepts such as paths, cycles, connectivity, and graph totals (like order and size) are defined similarly to simple graphs, but must account for parallel edges and loops.

Relationship to other graph types: a simple graph is a special case of a pseudograph with no loops and no multiple edges. A multigraph allows multiple edges but, in many definitions, excludes loops; when loops are allowed, the structure is typically called a pseudograph. Some authors use the term pseudograph more narrowly or differently, so definitions can vary slightly by context.

Applications and use: pseudographs model networks where multiple relationships can exist between the same entities and where self-relations (loops) may be meaningful, such as social networks with multiple ties, transportation networks with parallel routes, or chemical structures in certain representations.