Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Matching in hypergraphs
Résumé
In graph theory, a matching in a hypergraph is a set of hyperedges, in which every two hyperedges are disjoint. It is an extension of the notion of matching in a graph.
Recall that a hypergraph H is a pair (V, E), where V is a set of vertices and E is a set of subsets of V called hyperedges. Each hyperedge may contain one or more vertices.
A matching in H is a subset M of E, such that every two hyperedges e_1 and e_2 in M have an empty intersection (have no vertex in common).
The matching number of a hypergraph H is the largest size of a matching in H. It is often denoted by ν(H).
As an example, let V be the set {1,2,3,4,5,6,7}. Consider a 3-uniform hypergraph on V (a hypergraph in which each hyperedge contains exactly 3 vertices). Let H be a 3-uniform hypergraph with 4 hyperedges:
{ {1,2,3}, {1,4,5}, {4,5,6}, {2,3,6} }
Then H admits several matchings of size 2, for example:
{ {1,2,3}, {4,5,6} }
{ {1,4,5}, {2,3,6} }
However, in any subset of 3 hyperedges, at least two of them intersect, so there is no matching of size 3. Hence, the matching number of H is 2.
A hypergraph H = (V, E) is called intersecting if every two hyperedges in E have a vertex in common. A hypergraph H is intersecting if and only if it has no matching with two or more hyperedges, if and only if ν(H) = 1.
A graph without self-loops is just a 2-uniform hypergraph: each edge can be considered as a set of the two vertices that it connects. For example, this 2-uniform hypergraph represents a graph with 4 vertices {1,2,3,4} and 3 edges:
{ {1,3}, {1,4}, {2,4} }
By the above definition, a matching in a graph is a set M of edges, such that each two edges in M have an empty intersection. This is equivalent to saying that no two edges in M are adjacent to the same vertex; this is exactly the definition of a matching in a graph.
A fractional matching in a hypergraph is a function that assigns a fraction in [0,1] to each hyperedge, such that for every vertex v in V, the sum of fractions of hyperedges containing v is at most 1.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.