12

ここにグラフの抜粋があります。

n 個の頂点と m 個の辺を持つ無向グラフ G と整数 k が与えられた場合、H の各頂点が次数 ≥ k を持つような G の最大誘導部分グラフ H を見つける O(m + n) アルゴリズムを与えます。このようなグラフが存在します。グラフ G = (V, E) の誘導部分グラフ F = (U, R) は、G の頂点 V の U の部分集合であり、各辺の両方の頂点が U にあるような G のすべての辺 R です。

私の最初のアイデアは次のようなものです。

まず、この節税では、次数が k 以上であるすべての頂点 S を実際に要求し、次に、他の頂点に接続されたエッジを持たない S 内の頂点を削除します。次に、洗練された S は H であり、すべての頂点の次数は >= k であり、それらの間のエッジは R です。

さらに、O(m+n) を要求するので、BFS または DFS が必要だと思います。それから私は立ち往生します。

BFS では、頂点の次数を知ることができます。しかし、v (頂点) の次数を取得すると、その親以外の他の接続された頂点はわかりません。しかし、親が次数 >= k を持っていない場合、v はまだ他とつながっている可能性があるため、v を削除することはできません。

ヒントはありますか？

編集：

@Michael J. Barberの答えによると、私はそれを実装し、ここでコードを更新しました:

誰でもコードのキーメソッドを見ることができますpublic Graph kCore(Graph g, int k)か? 私はそれを正しくしますか？O(m+n)ですか？

class EdgeNode {
   EdgeNode next;
   int y;
}

public class Graph {
   public EdgeNode[] edges;
   public int numVertices;

   public boolean directed;

   public Graph(int _numVertices, boolean _directed) {
      numVertices = _numVertices;
      directed = _directed;
      edges = new EdgeNode[numVertices];
   }

   public void insertEdge(int x, int y) {
      insertEdge(x, y, directed);
   }

   public void insertEdge(int x, int y, boolean _directed) {
      EdgeNode edge = new EdgeNode();
      edge.y = y;
      edge.next = edges[x];
      edges[x] = edge;
      if (!_directed)
          insertEdge(y, x, true);
   }

   public Graph kCore(Graph g, int k) {
      int[] degree = new int[g.numVertices];
      boolean[] deleted = new boolean[g.numVertices];
      int numDeleted = 0;
      updateAllDegree(g, degree);// get all degree info for every vertex

      for (int i = 0;i < g.numVertices;i++) {
          **if (!deleted[i] && degree[i] < k) {
           deleteVertex(p.y, deleted, g);
          }**
      }

      //Construct the kCore subgraph
      Graph h = new Graph(g.numVertices - numDeleted, false);
      for (int i = 0;i < g.numVertices;i++) {
         if (!deleted[i]) {
           EdgeNode p = g[i];
           while(p!=null) {
              if (!deleted[p.y])
                 h.insertEdge(i, p.y, true); // I just insert the good edge as directed, because i->p.y is inserted and later p.y->i will be inserted too in this loop.
                 p = p.next;
              }
           }
         }
      }

      return h;
  }

  **private void deleteVertex(int i, boolean[] deleted, Graph g) {
     deleted[i] = true;
     EdgeNode p = g[i];
     while(p!=null) {
        if (!deleted[p.y] && degree[p.y] < k) 
            deleteVertex(p.y, deleted, g);
        p = p.next;
     }
  }**

  private void updateAllDegree(Graph g, int[] degree) {
     for(int i = 0;i < g.numVertices;i++) {
         EdgeNode p = g[i];
         while(p!=null) {
            degree[i] += 1;
            p = p.next;
         }
     }
  }

}

4

1 に答える 1

17

頂点の次数kが最小である最大誘導サブグラフは、 kコアと呼ばれます。次数がk未満の頂点を繰り返し削除するだけで、 kコアを見つけることができます。

実際には、まずすべての頂点の次数を評価します。これは O(m) です。次に、次数がk未満の頂点を探して頂点を調べます。そのような頂点が見つかったら、それをグラフから切り取り、近傍の次数を更新し、次数がkを下回る近傍も削除します。各頂点を少なくとも 1 回確認し (O(n) で実行可能)、エッジごとに次数を最大で 1 回更新する必要があります (O(m) で実行可能)。O(m+n) の総漸近境界が得られます。 .

残りの連結要素はkコアです。サイズを評価して最大のものを見つけます。

于 2012-04-18T08:09:04.873 に答える