连通图 的割点,也称为割顶点(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) 提出的示例图,其中指示了其割点 和 。
一个拥有两个或更多顶点的图 ,如果没有割点,则称为双连通图 。一个顶点是割点当且仅当 它出现在两个双连通分量中。
给定图 的没有割点的极大 连通 子图 称为块 (West 2000, p. 155)。
图桥 的端点是割点,除非它们都具有度为 1 的顶点度。另一方面,即使是非桥边也可能使其两个端点都是割点。
Wolfram 语言 函数FindVertexCut [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
主题分类