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

Mathématiques et sciences humaines. Mathematics and social sciences

Bordat, Jean-Paul¹  Berry, Anne¹ 

关键词: separator;    separability lattice;    graph;    Galois lattice;    ortholattice;   

DOI  :  10.4000/msh.2786

学科分类：数学（综合）

来源: College de France * Ecole des Hautes Etudes en Sciences Sociales (E H E S 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 orthocom-plemented lattices.

【 授权许可】

Unknown