主題
Search

構造數


設圖 G=(V,E) 定義在頂點集 V邊集 E 上。則圖 G 的構造序列(或 c-序列)是 V union E 上的線性順序,其中每條邊都出現在其兩個端點之後。圖 c(G) 的構造數 G 定義為圖 G 的不同構造序列的數量 (Kainen 2023)。

PathGraphP3

例如,對於路徑圖 P_3,其頂點集為 1, 2, 3,邊集為 12, 23,共有 16 個可能的構造序列:(1, 2, 3, 12, 23)、(1, 2, 3, 23, 12)、(1, 2, 12, 3, 23)、(1, 3, 2, 12, 23)、(1, 3, 2, 23, 12)、(2, 1, 3, 12, 23)、(2, 1, 3, 23, 12)、(2, 1, 12, 3, 23)、(2, 3, 1, 12, 23)、(2, 3, 1, 23, 12)、(2, 3, 23, 1, 12)、(3, 1, 2, 12, 23)、(3, 1, 2, 23, 12)、(3, 2, 1, 12, 23)、(3, 2, 1, 23, 12)、(3, 2, 23, 1, 12),因此 c(P_3)=16

下表總結了一些引數化圖的構造數(參見 Kainen 2023),其中 (n; k)二項式係數n階乘n!!雙階乘B_(2n)伯努利數,而 Gamma(n)伽瑪函式。Kainen等人 (2023) 提出了確定 c(K_n) 的問題,並由 Tauraso (2024) 解決。


另請參閱

組裝數

使用 探索

參考文獻

Kainen, P. C. "Construction Numbers: How to Build a Graph?" 2023 年 2 月 25 日。 https://arxiv.org/abs/2302.13186.Kainen, P. C.; Strong, R.; 和 Tilley, J. 問題 12401. Amer. Math. Monthly 130, 587, 2023.Sloane, N. J. A. 序列 A000142, A000182, A024255, A055546, A210277, 和 A374928,來自“整數序列線上百科全書”。Tauraso, R. 問題 12401 的解答. Amer. Math. Monthly. 2024. https://www.mat.uniroma2.it/~tauraso/AMM/AMM12401.pdf.

引用為

Weisstein, Eric W. "構造數。" 來自 Web 資源。 https://mathworld.tw/ConstructionNumber.html