2

安全な頂点の削除に関する 2 つの例外を次に示します。

5-28。グラフ G の分節頂点は、削除によって G が切断された頂点です。G を n 個の頂点と m 個の辺を持つグラフとします。関節点ではない G の頂点を見つけるための単純な O(n + m) アルゴリズムを与えてください。

5-29。前の問題をフォローアップして、削除によってグラフが切断されないように、n 個の頂点の削除順序を見つける O(n + m) アルゴリズムを与えます。(ヒント: DFS/BFS を考えてください。)

5-28 については、次のように考えています。

私はdfsを実行しますが、完全ではありません。処理が終了した最初の頂点は、葉である必要があるため、非関節頂点になります。または、後端がその祖先を指す葉です (これも関節頂点ではありません)。

5-29用

どうすれば綺麗にできるかはまだわかりません。私の頭に浮かぶのは、グラフでは、サイクル内の頂点を安全に削除できないということです。また、サイクルがない場合は、dfs ツリーから逆方向に頂点を削除することも安全です。

誰かヒントをくれたり、私の考えが正しいか間違っているか教えてくれませんか?

4

3 に答える 3

2

5-28 に対するあなたの解決策は正しいと思います。O(n+m) 時間で関節ではないノードを見つけることが保証されます。

5-29 については、5-28 に対するあなたのソリューションに基づいてそれを行う 1 つの方法だと思います。dfs を実行している間、各ノードがいつスタックを離れたか (処理が終了した時間) を追跡します。あなたが言ったように、最初の葉は葉ノードでなければならないので、削除してもグラフは切断されません。次に、ノードを削除してスタックから 2 番目に残すことができます。最初のノードを削除したとき、それはリーフ ノードでもある必要があります。したがって、DFS の実行中にノードがスタックからポップされたときとは逆の順序でノードを削除できます。これを行うには、DFS のパスが 1 つしか必要ないため、実行時間は O(n+m) です。

もう 1 つの簡単な方法は、BFS を使用することです。5.28 では、最大深度のノードを削除しても、グラフは切断されません。深さの浅いノードから他のノードに到達できるためです。そのため、5.29 では、すべてのノードをソート深度の降順で削除できます。また、必要な BFS は 1 つだけなので、実行時間は O(n+m) です。このアプローチの方が理解しやすいと思います。

于 2012-04-27T19:57:12.017 に答える
-1

最初の問題については、テストしたい頂点をグラフから削除し、他の頂点から開始して DFS/BFS を実行し、訪問した頂点の数を数えます。より小さい場合(original size - 1)、テストされた頂点は関節頂点です。

同じ考えが 2 番目の問題にも当てはまります。頂点をランダムに選択して削除すると、通常はグラフが 2 つのブロックに分割されます。削除された頂点がアーティキュレーション頂点でない場合、2 つのブロックのうちの 1 つが空でなければなりません。それ以外の場合、両方のブロックにいくつかの頂点があり、その場合、両方のブロックのすべての頂点は、最終的な「安全な削除」順序でこの頂点の前にリストする必要がありますが、どのブロックを最初に完全に削除するかを決定することは重要ではありません。 . したがって、次のような小さな再帰関数を書くことができます。

vertex[] safe_order_cut (vertex[] v)
    if (v.length==0) return empty_vertex_list;
    vertex x = randomly_pick(v);
    vertex v1[], v2[];
    cut_graph(v,x,v1,v2);
    return safe_order_cut(v1) + safe_order_cut(v2) + x;

接続性の問題 (および関連するカット頂点の問題) は、グラフ理論で広く研究されています。興味がある場合は、wiki ページでその他のアルゴリズムを読むことができます。

于 2012-04-25T23:15:26.630 に答える