Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Пусть E – множество ребер графа G, VP – искомое множество вершин вершинного покрытия графа G.
VP:=[]; {изначально множество VР пусто}
Е:=<множество всех ребер графа>;
While E<>[] Do Begin{пока множество ребер не пусто}
<выбрать ребро (u, v) из Е>;
VP:=VP+[u]+[v];
<удалить из E все ребра, инцидентные вершинам u и v>
End;
Выполним трассировку алгоритма на примерах, обозначив через А множество выбираемых ребер графа.
Пример 1
А | VP | Е | |
[] | [] | [1..9] | |
[1] | [1,3] | [6..9] | |
[1,6] | [1,2,3,5] | [] |
Найденное решение VP =[1,2,3,5] оптимально.
Пример 2
А | VP | Е | |
[] | [] | [1..7] | |
[1] | [1,3] | [4,6,7] | |
[1,4] | [1,2,3,5] | [7] | |
[1,4,7] | [1..6] | [] |
Найденное решение не оптимально. | VP |=6, а | VPОПТ |=3.
Теорема. Данный приближенный алгоритм решения задачи о вершинном покрытии работает с ошибкой не более чем в 2 раза.
Доказательство. Очевидно (по построению), что множество VP – множество вершин вершинного покрытия.
А – множество ребер, выбираемых в ходе работы алгоритма. Никакие два ребра из А не имеют общих вершин (по построению), следовательно, |VP|=2·|A| или .
Оптимальное вершинное покрытие VPОПТ содержит хотя бы одну из двух вершин выбранных в А ребер, следовательно, | A |≤| VPОПТ |.
Из полученных равенства и неравенства | A |≤| VPОПТ | следует, что . Это означает, что найденное решение не более чем в два раза превосходит оптимальное, т. е. алгоритм работает с ошибкой не более чем в два раза.
Вопросы по главе для самоконтроля
1. Сформулируйте определение массовой проблемы.
2. Сформулируйте определение NP -полной задачи.
3. Сформулируйте нерешенные задачи теории NP -полноты.
4. Сформулируйте определение полиномиальной сводимости.
5. На чем основан способ доказательства NP -полноты задач?
6. Что называется схемой приближения?
7. Что называется полностью полиномиальной схемой приближения?
8. Что значат слова «алгоритм работает с ошибкой не более чем в n раз»?
9. Привести пример графа, для которого приближенный алгоритм решения задачи о вершинном покрытии дает
a) точное решение;
b) решение с ошибкой ровно в два раза.
10. Известно, что задача о ВЕРШИННОМ ПОКРЫТИИ и задача о КЛИКЕ взаимно дополнительны: минимальное вершинное покрытие является дополнением к максимальной клике в графе-дополнении. Можно ли отсюда заключить, что приближенный алгоритм решения задачи о ВЕРШИННОМ ПОКРЫТИИ даст решение и для задачи о КЛИКЕ с такой же погрешностью? Ответ обоснуйте.
Дата публикования: 2015-07-22; Прочитано: 776 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!