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

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

Версия 05:03, 8 января 2015


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