12

这是图表的消费税。

给定一个有 n 个顶点和 m 个边的无向图 G，以及一个整数 k，给出一个 O(m + n) 算法，该算法找到 G 的最大诱导子图 H，使得 H 中的每个顶点的度数≥ k，或证明没有存在这样的图表。图 G = (V, E) 的诱导子图 F = (U, R) 是 G 的顶点 V 和 G 的所有边 R 的子集，使得每条边的两个顶点都在 U 中。

我最初的想法是这样的：

首先，这个 excise 实际上要求我们拥有所有度数大于或等于 k ​​的顶点 S，然后我们删除 S 中没有任何边与其他顶点相连的顶点。则精化后的 S 为 H，其中所有顶点的度数 >= k，并且它们之间的边为 R。

另外，它要求 O(m+n)，所以我想我需要一个 BFS 或 DFS。然后我就卡住了。

在 BFS 中，我可以知道一个顶点的度数。但是一旦我得到 v （一个顶点）的度数，我不知道除了它的父顶点之外的其他连接顶点。但是如果父母没有度数> = k，我不能消除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的任何邻居。您需要至少查看每个顶点一次（在 O(n) 中如此可行）并为每条边最多更新一次度数（在 O(m) 中如此可行），给出 O(m+n) 的总渐近界.

其余的连接组件是k核。通过评估它们的大小找到最大的。

于 2012-04-18T08:09:04.873 回答