我需要使用贪心算法来解决这个问题(这里m是边的数量，n是原始图中的顶点数量)。直觉上，我知道它与图的密度有关(由于 m/n*(n-1) 部分)，所以我尝试使用贪心算法在每次迭代中删除具有最小度数的顶点，直到我得到一个 k 节点图，但我不知道我如何才能保证该算法给我至少包含 m*k*(k-1)/n*( n-1) 边。
寻找任何提示，谢谢。
最佳答案
让我们定义图的密度 p=m/(n*(n-1)) (对于无向图，它应该是 p=2*m/(n*(n-1)) 。请注意，对于密度为 p 和 k 顶点的图，它有 (k*(k-1)) * p 边。还要注意，当你贪婪地删除具有最小度数的顶点时，它会赢'降低图的密度(下面会证明)。所以当你得到带有k个顶点的子图时，它的密度等于或大于m/(n*(n-1))，那么这个子图至少包含k*(k-1)(m*/n*(n-1))条边。
设 G 为 m 的图边缘和 n顶点，然后 p=m/n .让d所有顶点的最小度数。然后我们有 n * d <= m即 d <= m/n .因此，当您删除度数最小的顶点时，您会得到一个带有 m-d 的图。边缘和 n-1顶点，则新图的密度将为 p'=(m-d)/(n-1) >= (m-m/n)/(n-1) = m/n = p .所以我们有贪心算法不会降低图的密度。
关于algorithm - 如何找出至少有 m*k*(k-1)/n*(n-1) 条边的 k 个节点的诱导子图，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34075096/