Hypergraphe autotransversal
Un hypergraphe autotransversal (self-blocking en anglais) est un hypergraphe qui est égal à l'ensemble de ses arêtes transversales minimales.
Par exemple, un ensemble de mots est un hypergraphe autotransversal s'il a les propriétés suivantes :
- chaque paire de mots a au moins une lettre en commun ;
- chaque mot est minimal (si on lui ôte une lettre la première propriété n'est plus vérifiée) ;
- si on pioche une lettre dans chaque mot l'ensemble obtenu doit contenir un mot du groupe.
On peut remarquer que ce groupe de mots est un hypergraphe intersectant non bicolorable.
Voici deux autotransversaux qui sont 3-uniformes :
- (eau, réa, êta, rua, tua, rue, tue, rut, rat, ter) (ordre 5) ;
- (eau, rat, tua, set, sur, sût, rut, ras, sua, tas) (ordre 6).
Voici encore un exemple :
- (riens, site, tire, nets, tirs, ras, tas, tan, êta, ait, rat, ais, aïe, réa, ase, nia) (ordre 7).
- bien plus dur: le plan projectif (ordre 7):(eau, sel, pie, ais, pal, pus, lui). c'est le seul plan projectif qui soit autotransversal.
Références
- Olivier Flandre, Quelques problèmes concernant les hypergraphes autotransversaux; généralisation des treillis continus, Thèse de doctorat de l'université de Perpignan, 1992, cote INIST T 87022.
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.