塊(圖論術語)

基本介紹

• 中文名：塊
• 外文名：piece，block， chunk
• 讀音：kuài

如果連通無向圖G中存在一個點u，刪除u後G不再連通，則稱u為G的一個割點（articulationpoint) 。沒有割點的連通圖稱為雙連通圖(biconnected graph) 。對於任意兩條邊e1和e2，如果e1=e2或者它們在同一個環中，則稱它們滿足關係R。容易驗證R是一個等價關係。根據此等價關係我們可以把G的邊分為不相交集E1, E2, ..., Ek，設Vi為Ei中包含的點集，則每個子圖Gi=(Vi, Ei)稱為G的一個雙連通分量(biconnected compo-nent, BCC) ，或稱塊(block )　雙連通分量具有如下性質：

1. 雙連通分量都是雙連通的。

2. 任意兩個不同的雙連通分量最多只有一個公共點

3. 結點u是圖G的割頂若且唯若u是某兩個不同的雙連通分量的公共點。