主题
Search

仙人掌图

下载 Mathematica 笔记本下载 Wolfram 笔记本
CactusGraph

仙人掌图，有时也称为仙人掌树、混合 Husimi 树或带桥的多边形仙人掌，是一个连通图，其中任意两个图的环没有公共边。等价地，它是一个连通图，其中任意两个（简单）环最多有一个公共顶点。仙人掌图也可以定义为连通平面图，其中每个块是一个环或一条边（White 2001，第 57 页）。

仙人掌图的每个环都是弦图。然而，存在一些图（例如，theta_0-图和Pasch 图），它们的环都是弦图，但它们不是仙人掌图。

不等式

mu(G)=nu(G),

其中 mu 是环秩，nu 是无向图的环的总数，对于连通图 G 成立，当且仅当它是仙人掌图（Volkmann 1996）。

每个仙人掌图都是一个单位距离图（Erdős et al. 1965）。

每个伪树都是仙人掌图。

节点数为 1, 2, ... 的仙人掌图的数量为 1, 1, 2, 4, 9, 23, 63, 188, ... (OEIS A000083)。

另请参阅

弦图环, 图的环, 伪树, 树, 单位距离图

使用 探索

参考文献

Bona, M.; Bousquet, M.; Labelle, G.; 和 Leroux, P. "m-ary 仙人掌的枚举。" Adv. Appl. Math. 24, 22-56, 2000.Chao, C. Y. 和 Whitehead, E. G. Jr. "关于图的色等价性。" 在 图论及其应用（Proc. Internat. Conf., Western Mich. Univ., Kalamazoo, Mich., 1976) (Ed. Y. Alavi 和 D. R. Lick). Berlin: Springer-Verlag, pp. 121-131, 1978.Erdős, P.; Harary, F.; 和 Tutte, W. T. "关于图的维数。" Mathematika 12, 118-122, 1965.Ford, G. W. 和 Uhlenbeck, G. E. "图论中的组合问题 III。" Proc. Nat. Acad. Sci. USA 42, 529-535, 1956.Geller, D. 和 Manvel, B. "仙人掌的重构。" Canad. J. Math. 21, 1354-1360, 1969.Harary, F. 和 Uhlenbeck, G. "关于 Husimi 树的数量，I。" Proc. Nat. Acad. Sci. USA 39, 315-322, 1953.Husimi, K. "关于 Mayer 簇积分理论的注释。" J. Chem. Phys. 18, 682-684, 1950.Sloane, N. J. A. 序列 A000083/M1191 在 "整数序列在线百科全书" 中。Soifer, A. 数学着色书：着色数学及其创造者的多彩生活。 New York: Springer, p. 91, 2008.Volkmann, L. "图中环数的估计。" Per. Math. Hungar. 33, 153-161, 1996.White, A. T. "图论中的嵌入问题。" Ch. 6 在 曲面群图：交互与模型 (Ed. A. T. White). Amsterdam, Netherlands: Elsevier, 2001.

在 中被引用

仙人掌图

引用为

Weisstein, Eric W. "仙人掌图。" 来自 MathWorld——Wolfram 网络资源。 https://mathworld.net.cn/CactusGraph.html

主题分类