主题
Search

割点


ArticulationVertex

连通图的割点,也称为割顶点(cut-vertex)(Harary 1994, p. 26; West 2000; Gross and Yellen 2006)或“割点”(cutpoint)(Harary 1994, p. 26),是一个顶点,移除该顶点将会断开图的连通性(Chartrand 1985)。更一般地,非必然连通的割点是一个顶点,移除该顶点会增加连通分量的数量(Harary 1994, p. 26; West 2000, p. 23)。上面说明了 West (2000, pp. 22-23) 提出的示例图,其中指示了其割点 vy

一个拥有两个或更多顶点的,如果没有割点,则称为双连通图。一个顶点是割点当且仅当它出现在两个双连通分量中。

给定 G 的没有割点的极大连通子图称为(West 2000, p. 155)。

图桥的端点是割点,除非它们都具有度为 1 的顶点度。另一方面,即使是非桥边也可能使其两个端点都是割点。

Wolfram 语言函数FindVertexCut[g] 返回连通图 g 的最小尺寸的顶点割集,如果集合的大小为 1,则对应于割点。

边的割点类似物称为图桥


另请参阅

双连通图, , 连通图, 非连通图, 图桥, 图顶点, 顶点割

使用 Wolfram|Alpha 探索

参考文献

Chartrand, G. "Cut-Vertices and Bridges." §2.4 in Introductory Graph Theory. New York: Dover, pp. 45-49, 1985.Gross, J. T. and Yellen, J. Graph Theory and Its Applications, 2nd ed. Boca Raton, FL: CRC Press, 2006.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 175, 1990.West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2000.

在 Wolfram|Alpha 上引用

割点

请引用为

Weisstein, Eric W. "割点。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/ArticulationVertex.html

主题分类