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 :

  1. chaque paire de mots a au moins une lettre en commun ;
  2. chaque mot est minimal (si on lui ôte une lettre la première propriété n'est plus vérifiée) ;
  3. 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

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”