Résumé :
Nous présentons une généralisation de la
notion de séparateur minimal dans un graphe non orienté,
et 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.
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 orthocomplemented lattices.