簡單圖

簡單圖，也稱為嚴格圖（Tutte 1998，第 2 頁），是一個無權、無向的圖，不包含圖環或重邊（Gibbons 1985，第 2 頁；West 2000，第 2 頁；Bronshtein 和 Semendyayev 2004，第 346 頁）。簡單圖可以是連通的或非連通的。

除非另有說明，否則未限定的術語“圖”通常指簡單圖。具有重邊的簡單圖有時稱為多重圖（Skiena 1990，第 89 頁）。

n 個節點上的非同構簡單圖的數量可以由下式給出NumberOfGraphs[n] 在 Wolfram 語言 包中Combinatorica`，並且 n=1, 2, ... 的值是 1, 2, 4, 11, 34, 156, 1044, 12346, 274668, ... (OEIS A000088；參見上圖)。King 和 Palmer（在 Read 1981 中引用）已計算出高達 n=24 的 ，其中

(1)

對於 n 條邊的簡單圖，似乎沒有標準術語，儘管“polynema”（Kyrmse）和“polyedge”（Muñiz 2011）這兩個詞已被提議用於 -邊連通圖。

可以使用以下命令列舉 n 個節點上的所有簡單圖ListGraphs[n] 在 Wolfram 語言 包中Combinatorica`，並且可以透過以下方式獲得最多 n=7 個頂點的預計算列表GraphData[n]。可以使用程式進行更有效的列舉geng（一部分nauty），由 B. McKay 開發。然而，由於程式返回圖的順序geng隨著改進的進行，會隨時間變化，因此此處和以下位置使用了 McKay 網站上給出的規範排序GraphData.

可以在 Wolfram 語言 中測試圖是否為簡單圖，使用SimpleGraphQ[g]。

一個多項式

(2)

它枚舉了具有 個節點的不同圖的數量（其中 是具有 條邊的 個節點上的圖的數量），可以使用 Pólya 列舉定理的相當複雜的應用找到。此過程給出的計數多項式為

(3)

其中 是作用於 的 2-子集的對群，由下式給出

(4)

（Harary 1994，第 185 頁）。這裡， 是向下取整函式， 是二項式係數，LCM 是最小公倍數，GCD 是最大公約數，和 遍佈對稱群 的迴圈指標 的所有指數向量，並且 是 中具有指數向量 的項的係數。前幾個迴圈指標 是

			(5)
			(6)
			(7)
			(8)
			(9)

這些可以透過以下命令給出PairGroup[SymmetricGroup[n]], x] 在 Wolfram 語言 包中Combinatorica`。透過 歸一化並令 ，然後得到 ，其中前幾個是

			(10)
			(11)
			(12)
			(13)
			(14)

這些多項式實現為GraphPolynomial[n, x] 在 Wolfram 語言 包中Combinatorica` .

將 代入其中任何一個都會得到 n 個節點上的簡單圖的總數。可以使用以下命令列舉具有 條邊的 個節點上的所有簡單圖ListGraphs[n, k] 在 Wolfram 語言 包中Combinatorica`。n 個節點和 條邊的非同構簡單圖的數量可以由下式給出NumberOfGraphs[n, k] 在 Wolfram 語言 包中Combinatorica`，具有 個節點和 條邊的圖 的數量陣列如下所示 (OEIS A008406)。

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1	1
2	1	1
3	1	1	1	1
4	1	1	2	3	2	1	1
5	1	1	2	4	6	6	6	4	2	1	1
6	1	1	2	5	9	15	21	24	24	21	15	9	5	2	1	1

具有 個頂點的圖的平均邊數由 給出，對於 n=1, 2, ... 的序列為 0, 1/2, 3/2, 3, 5, 15/2, 21/2, 14, 18, ... (OEIS A064038 和 A014695)。這意味著階數為 , 2, ... 的不同圖中的邊總數是 0, 1, 6, 33, 170, 1170, 10962, 172844, 4944024, 270116280, ... (OEIS A086314)。

上圖顯示了各種常見簡單圖類別的前幾個成員：反稜柱圖、完全圖、圈圖、空圖、齒輪圖、稜柱圖、星圖和輪圖。