We define a new graph operator, called the weak-factor graph, which comes from the context of complex network modelling. The weak-factor operator is close to the well-known clique-graph operator but it rather operates in terms of bicliques in a multipartite graph. We address the problem of the termination of the series of graphs obtained by iteratively applying the weak-factor operator starting from a given input graph. As for the clique-graph operator, it turns out that some graphs give rise to series that do not terminate. Therefore, we design a slight variation of the weak-factor operator, called clean-factor, and prove that its associated series terminates for all input graphs. In addition, we show that the multipartite graph on which the series terminates has a very nice combinatorial structure: we exhibit a bijection between its vertices and the chains of the inclusion order on the intersections of the maximal cliques of the input graph.
翻译:我们定义了一个新的图形运算符, 称为微因子图, 它来自复杂的网络建模背景。 弱因子运算符接近著名的区划运算符, 但它却在多部分图中以双项操作方式运行。 我们从一个输入图中迭接地应用微因子运算符, 从而解决了终止一系列图的问题。 至于分类算运算符, 某些图表产生了一系列不终止的序列。 因此, 我们设计了一个微微因子运算符, 叫做清洁因子, 并证明其相关的序列终止了所有输入图。 此外, 我们展示了该序列终止的多部分图有一个非常好的组合结构: 我们展示了该序列结束的多部分图的组合结构: 在输入图的最大圆柱的交汇点和输入图的最大圆链链的交叉点之间有一个分母。