Mathématiques et sciences humaines/Mathematics and social sciences

n° 146, Été 1999

Version imprimable   Signaler cette page  

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

Ortholattices and separability in undirected graphs

Anne Berry et Jean-paul Bordat

Résumé

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.

Abstract

We present a generalization of minimal separation in an undirected graph, and show how the maximal rectangles of the adjacency matrix describe such separators, and form an ortholattice, which we call the Separability Lattice. Furthermore, for any given ortholattice L, we show that there does not exist a unique minimal graph of which L is the Separability Lattice. We establish a necessary and sufficient condition for the existence of such a graph. The end of the paper deals with algorithmic considerations on the class of orthocom-plemented lattices.

Index

Pour citer cet article

Anne Berry et Jean-paul Bordat, « Orthotreillis et séparabilité dans un graphe non orienté », Mathématiques et sciences humaines, n° 146, Été 1999, [En ligne], mis en ligne le 10 février 2006. URL : http://msh.revues.org/document2786.html. Consulté le 16 mai 2008.

 
Page générée par Lodel - Nous adhérons à www.revues.org

ISSN : 0987 6936
Ecole des hautes études en sciences sociales