Жадный алгоритм в задачах о покрытии/Задачи/ex-depth-tree-for-vertex-covering-1-2 — различия между версиями
Tsyganova (обсуждение | вклад) |
Tsyganova (обсуждение | вклад) |
||
| Строка 12: | Строка 12: | ||
Во-первых, докажем, что полученное таким образом множество вершин будет вершинным покрытием (не всегда минимальным, правда). Если это не так, то получалось бы, что алгоритм поиска в глубину давал бы цикл, что невозможно. | Во-первых, докажем, что полученное таким образом множество вершин будет вершинным покрытием (не всегда минимальным, правда). Если это не так, то получалось бы, что алгоритм поиска в глубину давал бы цикл, что невозможно. | ||
| − | Теперь покажем, что соблюдается заданная точность. Для этого рассмотрим полученное студентом дерево. Очевидно, что для каждого ребра в этом дереве хотя бы одна вершина должна лежать в минимальном вершинном покрытии. Тогда число вершин в найденном дереве отличается не больше, чем в 2 раза от числа вершин минимального вершинного покрытия, следовательно, соблюдена заданная точность. | + | Теперь покажем, что соблюдается заданная точность. Для этого рассмотрим полученное студентом дерево. Очевидно, что для каждого ребра в этом дереве хотя бы одна вершина должна лежать в минимальном вершинном покрытии (причем лист должен лежать - из-за того, что мы выкинули личты в "предысходном дереве". Это отсекает варианты "звездочки" и прочего). Тогда число вершин в найденном дереве отличается не больше, чем в 2 раза от числа вершин минимального вершинного покрытия, следовательно, соблюдена заданная точность. |
[[Category:На проверку]] | [[Category:На проверку]] | ||
Версия 21:42, 24 декабря 2014
Цыганова Светлана, 974 гр.
Студент предложил для задачи Vertex cover приближенный алгоритм с точностью ½:
- найти в графе дерево (методом поиска в глубину),
- выкинуть из него листья (кроме корневого узла).
- а оставшееся объявить вершинным покрытием.
Прав ли он? Докажите или опровергните.
Решение
Во-первых, докажем, что полученное таким образом множество вершин будет вершинным покрытием (не всегда минимальным, правда). Если это не так, то получалось бы, что алгоритм поиска в глубину давал бы цикл, что невозможно.
Теперь покажем, что соблюдается заданная точность. Для этого рассмотрим полученное студентом дерево. Очевидно, что для каждого ребра в этом дереве хотя бы одна вершина должна лежать в минимальном вершинном покрытии (причем лист должен лежать - из-за того, что мы выкинули личты в "предысходном дереве". Это отсекает варианты "звездочки" и прочего). Тогда число вершин в найденном дереве отличается не больше, чем в 2 раза от числа вершин минимального вершинного покрытия, следовательно, соблюдена заданная точность.