主題
Search

標記圖

DOWNLOAD Mathematica Notebook下載 Wolfram 筆記本
LabeledGraphTypes

一個標記圖 G=(V,E) 是一個有限序列的 圖頂點 V，帶有一組 圖邊 E，它是 V 的2-子集。給定一個 圖頂點 集合 V_n={1,2,...,n}，頂點標記圖的數量由 2^(n(n-1)/2) 給出。如果存在一個 置換 p，使得 {u,v} 在 圖邊 E(G) 集合中當且僅當 {p(u),p(v)} 在 圖邊 E(H) 集合中，則稱兩個圖 G 和 H 具有 圖頂點 V_n={1,2,...,n} 是 同構的。

LabeledGraphs

當不加限定地使用術語“標記圖”時，它指的是每個節點都以不同方式（但任意地）標記的圖，因此出於列舉的目的，所有節點都被認為是不同的。對於 n=1, 2, ...，總數（不一定連通）的標記 n 節點圖由 1, 2, 8, 64, 1024, 32768, ... 給出 (OEIS A006125; 如上所示)，而 n 節點上的連通標記圖的數量由前述序列的 對數變換 給出，為 1, 1, 4, 38, 728, 26704, ... (OEIS A001187; Sloane 和 Plouffe 1995, p. 19)。

所有 n=1, 2, ... 階的標記圖中圖頂點的數量為 1, 4, 24, 256, 5120, 196608, ... (OEIS A095340)，其中邊的數量為 0, 1, 12, 192, 5120, 245760, ... (OEIS A095351)，後者具有閉式形式

e(n)=n(n-1)2^(n(n-1)/2-2).

參見

15 拼圖, A-親切圖, 連通圖, 親切圖, 邊優美圖, 優雅圖, 公平圖, 優美圖, 圖, h-親切圖, 調和圖, 標記有向圖, 標記樹, 幻圖, 定向圖, 泰勒條件, 未標記圖, 加權樹

使用 探索

參考文獻

Cahit, I. "圖示記問題和新結果的主頁。" http://www.emu.edu.tr/~cahit/CORDIAL.htm.Gallian, J. "圖示記動態調查。" Elec. J. Combin. DS6. 2018年12月21日。 https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS6.Gilbert, E. N. "標記圖的列舉。" Canad. J. Math. 8, 405-411, 1956.Harary, F. "標記圖。" 圖論。 Reading, MA: Addison-Wesley, pp. 10 和 178-180, 1994.Harary, F. 和 Palmer, E. M. "標記列舉。" Ch. 1 in 圖形列舉。 New York: Academic Press, pp. 1-31, 1973.Sloane, N. J. A. 序列 A001187/M3671, A006125/M1897, A095340 和 A095351，在 "整數序列線上百科全書" 中。Sloane, N. J. A. 和 Plouffe, S. 整數序列百科全書。 San Diego, CA: Academic Press, 1995.

在 上被引用

標記圖

以此引用

Weisstein, Eric W. "標記圖。" 來自 Web 資源。 https://mathworld.tw/LabeledGraph.html

主題分類