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

Anne Berry; Jean-Paul Bordat

Mathématiques et Sciences Humaines (1999)

  • Volume: 146, page 5-17
  • ISSN: 0987-6936

Abstract

top
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.

How to cite

top

Berry, Anne, and Bordat, Jean-Paul. "Orthotreillis et séparabilité dans un graphe non orienté." Mathématiques et Sciences Humaines 146 (1999): 5-17. <http://eudml.org/doc/94526>.

@article{Berry1999,
abstract = {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.},
author = {Berry, Anne, Bordat, Jean-Paul},
journal = {Mathématiques et Sciences Humaines},
keywords = {Galois lattice; ortholattice; graph; separator; separability lattice},
language = {fre},
pages = {5-17},
publisher = {Ecole des hautes-études en sciences sociales},
title = {Orthotreillis et séparabilité dans un graphe non orienté},
url = {http://eudml.org/doc/94526},
volume = {146},
year = {1999},
}

TY - JOUR
AU - Berry, Anne
AU - Bordat, Jean-Paul
TI - Orthotreillis et séparabilité dans un graphe non orienté
JO - Mathématiques et Sciences Humaines
PY - 1999
PB - Ecole des hautes-études en sciences sociales
VL - 146
SP - 5
EP - 17
AB - 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.
LA - fre
KW - Galois lattice; ortholattice; graph; separator; separability lattice
UR - http://eudml.org/doc/94526
ER -

References

top
  1. [1] Barbut, M., Monjardet, B., Ordre et classification, Paris, Classiques Hachette, 1970. Zbl0267.06001
  2. [2] Berry, A., Bordat, J.-P., "Separability generalizes Dirac's theorem", Discrete Applied Math.84, (1998), 43-53. Zbl0901.05079MR1626534
  3. [3] Berry, A., Bordat, J.-P., Cogis, O.," Generating all the minimal separators of a graph", soumis à WG'99. Zbl0943.05078
  4. [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. [5] Bordat, J.-P., "Sur l'algorithmique combinatoire d'ordres finis", Thèse d'Etat, (1992). 
  6. [6] Bordat, J.P., "Construction du Treillis de Galois d'une relation binaire", Math. et Sci. hum.96, (1986), 31-47. Zbl0626.06007MR878296
  7. [7] Chameni-Nembua, C., Monjardet, B., "Finite pseudocomplemented lattices and 'permutoedre "', Discrete Math.111, (1993), 105-112. Zbl0787.06011MR1210087
  8. [8] Dirac, G.A., "On rigid circuit graphs", Abh. Math. Sem. Univ. Hamburg25, (1961), 71-76. Zbl0098.14703MR130190
  9. [9] Escalante, F., "Schnittverbände in Graphen", Abh. Math. Sem. Hamburg38, (1972), 199-220. Zbl0239.05131MR314698
  10. [10] Guénoche, A., "Calcul pratique du treillis de Galois d'une correspondance", Math. Inf. Sci. hum.121, (1990), 23-34. 
  11. [11] Halin, R., "Lattices of cuts in graphs", Abh. Math. Sem. Univ. Hamburg61, (1991), 217-230. Zbl0770.05092MR1138288
  12. [12] Maeda, F., Maeda, S., Theory of Symmetric Lattices, BerlinHeidelbergNew York, Springer-Verlag, 1970. Zbl0219.06002MR282889
  13. [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. Zbl0785.06004MR1231408
  14. [14] Walker, J.W., "From graphs to ortholattices and equivariant maps", Journ. of Comb. Theory, ser. B, 35, (1983), 171-192. Zbl0509.05059MR733022
  15. [15] Zapatrin, R.R., "Graph representation of finite ortholattices ", Proc. 2nd Winter School on Measure Theory, Lipovsky, (1990), 213-218. Zbl0729.06006MR1118432

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.