Multigrafer

Multigrafer is a term used in graph theory to describe a graph that permits more than one edge between the same pair of vertices. In an undirected multigrafer, the edge set is a multiset of unordered pairs of vertices; multiple identical pairs correspond to parallel edges. Loops, edges from a vertex to itself, may be included depending on convention. If loops are excluded, the structure is sometimes called a simple multigrafer, or more commonly just a multigrafer without loops. In many texts the standard English term for this concept is multigraph; multigrafer can appear as a direct translation or in non-English sources.

Directed multigrafer extend the idea to directed edges, or arcs. A pair of vertices may be connected by several parallel arcs, and loops (arcs from a vertex to itself) may also be allowed. The multiplicity of each edge is counted in the size of the edge set, and the graph is often represented as a directed multigraph or pseudodigraph depending on whether loops are permitted.

Representations and basic properties differ from simple graphs. The degree of a vertex in an undirected multigrafer counts multiplicities of incident edges, with loops typically contributing two to the degree. In directed multigrafer, one distinguishes in-degree and out-degree, each counting parallel arcs accordingly. An adjacency representation can track multiplicities: an adjacency matrix entries indicate how many parallel edges connect vertex pairs; an adjacency list records multiplicities for each neighbor.

Applications include modeling networks with parallel connections, such as transportation routes with multiple lines, telecommunications links, or biological networks with redundant interactions. Concepts like paths, cycles, and Eulerian trails generalize to multigrafer by accounting for edge multiplicities.