Как я могу найти индуцированный подграф k узлов с не менее m * k * (k-1)/n * (n-1) ребрами

Question

Мне нужно использовать жадный алгоритм для решения этой проблемы (здесь m число ребер и n - количество вершин в исходном графе). Интуитивно я знаю, что это как-то связано с плотностью графика (из-за части m/n*(n-1)), поэтому я пытаюсь использовать жадный алгоритм для удаления вершины с минимальной степенью каждой итерации, пока не получу график узлов k, но я не знаю, как можно I GARUNTEE алгоритм дает мне окончательный график с по крайней мере m*k*(k-1)/n*(n-1) ребрами.

Ищет любые подсказки, спасибо.

Answer 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. Итак, мы имеем, что жадный алгоритм не уменьшит плотность графа.