主題
Search

謝爾賓斯基墊片圖

DOWNLOAD Mathematica Notebook下載 Wolfram Notebook
SierpinskiGraph

階為 n 的謝爾賓斯基墊片圖是透過 謝爾賓斯基篩 的連通性獲得的圖。上面展示了前幾個謝爾賓斯基墊片圖。

S_2 也被稱為 Hajós 圖 或 2-太陽圖 (Brandstädt et al. 1987, p. 18)。

其在三維空間中的類似物可以稱為 謝爾賓斯基四面體圖，並且它可以進一步推廣到更高的維度 (D. Knuth, 私人通訊, 2022年5月1日)。

Teguia 和 Godbole (2006) 研究了謝爾賓斯基墊片圖的性質，並證明它們是 哈密頓圖 和 泛圈圖。

圖 S_n 有 3(3^(n-1)-1)/2 個頂點 (OEIS A067771) 和 3^n 條邊 (OEIS A000244; Teguia 和 Godbole 2006)。它的 圖直徑 為 2^(n-1)，支配數 對於 n=1 為 1，對於 n=2 為 2，對於 n>=3 為 3^(n-2) (Teguia 和 Godbole 2006)。

SierpinskiGasketGraphColorings

謝爾賓斯基墊片圖在顏色置換下是 唯一 3-可著色的 (D. Knuth, 私人通訊, 2022年4月11日)，這意味著 S_n 的不同著色數對於所有 n 均為 6=3!，如上面針對 S_2 和 S_3 所示。有趣的是，獨特的著色直接源於這些圖的對稱性，而無需顯式交換顏色。這些圖推廣到更高奇數維度也是唯一可著色的 (D. Knuth, 私人通訊, 2022年5月1日)。

謝爾賓斯基墊片圖在 Wolfram 語言 中實現為GraphData[{"SierpinskiGasket", n}].

另請參閱

Hajós 圖, 河內圖, 謝爾賓斯基地毯圖, 謝爾賓斯基篩, 謝爾賓斯基四面體圖, 太陽圖, 三角網格圖

使用 探索

參考文獻

Brandstädt, A.; Le, V. B.; and Spinrad, J. P. Graph Classes: A Survey. Philadelphia, PA: SIAM, 1987.Hinz, A. M. and Schief, A. "The Average Distance on the Sierpinski Gasket." Probab. Th. Rel. Fields 87, 129-138, 1990.Knuth, D. E. 圖 113, §7.2.2.3 in The Art of Computer Programming, Vol. 4. Pre-Fascicle 7A, 12月 5, p. 41, 2024.Sloane, N. J. A. Sequences A000244/M2807 and A067771 in "The On-Line Encyclopedia of Integer Sequences."Teguia, A. M. and Godbole, A. P. "Sierpiński Gasket Graphs and Some of Their Properties." Australasian J. Combin. 35, 181-192, 2006.

請引用本文為

Weisstein, Eric W. "Sierpiński Gasket Graph." 來自 —— 資源。 https://mathworld.tw/SierpinskiGasketGraph.html

主題分類