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 (mathématiques)|grille[réf. nécessaire]]][Quoi ?]. C'est l'analogue du problème de couverture par sommets (vertex cover en anglais) chez les graphes.
Définitions[modifier | modifier le code]
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[réf. nécessaire] de est un ensemble tel que pour toute arête appartenant à , .
Le nombre de transversalité[réf. nécessaire] d'un hypergraphe est la taille d'une plus petite transversale de . Il est souvent noté
Exemple[modifier | modifier le code]
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.
Sommets redondants d'une transversale[modifier | modifier le code]
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[1]) 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).
Hypergraphe transverse[modifier | modifier le code]
L'ensemble des transversales minimales associées à un hypergraphe forme un hypergraphe appelé hypergraphe transverse.
Le calcul d'un hypergraphe transverse est faisable, à ce jour, en temps [2], étant le cardinal de l'ensemble de sommets.
Algorithme[modifier | modifier le code]
Pseudo-code[modifier | modifier le code]
L'algorithme MTMiner[3],[4] (pour Minimal Transversals Miner) permet de calculer les transversales minimales d'un hypergraphe donné.
Entrée Un hypergraphe Sortie L'ensemble des transversales minimales de Fonction MTMiner() tant que faire : pour tous et tels que : si est non-redondant : si est transversal : Ajouter à sinon : Ajouter à renvoyer
Exemple d'exécution[modifier | modifier le code]
Soit l'hypergraphe formé des sommets , avec pour arêtes . L'exécution se déroule comme suit :
- est initialisé à ;
- est initialisé à ;
- prendra successivement pour valeurs et :
- et sont ajoutées à ,
- et sont ajoutées à ,
- Les autres hyperarêtes sont redondantes ;
- vaut ;
- prendra successivement pour valeurs et :
- est ajoutée à ,
- Les autres hyperarêtes sont redondantes ;
- ;
- L'algorithme renvoie .
Les transversales minimales de sont bien et .
Notes et références[modifier | modifier le code]
- Loïck. Lhote, Exemples d’analyses d’algorithmes en Arithmétique, Théorie de l’Information et Fouille de Données, , 75 p. (lire en ligne)
- (en) Michael L. Fredman et Leonid Khachiyan, « On the Complexity of Dualization of Monotone Disjunctive Normal Forms », Journal of Algorithms, vol. 21, no 3, , p. 618–628 (ISSN 0196-6774, DOI 10.1006/jagm.1996.0062, lire en ligne, consulté le )
- (en) Céline Hébert, Alain Bretto et Bruno Crémilleux, « A data mining formalization to improve hypergraph minimal transversal computation », Fundamenta Informaticae, , p. 415-433
- (en) Julien David, Loïck Lhote, Arnaud Mary et François Rioult, « An average study of hypergraphs and their minimal transversals », Theoretical Computer Science, (DOI 10.1016/j.tcs.2015.06.052)