Autotransversal
- Autotransversal
-
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). 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.
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Autotransversal de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Hypergraphe — Exemple d hypergraphe : V = {v1,v2,v3,v4,v5,v6,v7}, E = {e1,e2,e3,e4} = {{v1,v2,v3},{v2,v3}, {v3,v … Wikipédia en Français
Hypergraphes — Hypergraphe Exemple d hypergraphe: V = {v1,v2,v3,v4,v5,v6,v7}, E = {e1,e2,e3,e4} = {{v1,v2,v3},{v2,v3}, {v3,v5,v6},{v4}}. Les hyperg … Wikipédia en Français
Arete transversale — Arête transversale En théorie des hypergraphes, une transversale est une partie qui rencontre toutes les arêtes de l hypergraphe de départ. L ensemble des transversales est la grille. Un ultrafiltre est donc égal à sa grille ! la grille d un … Wikipédia en Français
Arête Transversale — En théorie des hypergraphes, une transversale est une partie qui rencontre toutes les arêtes de l hypergraphe de départ. L ensemble des transversales est la grille. Un ultrafiltre est donc égal à sa grille ! la grille d un autotransversal… … Wikipédia en Français
Arête transversale — En théorie des hypergraphes, une transversale est une partie qui rencontre toutes les arêtes de l hypergraphe de départ. L ensemble des transversales est la grille. Un ultrafiltre est donc égal à sa grille ! la grille d un autotransversal… … Wikipédia en Français
Hypergraphe autodual — Pour les articles homonymes, voir autodual pour les autres notions d autodualité. Un hypergraphe est autodual si sa matrice est symétrique, ex: (12,13,234,235,145). Pour que la matrice soit symétrique il faut l écrire (145,235,234,13,12). Cet… … Wikipédia en Français
Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… … Wikipédia en Français
