Voir la notice de l'article provenant de la source Numdam
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.
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.
@article{MSH_1999__146__5_0,
author = {Berry, Anne and Bordat, Jean-Paul},
title = {Orthotreillis et s\'eparabilit\'e dans un graphe non orient\'e},
journal = {Math\'ematiques informatique et sciences humaines},
pages = {5--17},
publisher = {Ecole des hautes-\'etudes en sciences sociales},
volume = {146},
year = {1999},
mrnumber = {1707208},
language = {fr},
url = {http://geodesic.mathdoc.fr/item/MSH_1999__146__5_0/}
}
TY - JOUR AU - Berry, Anne AU - Bordat, Jean-Paul TI - Orthotreillis et séparabilité dans un graphe non orienté JO - Mathématiques informatique et sciences humaines PY - 1999 SP - 5 EP - 17 VL - 146 PB - Ecole des hautes-études en sciences sociales UR - http://geodesic.mathdoc.fr/item/MSH_1999__146__5_0/ LA - fr ID - MSH_1999__146__5_0 ER -
%0 Journal Article %A Berry, Anne %A Bordat, Jean-Paul %T Orthotreillis et séparabilité dans un graphe non orienté %J Mathématiques informatique et sciences humaines %D 1999 %P 5-17 %V 146 %I Ecole des hautes-études en sciences sociales %U http://geodesic.mathdoc.fr/item/MSH_1999__146__5_0/ %G fr %F MSH_1999__146__5_0
Berry, Anne; Bordat, Jean-Paul. Orthotreillis et séparabilité dans un graphe non orienté. Mathématiques informatique et sciences humaines, Tome 146 (1999), pp. 5-17. http://geodesic.mathdoc.fr/item/MSH_1999__146__5_0/