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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: замена :Нерешенные задачи]] на :Решенные задачи]])
(не показано 12 промежуточных версий этого же участника)
Строка 1: Строка 1:
 
Найдите приближенный алгоритм с точностью <m>\frac{1}{2}</m> для нахождения паросочетания максимального размера.
 
Найдите приближенный алгоритм с точностью <m>\frac{1}{2}</m> для нахождения паросочетания максимального размера.
  
−
[[Category:На проверку]]
 
  
−
Рассмотрим ленивый алгоритм построения вершинного покрытия. Множество '''E''' "попавшихся алгоритму" ребер, вершины которых добавлялись в вершинное покрытие '''C''', является паросочетанием. '''M''' паросочетание максимального размера. Тогда |'''C'''| ≥ |'''M'''|, поскольку любое вершинное покрытие содержит по крайней мере одну вершину для каждого ребра из '''М'''
+
<!--Вообще-то, решения уже есть-->
  
−
                            |'''E'''| = |'''C'''|/2 ≥ |'''M'''|/2
+
[[Категория:Решенные задачи]]
−
 
+
−
Ленивый алгоритм строит паросочетание максимального размера с точностью 1/2.
+

Версия 15:49, 20 мая 2020

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

Источник — «https://discopal.ispras.ru/index.php?title=Жадный_алгоритм_в_задачах_о_покрытии/Задачи/ex-max-maxmatching-1-2&oldid=11043»