Arête transversale

En théorie des hypergraphes, une transversale est une partie des sommets qui rencontre toutes les arêtes d'un hypergraphe. L'ensemble des transversales est la grille. C'est l'analogue du problème de couverture par sommets (vertex cover en anglais) chez les graphes. On rappelle qu'un hypergraphe est un couple où est un ensemble de sommets, et une famille de sous-ensembles de qu'on nomme arêtes, ou hyperarêtes. Une transversale de est un ensemble tel que pour toute arête appartenant à , . Le nombre de transversalité d'un hypergraphe est la taille d'une plus petite transversale de . Il est souvent noté Par exemple, si est l'hypergraphe défini par et , alors admet plusieurs transversales de taille 2 (par exemple ou ) et aucune de taille 1 (car aucun sommet n'appartient à toutes les arêtes). Son nombre de transversalité vaut donc 2. Un sommet d'une transversale est dit non-redondant s'il existe une arête de l'hypergraphe de départ dont l'intersection avec cette transversale est réduite au sommet considéré. Autrement dit, un sommet d'une transversale associée à un hypergraphe est non-redondant s'il vérifie : Intuitivement, la redondance d'un sommet équivaut à la transversalité de l'ensemble de sommets . En effet, si est redondant, alors pour toute hyperarête : si alors , et si alors il existe un élément tel que car est redondant. On a alors . Réciproquement, si est une transversale, alors est forcément redondant car s'il existait tel que , alors on aurait et ne serait pas une transversale. Une transversale est dite minimale (ou non-redondante) si aucun de ses sous-ensembles n'est également une transversale, ce qui est équivalent à dire qu'aucun de ses sommets n'est redondant. En effet : on a vu au paragraphe précédent que si l'un de ses sommets était redondant on disposerait d'un sous-ensemble transversal, et si l'on disposait d'un sous-ensemble transversal on pourrait montrer que tout sommet de est redondant (la démonstration est très similaire à celle du paragraphe précédent).