algorithm - グラフが切断されないように、グラフから頂点を削除するように命令します

Question

これは、StevenSkienaによるAlgorithmDesignからの質問です（インタビューの準備用）。

グラフGのアーティキュレーション頂点は、削除によってGが切断される頂点です。Gをn個の頂点とm個のエッジを持つグラフとします。削除がグラフを切断しないように、n個の頂点の削除順序を見つける単純なO（n + m）を与えます。

これは私が思ったことです：

1. グラフでDFSを実行し、各ノードの到達可能な最も古い祖先を更新し続けます（これに基づいて、ブリッジカットノード、親キュートノード、またはルートカットノードのいずれであるかを決定します）

2. リーフノード（頂点）またはアーティキュレーション頂点ではないノードが見つかった場合は、それを削除します。

3. DFSの最後に、アーティキュレーション頂点であることが判明したグラフ内のすべてのノードが残ります。

アーティキュレーションの頂点はそのままなので、グラフは接続されたままになります。いくつかのグラフで試してみましたが、うまくいくようですが、本には単純すぎるように感じます。

Answer 1

グラフが接続されていると仮定すると、任意のランダム ノードがサブグラフに到達し、そのスパニング ツリーは、グラフの接続性を壊すことなく事後順に削除できます。グラフがすべてなくなるまで、この方法を繰り返します。

Answer 2

2 つのステップで:

1. トラバーサル アルゴリズムを使用してグラフ DAG を作成する
2. トポロジーソートを行う

各ステップは O(m+n) を超えずに終了します

Answer 3

常にツリーの葉を 1 つずつ削除すると、ツリーの残りの部分は接続されたままになります。これを行う特定の方法の 1 つは、DFS または BFS を使用してグラフをトラバースするときに、各頂点に事前注文番号を割り当てることです。頂点を降順で並べ替えます (事前注文番号に基づく)。グラフからその順序で頂点を削除します。葉は常に最初に削除されることに注意してください。