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

Ссылки сюда (6) →

Алгоритм: возьмем граф 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* - минимум.

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.