Жадный алгоритм в задачах о покрытии/Задачи/ex-depth-tree-for-vertex-covering-1-2 — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 1: Строка 1:
−
<big>Цыганова Светлана, 974 гр.</big>
 
−
 
 
Студент предложил для задачи [[Vertex cover]] приближенный алгоритм с точностью ½:
 
Студент предложил для задачи [[Vertex cover]] приближенный алгоритм с точностью ½:
 
* найти в графе дерево (методом поиска в глубину),
 
* найти в графе дерево (методом поиска в глубину),
Строка 8: Строка 6:
 
Прав ли он? Докажите или опровергните.
 
Прав ли он? Докажите или опровергните.
  
−
'''Решение'''
+
[[Category:Решенные задачи]]
−
 
+
−
Во-первых, докажем, что полученное таким образом множество вершин будет вершинным покрытием (не всегда минимальным, правда). Если это не так, то получалось бы, что алгоритм поиска в глубину давал бы цикл, что невозможно.
+
−
 
+
−
Теперь покажем, что соблюдается заданная точность. Для этого рассмотрим полученное студентом дерево. Очевидно, что для каждого ребра в этом дереве хотя бы одна вершина должна лежать в минимальном вершинном покрытии (причем лист должен лежать - из-за того, что мы выкинули личты в "предысходном дереве". Это отсекает варианты "звездочки" и прочего). Тогда число вершин в найденном дереве отличается не больше, чем в 2 раза от числа вершин минимального вершинного покрытия, следовательно, соблюдена заданная точность.
+
−
 
+
−
 
+
−
[[Category:На проверку]]
+

Версия 22:28, 24 декабря 2014

Студент предложил для задачи Vertex cover приближенный алгоритм с точностью ½:

  • найти в графе дерево (методом поиска в глубину),
  • выкинуть из него листья (кроме корневого узла).
  • а оставшееся объявить вершинным покрытием.

Прав ли он? Докажите или опровергните.

Источник — «https://discopal.ispras.ru/index.php?title=Жадный_алгоритм_в_задачах_о_покрытии/Задачи/ex-depth-tree-for-vertex-covering-1-2&oldid=3385»