algorithm - グラフの頂点接続を計算する

Question

グラフが与えられたときに、そのグラフの頂点の接続性 (グラフを 2 つの接続されたグラフに分離するために削除する頂点の最小数) を計算するアルゴリズムはありますか。(グラフはすでに切断されている可能性があることに注意してください)。ありがとう！

Answer 1

参照: グラフが K 頂点接続かどうかの判断

グラフの k 頂点連結性

これをバイナリ検索と組み合わせると完了です。