主題
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,則對應於割點。

邊的割點類似物稱為圖橋


另請參閱

雙連通圖, , 連通圖, 非連通圖, 圖橋, 圖頂點, 頂點割

使用 探索

參考文獻

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

主題分類