论文标题
无向图的循环的晶格
The lattice of cycles of an undirected graph
论文作者
论文摘要
我们研究由无向图的循环产生的晶格的基础，该循环定义为循环0/1构成矢量的整数线性组合。我们证明了该晶格的结构性结果，包括其尺寸和决定因素的显式公式，并且我们提出有效的算法来构建晶格碱基，仅在二次时段使用循环作为发电机。根据代数考虑，我们将这些结果与更通用的设置与任意阿贝尔组的系数联系起来。我们的结果将图形循环的向量空间概括为在二进制字段上的矢量空间到任意场的情况。
We study bases of the lattice generated by the cycles of an undirected graph, defined as the integer linear combinations of the 0/1-incidence vectors of cycles. We prove structural results for this lattice, including explicit formulas for its dimension and determinant, and we present efficient algorithms to construct lattice bases, using only cycles as generators, in quadratic time. By algebraic considerations, we relate these results to the more general setting with coefficients from an arbitrary Abelian group. Our results generalize classical results for the vector space of cycles of a graph over the binary field to the case of an arbitrary field.
