主题
Search

串并联图


在组合数学中,串并联网络问题要求计算可以使用给定数量的边形成的网络的数量。边可以是可区分的或不可区分的。

当边不可区分时,考虑枚举在 n 条边上拓扑不同的网络的数量问题,其中允许多条边。 想法是通过将网络分类为本质上是串联和本质上是并联网络来分解问题。

1. “本质上是串联网络”是可以分解为两个或多个串联“子网络”的网络。

2. “本质上是并联网络”是可以分解为两个或多个并联“子网络”的网络。

通过网络的对偶性,可以证明本质上是串联网络的数量等于本质上是并联网络的数量。 因此,对于所有 n>1n 条边中的网络数量是本质上是串联网络数量的两倍。 对于 n=1,网络数量为 1。

a_n 定义为 n 条不可区分的边上的串并联网络的数量,将 b_n 定义为本质上是串联网络的数量。 然后

 a_n={1   if n=1; 2b_n   otherwise.
(1)

b_n 可以通过枚举 n 的分partitions来找到。 考虑 n 的一个分partition {p_i},即,

 sum_(i)ip_i=n.
(2)

那么,本质上是串联网络的数量可以计算为 product_(i)(b_i+p_i-1; i)。 因此

 b_n=sum_(p_i)product_(i)(b_i+p_i-1; i),
(3)

其中,求和是对 n 的所有分partitions p_i 进行的,不包括平凡分partition {0,0,...,n}。 这给出了一个用于计算 b_n 的递归,由此可以如上计算 a_n

此外,该序列满足

 product_(k=1)^infty1/((1-x^k)^(b_k))=1+sum_(k=1)^inftya_kx^k,
(4)

或更明确地,

 1/(1-x)product_(k=2)^infty1/((1-x^k)^(a_k))=1+sum_(k=1)^inftya_kx^k.
(5)

a_n 对于 n=1, 2, ... 的前几个值是 1, 2, 4, 10, 24, 66, 180, 522, 1532, 4624, ... (OEIS A000084),而 b_n 的前几个值是 1, 1, 2, 5, 12, 33, 90, 261, 766, 2312, ... (OEIS A000669)。

Valdes (1978) 表明,偏序集是串并联的,当且仅当其可比性图是 cograph。


另请参阅

Cograph

此条目的部分内容由 Rajsekar 贡献

使用 探索

参考文献

Ellis-Monaghan, J. A. 和 Merino, C. “图多项式及其应用 I:Tutte 多项式。” 2008 年 6 月 28 日。 http://arxiv.org/abs/0803.3079Eppstein, D. “串并联图的并行识别。”Information and Computation 98, 41-55, 1992.Finch, S. “串并联网络。” 2003 年 7 月 7 日。 http://algo.inria.fr/bsolve/Sloane, N. J. A. 序列 A000084A000669,出自“整数序列在线百科全书”。Valdes, J. “解析流程图和串并联图。” 博士论文。 也是技术报告 STAN-CS-78-682,计算机科学系。 加利福尼亚州斯坦福:斯坦福大学,1978 年。

引用为

RajsekarWeisstein, Eric W. “串并联图。” 来自 —— 资源。 https://mathworld.net.cn/Series-ParallelGraph.html

主题分类