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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Решение Тихомиров)
Строка 3: Строка 3:
 
</latex>
 
</latex>
 
<!--Вообще-то, решения уже есть-->
 
<!--Вообще-то, решения уже есть-->
 
<big>Алгоритм: возьмем граф G=(V,E); результирующее множество R — пустое.
 
 
1) Выберем произвольное ребро (u, v) из E, <latex>u \in V, v \in V</latex>
 
 
2) Добавим это ребро в множество R
 
 
3) Удалим для u, v все инцидентные этим вершинам ребра из E.
 
 
повторяем 1-3 пока не останется ребер в E; получим R — искомое паросочетание.
 
 
Доказательство 1/2-точности данного приближенного алгоритма:
 
Для оптимального паросочетания R* любое ребро из исходного графа инцедентно ребрам из R*(или содержится в R*).
 
Пусть «нет» и существует ребро (u, v) не из R* и не инцедентное ребрам из R* — тогда это ребро можно добавить к R* тоесть R* не максимальное по включению(<latex>R* \subset (R^* \cup(u, v))</latex>).
 
Значит все ребра из R имеют общую вершину с ребрами из R*, так как количество вершин R* = 2|R*| и ребра из R содержат минимум по одной вершине, и в одной вершине может быть максимум одно ребро из R, то |R| < 2|R*| , чтд.
 
 
ps: Вообще, мне кажется, если следовать определению точно, то точность = 2 и точность 1/2 была бы если бы |R| < 1/2|R*|, но это не возможно так как R* - минимум.
 
</big>
 
[[Category:На проверку]]
 

Версия 02:57, 11 декабря 2013