论文标题
关于图的顶点子集的活动和分区
On the Activities and Partitions of the Vertex Subsets of Graphs
论文作者
论文摘要
Crapo引入了布尔晶格的间隔分区的构造，用于配备具有矩形结构的套件。在图形矩阵的背景下，这种构建与图特提出的边缘活动的概念有关。这意味着可以通过删除独特的内部活动边缘的唯一子集并添加外部活动边缘的唯一子集来从一个跨越树的边缘构建连接图的每个跨度子图。由于顶点独立集合的家族不会引起矩阵结构，因此当使用独立集的家族作为生成集时，我们无法在顶点组上应用Crapo的构造。在本文中，我们介绍了顶点活动的概念，以解决顶点集合布尔晶格的间隔分区的问题。我们展示了如何生成封面，呈现与某些特殊最大独立集的顶点活动相关的一些属性，并考虑一些特殊的图表。最后，我们将在修剪图中显示级别的标记始终生成一个分区。
Crapo introduced a construction of interval partitions of the Boolean lattice for sets equipped with matroid structure. This construction, in the context of graphic matroids, is related to the notion of edge activities introduced by Tutte. This implies that each spanning subgraph of a connected graph can be constructed from edges of exactly one spanning tree by deleting a unique subset of internally active edges and adding a unique subset of externally active edges. Since the family of vertex independent sets does not give rise to a matroid structure we can not apply Crapo's construction on the vertex set when using the family of independent sets as generating sets. In this paper, we introduce the concept of vertex activities to tackle the problem of generating interval partitions of the Boolean lattice of the vertex set. We show how to generate a cover, present some properties related to vertex activities of some special maximal independent sets and consider some special graphs. Finally, we will show that level labellings in pruned graphs always generate a partition.
