Жадный алгоритм в задачах о покрытии/Задачи/ex-min-maxmatching-1-2 — различия между версиями
StasFomin (обсуждение | вклад) |
|||
Строка 1: | Строка 1: | ||
− | <latex> | + | <big><latex> |
Найдите приближенный алгоритм с точностью~$\frac{1}{2}$ для нахождения максимального (по включению) паросочетания минимального объема. | Найдите приближенный алгоритм с точностью~$\frac{1}{2}$ для нахождения максимального (по включению) паросочетания минимального объема. | ||
</latex> | </latex> | ||
− | [[Category: | + | Алгоритм: возьмем граф 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, то <latex>|R| <= 2|R*|</latex> , чтд. | ||
+ | |||
+ | ps: Вообще, мне кажется, если следовать определению точно, то точность = 2 и точность 1/2 была бы если бы <latex>|R| <= 1/2|R*|</latex>, но это не возможно так как R* - минимум. | ||
+ | </big> | ||
+ | [[Category:На проверку]] | ||
<!--Вообще-то, решения уже есть--> | <!--Вообще-то, решения уже есть--> |
Версия 23:39, 10 декабря 2013
Алгоритм: возьмем граф G=(V,E); результирующее множество R — пустое.
1) Выберем произвольное ребро (u, v) из E,
2) Добавим это ребро в множество R
3) Удалим для u, v все инцидентные этим вершинам ребра из E.
повторяем 1-3 пока не останется ребер в E; получим R — искомое паросочетание.
Доказательство 1/2-точности данного приближенного алгоритма: Для оптимального паросочетания R* любое ребро из исходного графа инцедентно ребрам из R*(или содержится в R*). Пусть «нет» и существует ребро (u, v) не из R* и не инцедентное ребрам из R* — тогда это ребро можно добавить к R*, то-есть R* не максимальное по включению(). Значит все ребра из R имеют общую вершину с ребрами из R*, так как количество вершин R* = 2|R*| и ребра из R содержат минимум по одной вершине, и в одной вершине может быть максимум одно ребро из R, то , чтд.
ps: Вообще, мне кажется, если следовать определению точно, то точность = 2 и точность 1/2 была бы если бы , но это не возможно так как R* - минимум.