Orthotreillis et séparabilité dans un graphe non orienté
Mathématiques informatique et sciences humaines, Tome 146 (1999), pp. 5-17.

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.

Mot clés : treillis de Galois, orthotreillis, graphe, séparateur, treillis de séparabilité
Mots-clés : Galois lattice, ortholattice, graph, separator, separability lattice 
@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://archive.numdam.org/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://archive.numdam.org/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://archive.numdam.org/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://archive.numdam.org/item/MSH_1999__146__5_0/

[1] Barbut, M., Monjardet, B., Ordre et classification, Paris, Classiques Hachette, 1970. | Zbl

[2] Berry, A., Bordat, J.-P., "Separability generalizes Dirac's theorem", Discrete Applied Math. 84, (1998), 43-53. | MR | Zbl

[3] Berry, A., Bordat, J.-P., Cogis, O.," Generating all the minimal separators of a graph", soumis à WG'99. | Zbl

[4] Booth, K.S., Colbourn, C.-J., "Problems polynomially equivalent to graph isomorphism", TR CS-77, D4, Dept. of Computer Science, Univ. of Waterloo, (1979).

[5] Bordat, J.-P., "Sur l'algorithmique combinatoire d'ordres finis", Thèse d'Etat, (1992).

[6] Bordat, J.P., "Construction du Treillis de Galois d'une relation binaire", Math. et Sci. hum. 96, (1986), 31-47. | Numdam | MR | Zbl

[7] Chameni-Nembua, C., Monjardet, B., "Finite pseudocomplemented lattices and 'permutoedre "', Discrete Math. 111, (1993), 105-112. | MR | Zbl

[8] Dirac, G.A., "On rigid circuit graphs", Abh. Math. Sem. Univ. Hamburg 25, (1961), 71-76. | MR | Zbl

[9] Escalante, F., "Schnittverbände in Graphen", Abh. Math. Sem. Hamburg 38, (1972), 199-220. | MR | Zbl

[10] Guénoche, A., "Calcul pratique du treillis de Galois d'une correspondance", Math. Inf. Sci. hum. 121, (1990), 23-34.

[11] Halin, R., "Lattices of cuts in graphs", Abh. Math. Sem. Univ. Hamburg 61, (1991), 217-230. | MR | Zbl

[12] Maeda, F., Maeda, S., Theory of Symmetric Lattices, Berlin Heidelberg New York, Springer-Verlag, 1970. | MR | Zbl

[13] Morvan, M., Nourine, L., "Sur la distributivité du treillis des antichaînes maximales d'un ensemble ordonné", C. R. Acad.Sci. Paris, t. 317, Série I, (1993), 129-133. | MR | Zbl

[14] Walker, J.W., "From graphs to ortholattices and equivariant maps", Journ. of Comb. Theory, ser. B, 35, (1983), 171-192. | MR | Zbl

[15] Zapatrin, R.R., "Graph representation of finite ortholattices ", Proc. 2nd Winter School on Measure Theory, Lipovsky, (1990), 213-218. | MR | Zbl