Ê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
Bipartite hypergraph
Résumé
In graph theory, the term bipartite hypergraph describes several related classes of hypergraphs, all of which are natural generalizations of a bipartite graph.
Property B
The weakest definition of bipartiteness is also called 2-colorability. A hypergraph H = (V, E) is called 2-colorable if its vertex set V can be partitioned into two sets, X and Y, such that each hyperedge meets both X and Y. Equivalently, the vertices of H can be 2-colored so that no hyperedge is monochromatic. Every bipartite graph G = (X+Y, E) is 2-colorable: each edge contains exactly one vertex of X and one vertex of Y, so e.g. X can be colored blue and Y can be colored yellow and no edge is monochromatic.
The property of 2-colorability was first introduced by Felix Bernstein in the context of set families; therefore it is also called Property B.
A stronger definition of bipartiteness is: a hypergraph is called bipartite if its vertex set V can be partitioned into two sets, X and Y, such that each hyperedge contains exactly one element of X. Every bipartite graph is also a bipartite hypergraph.
Every bipartite hypergraph is 2-colorable, but bipartiteness is stronger than 2-colorability. Let H be a hypergraph on the vertices {1, 2, 3, 4} with the following hyperedges:{ {1,2,3} , {1,2,4} , {1,3,4} , {2,3,4} }This H is 2-colorable, for example by the partition X = {1,2} and Y = {3,4}. However, it is not bipartite, since every set X with one element has an empty intersection with one hyperedge, and every set X with two or more elements has an intersection of size 2 or more with at least two hyperedges.
Hall's marriage theorem has been generalized from bipartite graphs to bipartite hypergraphs; see Hall-type theorems for hypergraphs.
An stronger definition is: given an integer n, a hypergraph is called n-uniform if all its hyperedges contain exactly n vertices. An n-uniform hypergraph is called n-partite if its vertex set V can be partitioned into n subsets such that each hyperedge contains exactly one element from each subset.
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.