主題
Search

無環有向圖

下載 Mathematica 筆記本下載 Wolfram 筆記本
AcyclicDigraphs

無環有向圖是一個有向圖，不包含有向環，也稱為有向無環圖或“DAG”。每個有限無環有向圖至少有一個出度為 0 的節點。頂點數為 n=1, 2, ... 的無環有向圖的數量分別是 1, 2, 6, 31, 302, 5984, ... (OEIS A003087)。

頂點數為 n=1, 2, ... 的標記無環有向圖的數量分別是 1, 3, 25, 543, 29281, ... (OEIS A003024)。 韋斯坦因猜想 提出 正特徵值 (0,1)-矩陣與頂點數為 n 的標記無環有向圖之間存在一一對應關係，隨後 McKay et al. (2004) 證明了這一點。因此，兩者的計數都由美麗的遞推方程給出

a_n=sum_(k=1)^n(-1)^(k-1)(n; k)2^(k(n-k))a_(n-k)

其中 a_0=1 (Harary and Palmer 1973, p. 19; Robinson 1973, pp. 239-273)。

另請參閱

森林, 超串, 正特徵值矩陣, 簡單有向圖, 韋斯坦因猜想

使用 探索

參考文獻

Harary, F. 圖論。 Reading, MA: Addison-Wesley, p. 200, 1994.Harary, F. 和 Palmer, E. M. "無環有向圖。" §8.8 in 圖形計數。 New York: Academic Press, pp. 191-194, 1973.McKay, B. D.; Royle, G. F.; Wanless, I. M.; Oggier, F. E.; Sloane, N. J. A.; 和 Wilf, H. "無環有向圖和 (0,1)-矩陣的特徵值。" J. Integer Sequences 7, Article 04.3.3, 1-5, 2004. http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Sloane/sloane15.html.Robinson, R. W. "標記無環有向圖的計數。" In 圖論新方向 (Ed. F. Harary). New York: Academic Press, 1973.Robinson, R. W. "未標記無環有向圖的計數。" In 組合數學 V：第五屆澳大利亞會議論文集，於 1976 年 8 月 24-26 日在皇家墨爾本理工學院舉行)。 Providence, RI: Amer. Math. Soc., pp. 28-43, 1976.Sloane, N. J. A. 序列 A003087/M1696 in "整數序列線上百科全書。"

在 上被引用

無環有向圖

引用此內容為

韋斯坦因，埃裡克·W. "無環有向圖。" 來自 Web 資源。 https://mathworld.tw/AcyclicDigraph.html

主題分類