主题
Search


Blocks

块是给定 G极大 连通 子图,它没有割点(West 2000, p. 155)。如果一个块有超过两个顶点,那么它是双连通的。无环图的块是它的孤立点和极大2-连通子图(West 2000, p. 155; Gross and Yellen 2006, p. 241)。上面说明了Harary(1994, p. 26)和West(2000, p. 155)给出的图及其对应的块的例子。

如果一个图 G连通的且没有割点,那么 G 本身被称为一个块(Harary 1994, p. 26; West 2000, p. 155)。

块出现在图论问题中,例如寻找单位距离图连通图图亏格。例如,一个连通图单位距离图当且仅当它的每个块都是单位距离图,并且一个图的图的粗细度是其块的粗细度之和。


另请参阅

割点, 双连通图, 区组设计, 数字块, k-连通图, 正方形多联骨牌

使用 Wolfram|Alpha 探索

参考文献

Aho, A. V.; Hopcroft, J. E.; 和 Ullman, J. D. 计算机算法的设计与分析。 Reading, MA: Addison-Wesley, 1974.Gross, J. T. 和 Yellen, J. 图论及其应用,第 2 版。 Boca Raton, FL: CRC Press, 2006.Harary, F. 图论。 Reading, MA: Addison-Wesley, 1994.Skiena, S. "双连通分量。" §5.1.4 in 离散数学实现:使用 Mathematica 的组合数学和图论。 Reading, MA: Addison-Wesley, pp. 175-177, 1990.West, D. B. 图论导论,第 2 版。 Englewood Cliffs, NJ: Prentice-Hall, pp. 155-158, 2000.

在 Wolfram|Alpha 上被引用

请这样引用

Weisstein, Eric W. “块。” 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/Block.html

主题分类