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

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 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.