Покажите, что эвристическое решение вершинного покрова в большинстве вдвое больше, чем оптимальное решением

Question

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

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

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

Answer 1

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

Я также предполагаю, что дерево 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, как f(v) = u (где v и u имеют то же значение, что и в предыдущем предложении). Обратите внимание, что v является родителем u в дереве dfs. Но для любой вершины в дереве может быть только один родитель!Таким образом, f представляет собой инъекцию. Это означает, что количество вершин в наборе, возвращаемое эвристикой, но не в оптимальном ответе, не больше размера оптимального ответа. Это именно то, что нам нужно было показать.

Answer 2

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

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

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

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