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

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

Найдите приближенный алгоритм с точностью для нахождения паросочетания максимального размера.

Рассмотрим ленивый алгоритм построения вершинного покрытия. Множество E "попавшихся алгоритму" ребер, вершины которых добавлялись в вершинное покрытие C, является паросочетанием. M паросочетание максимального размера. Тогда |C| ≥ |M|, поскольку любое вершинное покрытие содержит по крайней мере одну вершину для каждого ребра из М

                            |E| = |C|/2 ≥ |M|/2 

Ленивый алгоритм строит паросочетание максимального размера с точностью 1/2.

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

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

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