In our study of the extremities of a graph, we define a moplex as a maximal clique module the neighborhood of which is a minimal separator of the graph. This notion enables us to strengthen Dirac's theorem (Dirac, 1961): "Every non-clique triangulated graph has at least two non-adjacent simplicial vertices", restricting the definition of a simplicial vertex; this also enables us to strengthen Fulkerson and Gross' simplicial elimination scheme; thus provides a new characterization for triangulated graphs. Our version of Dirac's theorem generalizes from the class of triangulated graphs to any undirected graph: "Every non-clique graph has at feast two non-adjacent moplexes". To insure a linear-time access to a moplex in any graph, we use an algorithm due to Rose Tarjan and Lueker (1976) for the recognition of triangulated graphs, known as LexBFS: we prove a new invariant for this, true even on non-triangulated graphs. (C) 1998 Elsevier Science B.V. All rights reserved. [References: 19]
展开▼
机译：在研究图的末端时，我们将复合体定义为最大派系模块，其最大邻域是图的最小分隔符。这一概念使我们能够加强狄拉克定理（狄拉克，1961年）：“每个非三角剖分图都有至少两个不相邻的单纯形顶点”，这限制了单纯形顶点的定义。这也使我们能够加强Fulkerson and Gross的简单消除方案;从而为三角图提供了新的表征。我们的狄拉克定理版本从三角图的类别推广到任何无向图：“每个非自然图都至少有两个不相邻的复形”。为确保线性时间访问任何图中的复合体，我们使用了Rose Tarjan和Lueker（1976）提出的算法来识别三角图，称为LexBFS：我们证明了这一点的新不变性，即使在非连续性上也是如此。三角图。 （C）1998 Elsevier Science B.V.保留所有权利。 [参考：19]
展开▼
