Orthotreillis et séparabilité dans un graphe non orienté
Berry, Anne ; Bordat, Jean-Paul
Mathématiques et Sciences humaines, Tome 147 (1999), p. 5-17 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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.

Publié le : 1999-01-01
Mots clés: treillis de Galois, orthotreillis, graphe, séparateur, treillis de séparabilité 
@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 et Sciences humaines},
     volume = {147},
     year = {1999},
     pages = {5-17},
     mrnumber = {1707208},
     language = {fr},
     url = {http://dml.mathdoc.fr/item/MSH_1999__146__5_0}
}

Berry, Anne; Bordat, Jean-Paul. Orthotreillis et séparabilité dans un graphe non orienté. Mathématiques et Sciences humaines, Tome 147 (1999) pp. 5-17. http://gdmltest.u-ga.fr/item/MSH_1999__146__5_0/

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

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

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

[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 878296 | Zbl 0626.06007

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

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

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

[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 1138288 | Zbl 0770.05092

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

[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 1231408 | Zbl 0785.06004

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

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