Ê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 GraphSearch.
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.
Concepts associés (15)
Rainbow matching
In the mathematical discipline of graph theory, a rainbow matching in an edge-colored graph is a matching in which all the edges have distinct colors. Given an edge-colored graph G = (V,E), a rainbow matching M in G is a set of pairwise non-adjacent edges, that is, no two edges share a common vertex, such that all the edges in the set have distinct colors. A maximum rainbow matching is a rainbow matching that contains the largest possible number of edges. Rainbow matchings are of particular interest given their connection to transversals of Latin squares.
Transversal (combinatorics)
In mathematics, particularly in combinatorics, given a family of sets, here called a collection C, a transversal (also called a cross-section) is a set containing exactly one element from each member of the collection. When the sets of the collection are mutually disjoint, each element of the transversal corresponds to exactly one member of C (the set it is a member of). If the original sets are not disjoint, there are two possibilities for the definition of a transversal: One variation is that there is a bijection f from the transversal to C such that x is an element of f(x) for each x in the transversal.
Matching in hypergraphs
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).
Cours associés (3)
MATH-448: Statistical analysis of network data
A first course in statistical network analysis and applications.
CS-450: Advanced algorithms
A first graduate course in algorithms, this course assumes minimal background, but moves rapidly. The objective is to learn the main techniques of algorithm analysis and design, while building a reper
MATH-467: Probabilistic methods in combinatorics
We develop a sophisticated framework for solving problems in discrete mathematics through the use of randomness (i.e., coin flipping). This includes constructing mathematical structures with unexpecte
Séances de cours associées (33)
Configurations tactiques : Rdl NibbleMATH-467: Probabilistic methods in combinatorics
Explore les configurations tactiques, couvrant la taille minimale des sous-ensembles nécessaires pour couvrir les ensembles d'éléments et le concept de K-sets et de points de base.
Définir les couvertures et les théorèmes d'uniformitéMATH-467: Probabilistic methods in combinatorics
Explore les couvertures fixes et les théorèmes d'uniformité dans les hypergraphes, révélant des aperçus de leurs structures.
L’IA en chimie : Hypergraphe et synthèse rituelle en une seule étapePHYS-754: Lecture series on scientific machine learning
Explore les applications de l'IA dans la chimie, les hypergraphes, la synthèse rituelle en une seule étape et l'évaluation des modèles rétro-synthétiques.