Участник:Bunakov/ex-min-maxmatching-1-2 — Решение Василия Бунакова — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Новая страница: «Category:На проверку <latex> Т. к. для нахождения произвольного максимального паросочетания …»)
 
м (StasFomin переименовал страницу MAX-CUT: вероятностное округление/Задачи/ex-min-maxmatching-1-2/Решение Василия Бунакова в [[Участник:Bunakov/ex-min-maxmatching-1-2 —…)
 
(не показаны 4 промежуточные версии этого же участника)
Строка 1: Строка 1:
[[Category:На проверку]]
+
* [[MAX-CUT: вероятностное округление/Задачи/ex-min-maxmatching-1-2]]
  
 
<latex>
 
<latex>
 
 
Т. к. для нахождения произвольного максимального паросочетания существует полиномиальный алгоритм (алгоритм Эдмондса), а
 
Т. к. для нахождения произвольного максимального паросочетания существует полиномиальный алгоритм (алгоритм Эдмондса), а
 
размер любого максимального паросочетания превосходит размер оптимального не более, чем в 2 раза, то это и будет
 
размер любого максимального паросочетания превосходит размер оптимального не более, чем в 2 раза, то это и будет
Строка 11: Строка 10:
 
Рассмотрим произвольное ребро $e$ из оптимального паросочетания.
 
Рассмотрим произвольное ребро $e$ из оптимального паросочетания.
 
В любом максимальном паросочетании найдётся не более двух рёбер, смежных ребру $e$. Поскольку каждое ребро графа смежно хотя бы одному ребру из оптимального паросочетания (так как оно является максимальным), то в любом максимальном паросочетании будут только ребра, смежные или совпадающие с ребрами из оптимального паросочетания. Значит, размер любого максимального паросочетания превосходит размер оптимального не более, чем в 2 раза, что и требовалось доказать.
 
В любом максимальном паросочетании найдётся не более двух рёбер, смежных ребру $e$. Поскольку каждое ребро графа смежно хотя бы одному ребру из оптимального паросочетания (так как оно является максимальным), то в любом максимальном паросочетании будут только ребра, смежные или совпадающие с ребрами из оптимального паросочетания. Значит, размер любого максимального паросочетания превосходит размер оптимального не более, чем в 2 раза, что и требовалось доказать.
 +
</latex>
  
 +
[[Участник:StasFomin|StasFomin]] ([[Обсуждение участника:StasFomin|обсуждение]]) 05:03, 8 января 2015 (MSK): Вы невнимательно посмотрели в условие. Ищем ведь мы паросочетание минимального размера (максимальное по включению), а не максимального. Наверно обсудим эту задачу уже на экзамене сегодня. Специально даже решил поменять на будущее условие, чтобы алгоритм Эдмондса даже в голову не приходил.
  
 
+
[[Категория:Уже не исправить]]
 
+
<\latex>
+

Текущая версия на 21:27, 6 октября 2020

StasFomin (обсуждение) 05:03, 8 января 2015 (MSK): Вы невнимательно посмотрели в условие. Ищем ведь мы паросочетание минимального размера (максимальное по включению), а не максимального. Наверно обсудим эту задачу уже на экзамене сегодня. Специально даже решил поменять на будущее условие, чтобы алгоритм Эдмондса даже в голову не приходил.