主题
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.net.cn/SierpinskiGasketGraph.html

主题分类