• Aide
  • Eurêkoi Eurêkoi

Article

Orthotreillis et séparabilité dans un graphe non orienté

dans Centre d’analyse et de mathématique sociales de l’EHESS


  • Éditeur(s)
  • Date
    • 2006-02-10T01:00:00Z
  • Notes
    • Nous présentons une généralisation de la notion de séparateur minimal dans un graphe non orienté, et nous montrons que ces séparateurs sont représentés par les rectangles maximaux de la matrice d'adjacence, structurés en un orthotreillis, que nous appelons treillis de séparabilité. Réciproquement, tant donné un orthotreillis, nous montrons qu'il n'existe pas en général un unique graphe minimal dont il serait treillis de séparabilité. Nous donnons une condition nécessaire et suffisante pour que cette dernière propriété soit vérifiée. Le dernier paragraphe de l'article contient des considérations algorithmiques relatives aux treillis orthocomplémentés.
  • Langues
    • Français
  • Sujet(s)
  • Droits
    • info:eu-repo/semantics/openAccess .
    • All rights reserved
  • Résultat de :