论文标题
通过Draconian序列计算邻接多面体的体积
Computing Volumes of Adjacency Polytopes via Draconian Sequences
论文作者
论文摘要
在复杂网络中非线性新兴现象的研究中，邻接多面体自然出现。 “ pq-type”邻接多层，表示为$ \ nabla^{\ mathrm {pq}} _ g $，这是这项工作的重点，它编码了有关电力工程中研究的稀疏电力网络中有关电力流溶液的丰富组合信息。这种相邻多层的归一化体积特别重要，该体积在不同的电流溶液的数量上提供了上限。 在本文中，我们表明，计算$ \ nabla^{\ mathrm {pq}} _ g $的归一量化量的问题可以重新分配为计数$ d（g）$ - draconian序列，其中$ d（g）$是与网络相关的某些品牌图。我们证明了所有连接性最多$ 1 $的网络的复发，并且在某些限制下以$ 2 $连接的图表，我们会重复出现，以划分边缘，并使用新的顶点进行边缘连接。这些复发在一起意味着，当$ \ nabla^{\ mathrm {pq}}} _ g $的归一量化卷是一个简单的，非恢复的公式。我们猜想该公式适用于所有外平面图。给出了其他几个（非欧特平台）类的明确公式。此外，我们确定了几个重要的图表$ g $，这些图形是平面，而不是外部平面的，值得进行额外的研究。
Adjacency polytopes appear naturally in the study of nonlinear emergent phenomena in complex networks. The "PQ-type" adjacency polytope, denoted $\nabla^{\mathrm{PQ}}_G$ and which is the focus of this work, encodes rich combinatorial information about power-flow solutions in sparse power networks that are studied in electric engineering. Of particular importance is the normalized volume of such an adjacency polytope, which provides an upper bound on the number of distinct power-flow solutions. In this article we show that the problem of computing normalized volumes for $\nabla^{\mathrm{PQ}}_G$ can be rephrased as counting $D(G)$-draconian sequences where $D(G)$ is a certain bipartite graph associated to the network. We prove recurrences for all networks with connectivity at most $1$ and, for $2$-connected graphs under certain restrictions, we give recurrences for subdividing an edge and taking the join of an edge with a new vertex. Together, these recurrences imply a simple, non-recursive formula for the normalized volume of $\nabla^{\mathrm{PQ}}_G$ when $G$ is part of a large class of outerplanar graphs; we conjecture that the formula holds for all outerplanar graphs. Explicit formulas for several other (non-outerplanar) classes are given. Further, we identify several important classes of graphs $G$ which are planar but not outerplanar that are worth additional study.
