Найдите k вершин в дереве, чтобы покрыть максимальное количество ребер

Моя идея жадная.

Я поддерживаю E [i] как количество ребер, соединенных с вершиной i.

Repeat following k times:

    Every time I extract largest E[k] and add vertex k to the result set, and I decrease E[t] by 1 for every vertex t adjacent to k.

    Set E[k] = 0;

Однако я не знаю, верна моя идея или нет ... И я не знаю, как это доказать.

Если нет, то как правильно решить эту проблему?


algorithm dynamic-programming graph-algorithm greedy
person Euclid Ye    schedule 23.11.2015    source источник
comment
Я думаю, вы получите более точные ответы, если зададите такие вопросы на cs.stackexchange.com.   -  person Saeid    schedule 23.11.2015
comment
Я согласен с sudomakeinstall2. Но эта проблема звучит сложно, а это значит, что жадный подход не сработает.   -  person Teepeemm    schedule 23.11.2015
comment
Упс ... Но на самом деле вопрос требует, чтобы я решил его за O (k ^ 2 * n) раз .. Спасибо за информацию! Я вчера разместил этот вопрос по математике, и никто не ответил.   -  person Euclid Ye    schedule 23.11.2015
comment
@Tipton Я считаю, что это неправильный подход. что произойдет, если после извлечения K узлов ни один из них не будет связан ни с каким другим в этом подграфе? точно, вы нашли подграф без ребер.   -  person Luis Daniel    schedule 25.11.2015

Ответы (1)


arrow_upward
0
arrow_downward

Такой жадный подход неверен.

Предположим, вас просят вычислить максимальное количество ребер, которое могут покрыть 4 узла (k = 4) на графике ниже:

введите здесь описание изображения

Ваш алгоритм выберет Узел 1, а затем выберет 3 узла из {2,3,4,5}.

Этим выбором вы закроете 7 ребер, вместо этого вы можете выбрать узлы 2, 3, 4 и 5 и покрыть все 8 ребер!

person mstou    schedule 02.01.2020