gpt4 book ai didi

algorithm - graph - 如何找到 G 的最大诱导子图 H,使得 H 中的每个顶点的度数≥ k

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:25:32 24 4
gpt4 key购买 nike

这里是图表的练习。

Given an undirected graph G with n vertices and m edges, and an integer k, give an O(m + n) algorithm that finds the maximum induced subgraph H of G such that each vertex in H has degree ≥ k, or prove that no such graph exists. An induced subgraph F = (U, R) of a graph G = (V, E) is a subset of U of the vertices V of G, and all edges R of G such that both vertices of each edge are in U.

我最初的想法是这样的:

首先,这个练习实际上要求我们拥有度数大于或等于 k ​​的所有顶点 S,然后我们删除 S 中没有任何边连接到其他顶点的顶点。则细化后的S为H,其中所有顶点的度数>= k,它们之间的边为R。

此外,它要求 O(m+n),所以我认为我需要一个 BFS 或 DFS。然后我就卡住了。

在 BFS 中,我可以知道顶点的度数。但是一旦我得到了v(一个顶点)的度数,我就不知道除了它的父节点之外还有其他连接的顶点。但是如果 parent 没有度 >= 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;
}
}
}

最佳答案

顶点具有最小度k的最大导出子图称为k-core .您可以通过重复删除任何度数小于 k 的顶点来找到 k 核。

在实践中,您首先评估所有顶点的度数,即 O(m)。然后,您遍历顶点以寻找度数小于 k 的顶点。当您找到这样的顶点时,将其从图中删除并更新邻居的度数,同时删除度数低于 k 的所有邻居。您需要至少查看每个顶点一次(在 O(n) 中如此可行)并为每条边最多更新一次度数(在 O(m) 中如此可行),给出 O(m+n) 的总渐近边界.

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

关于algorithm - graph - 如何找到 G 的最大诱导子图 H,使得 H 中的每个顶点的度数≥ k,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10205191/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com