連通圖 的割點,也稱為割頂點(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,則對應於割點。
邊的割點類似物稱為圖橋 。
另請參閱 雙連通圖 ,
塊 ,
連通圖 ,
非連通圖 ,
圖橋 ,
圖頂點 ,
頂點割
使用 探索
參考文獻 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. 在 上引用 割點
請引用為
Weisstein, Eric W. "割點。" 來自 Web 資源。 https://mathworld.tw/ArticulationVertex.html
主題分類