论文标题
加权图的展开和覆盖物
Unfoldings and coverings of weighted graphs
论文作者
论文摘要
无向图的覆盖物用于分布式计算，以及程序语义中的有向图的展开。我们从图理论的角度研究了这两个概念，以突出它们的相似性，因为它们都是根据五幅图形同态定义的。特别是，如果初始图是有限的，则通用覆盖物和完整的展开是无限的树木。规律性意味着一棵树有限的许多子树，直到同构。 Leighton和Norris为掩护建立了两个重要的定理。我们证明了相似的陈述。 我们对Leighton定理的难以证明的研究使我们通过将有限或无限的重量附加到覆盖或展开的图表的边缘，从而使我们概括了覆盖物，并通过类似地进行展开。这种概括得出了任何有限图的通用覆盖物的规范分解，如果不使用权重，就不存在（证明）。引入无限的重量为我们提供了有限的定期树，具有无数度的淋巴结。我们还推广到加权图及其覆盖范围的特征多项式定理。
Coverings of undirected graphs are used in distributed computing, and unfoldings of directed graphs in semantics of programs. We study these two notions from a graph theoretical point of view so as to highlight their similarities, as they are both defined in terms of surjective graph homomorphisms. In particular, universal coverings and complete unfoldings are infinite trees that are regular if the initial graphs are finite. Regularity means that a tree has finitely many subtrees up to isomorphism. Two important theorems have been established by Leighton and Norris for coverings. We prove similar statements for unfoldings. Our study of the difficult proof of Leighton's Theorem lead us to generalize coverings and similarly, unfoldings, by attaching finite or infinite weights to edges of the covered or unfolded graphs. This generalization yields a canonical factorization of the universal covering of any finite graph, that (provably) does not exist without using weights. Introducing infinite weights provides us with finite descriptions of regular trees having nodes of countably infinite degree. We also generalize to weighted graphs and their coverings a classical factorization theorem of their characteristic polynomials.
