Блог

Эвристическое решение, которое мне дали, является:

• Выполните поиск в глубину на графике
• Удалите все листья
• Оставшийся граф образует покрытие вершин

Мне был задан вопрос: «Покажите, что это эвристическое решение не более чем в два раза больше оптимального решения для покрытия вершин». Как я могу это показать?

Я предполагаю, что граф связан (если это не так, мы можем решить эту проблему для каждого компонента отдельно).

Я также предполагаю, что dfs-дерево является корневым, а листом является вершина, у которой нет дочерних элементов в корневом dfs-дереве (это важно. Если мы определим его по-другому, алгоритм может не сработать).

Нам нужно показать вещам:

1. Набор вершин, возвращаемый алгоритмом, является покрытием вершин. Действительно, в dfs-дереве любого неориентированного графа могут быть только типы ребер: ребра дерева (такое ребро покрыто, поскольку по крайней мере одна из его конечных точек не является листом) и заднее ребро (опять же, одна из его конечных точек не является листом, потому что заднее ребро идет от вершины к ее предку. Лист не может быть предком листа).

2. Давайте рассмотрим dfs-дерево и проигнорируем остальные ребра. Я покажу, что невозможно покрыть ребра дерева, используя менее половины не оставляющих вершин. Пусть S — минимальное покрытие вершин. Рассмотрим вершину, v такую v , которая не является листом и v не входит в S (то есть v возвращается рассматриваемой эвристикой, но не входит в оптимальный ответ). v не является листом, следовательно, в dfs-дереве есть ребро v -> u (где u является преемником v ). Ребро v -> u покрыто S . Таким образом, u находится в S . Давайте определим отображение f из вершин, возвращаемых эвристикой, которые не входят в S as f(v) = u (где v и u имеют то же значение, что и в предыдущем предложении). Обратите внимание, что v является родительским для u в dfs-дереве. Но для любой вершины в дереве может быть только один родительский элемент! Таким образом, f это внедрение. Это означает, что количество вершин в наборе, возвращенном эвристикой, но не в оптимальном ответе, не больше размера оптимального ответа. Это именно то, что нам нужно было показать.

Плохие новости: эвристика не работает. Строго говоря, 1 изолированная вершина является контрпримером для вопроса. Тем не менее, эвристика вообще не дает решения для покрытия вершин, даже если вы исправите ее для изолированной вершины и для двухточечных кликов. Взгляните на полносвязные графы с числом вершин от 1 до 3:

1 — строго говоря, изолированная вершина не является листом (она имеет степень 0, в то время как лист — это вершина со степенью 1), поэтому эвристическое решение сохранит ее, в то время как покрытие вершин не будет

2 — эвристическое решение удалит оба листа, в то время как покрытие вершин сохранит по крайней мере 1 из них

3 — эвристическое решение оставит 1 вершину, в то время как покрытие вершин должно содержать не менее 2 вершин этой группы