Autotransversal
Un article de Wikipédia, l'encyclopédie libre.
 |
Cet article est une ébauche concernant les mathématiques.
Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).
|
Un hypergraphe autotransversal (self-blocking en anglais) est égal à l'ensemble de ses transversales minimales.
Par exemple, une ensemble de mots est un 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)
[modifier] Références
- quelques problèmes concernant les hypergraphes autotransversaux; généralisation des treillis continus, thèse de doctorat de l'université de Perpignan, Flandre Olivier, 1992.côte INIST T 87022
