Ê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
Arête transversale
Résumé
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).
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.