點連通度的定義：一個具有N個點的圖G中，在去掉任意k-1個頂點后（1<=k<=N）,所得的子圖仍然連通，去掉K個頂點后不連通，則稱G是K連通圖，K稱作圖G的連通度，記作K（G）。即去掉最少個數(shù)的點后，子圖不連通或者成為平凡圖；

詳細(xì)的理解：http://hi.baidu.com/lerroy312/blog/item/d7ea97ee7b1f3cddd439c927.html

求連通度的做法：（個人能力有限，可能會有錯誤）

1：枚舉源匯點(這里源點也是要枚舉的)求最小割；如果沒有最小割說明原圖是強(qiáng)連通的，點連通度為N。

2：拆點（無向無向邊拆成兩條有向邊），指定一個源點，枚舉匯點（如果匯點與源點不連通，則圖不連通），求使源匯不連通最少要移除的點數(shù)，并取最小值，如果最小值比n大，則最小值為n。

3：求最大生成樹，利用最大生成樹的邊（點）來求點連通度。（此方法應(yīng)該比較簡單）；

轉(zhuǎn)載于:https://www.cnblogs.com/adroitly/archive/2012/08/10/2632212.html

總結(jié)

以上是生活随笔為你收集整理的点连通度的求法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。