4

N 個のノードと E 個のエッジを含むグラフ G があります。各エッジは方向性がありません。目標は、ノーを見つけることです。重要なノードの。

外すとグラフが切れるノードをクリティカルノードと呼びます。目標は、いいえを見つけることです。グラフ内のそのようなノードの。

解決策は次のとおりです。

グラフに属する各ノードについて、グラフから削除し、残りのグラフからノードを選択し、dfs を実行します。どこにでも到達できる場合、それは重要なノードではありません。

この解は O(N*E) または最悪の場合 O(N^3) です。

N^3 は少し遅すぎるため、O(N^2) ソリューションまたは O(E) ソリューションはありますか。

4

1 に答える 1

2

重要なノードは、削除されたときにグラフを 2 つ以上のばらばらのサブグラフに分割するノードです。

したがって、重要なノードは、この重要なノードを介してのみ接続されている 2 つ以上のサブグラフに接続されているノードです。

可能な解決策は次のようになります。

  • グラフ G のすべてのノード i について:

    1. リスト L: ノード i に直接接続されているすべてのノード

    2. リスト L に 2 つのノード u と v が存在し、i を介さずに v で u を接続するパスが存在しない場合、i は重要なノードです。

参考：Wikipedia:周期検出

例 (Java):

public class CrucialNode
{
    public static ArrayList<Node> crucialVertices (Graph g)
    {
        ArrayList<Node> crucial = new ArrayList<Node> ();

        for (Node n : g.getV()) if (isCrucial(g,n)) crucial.add(n);

        return crucial;
    }

    public static boolean isCrucial (Graph g, Node n)
    {
        Graph h = new Graph(g);

        h.removeVertex(n);

        for (Node u : n.getNext())
        {
            for (Node v : n.getNext())
            {
                if (u.equals(v)) continue;

                if (!h.connected(u,v)) return true;
            }
        }

        return false;
    }
}
于 2013-04-07T08:18:01.490 に答える