Жадный алгоритм в задачах о покрытии/Задачи/ex-max-maxmatching-1-2 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
Larisa (обсуждение | вклад) |
||
Строка 1: | Строка 1: | ||
Найдите приближенный алгоритм с точностью <m>\frac{1}{2}</m> для нахождения паросочетания максимального размера. | Найдите приближенный алгоритм с точностью <m>\frac{1}{2}</m> для нахождения паросочетания максимального размера. | ||
− | [[Category: | + | [[Category:На проверку]] |
− | + | ||
+ | Рассмотрим ленивый алгоритм построения вершинного покрытия. Множество '''E''' "попавшихся алгоритму" ребер, вершины которых добавлялись в вершинное покрытие '''C''', является паросочетанием. '''M''' паросочетание максимального размера. Тогда |'''C'''| ≥ |'''M'''|, поскольку любое вершинное покрытие содержит по крайней мере одну вершину для каждого ребра из '''М''' | ||
+ | |||
+ | |'''E'''| = |'''C'''|/2 ≥ |'''M'''|/2 | ||
+ | |||
+ | Ленивый алгоритм строит паросочетание максимального размера с точностью 1/2. |
Версия 11:38, 26 октября 2014
Найдите приближенный алгоритм с точностью для нахождения паросочетания максимального размера.
Рассмотрим ленивый алгоритм построения вершинного покрытия. Множество E "попавшихся алгоритму" ребер, вершины которых добавлялись в вершинное покрытие C, является паросочетанием. M паросочетание максимального размера. Тогда |C| ≥ |M|, поскольку любое вершинное покрытие содержит по крайней мере одну вершину для каждого ребра из М
|E| = |C|/2 ≥ |M|/2
Ленивый алгоритм строит паросочетание максимального размера с точностью 1/2.