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