點連通度怎麼求

一個具有N個點的圖G中，在去掉任意k-1個頂點後1<=k<=N，所得的子圖仍然連通，去掉K個頂點後不連通，則稱G是K連通圖，K稱作圖G的連通度，記作K(G)。

連通圖G的連通程度通常叫做連通度。連通度有兩種，一種是點連通度，另一種是邊連通度。通常一個圖的連通度越好，它所代表的網路越穩定。如果圖G的頂點集的一個真子集T滿足G-T不連通或是平凡圖，則稱T為G的一個點割。如果圖G的邊集的一個真子集S滿足G-S不連通或是平凡圖，則稱S為G的一個邊割。