Multigráfok

Multigráfok, also known as pseudographs, are a generalization of simple graphs where multiple edges are allowed between the same two vertices and loops (edges connecting a vertex to itself) are also permitted. In a simple graph, there is at most one edge between any pair of distinct vertices and no loops. Multigráfok relax these restrictions.

The definition of a multigráf involves a set of vertices V and a multiset of edges E. An edge in E is an unordered pair of vertices {u, v}, where u and v are in V. The use of a multiset for E allows for repeated edges. If an edge connects a vertex to itself, it is called a loop.

Multigráfok find applications in various fields. For instance, in network analysis, parallel connections between two nodes can be represented by multiple edges. In image processing, loops might represent self-referential features. In combinatorics, they provide a richer structure for studying graph properties.

When analyzing multigráfok, concepts like degree of a vertex are adjusted. The degree of a vertex in a multigráf is the number of edges incident to it, with loops counted twice. The sum of degrees in any multigráf is equal to twice the number of edges, a property known as the handshaking lemma, which still holds true. Algorithms for simple graphs can often be adapted to work with multigráfok, though the presence of multiple edges and loops may require modifications to handle the increased complexity.