Orthotreillis et séparabilité dans un graphe non orienté
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 exi...
Αποθηκεύτηκε σε:
| Τόπος έκδοσης: | URI:https://journals.openedition.org/msh, |
|---|---|
| Κύριοι συγγραφείς: | , |
| Μορφή: | Article ou chapitre numérique |
| Γλώσσα: | Français |
| Έκδοση: |
Mathématiques et sciences humaines
2006
|
| Θέματα: | |
| Διαθέσιμο Online: | Accès Université d'Orléans et IFPM Accès Université d'Orléans et IFPM |
| Περίληψη: | 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 orthocom-plemented lattices. |
|---|