主題
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.tw/Series-ParallelGraph.html

主題分類