Участник:Jzargo/Паросочетание

Материал из DISCOPAL
< Участник:Jzargo
Версия от 12:21, 3 мая 2019; Jzargo (обсуждение | вклад) (Новая страница: «Задача(она лежала в нерешённых): http://discopal.ispras.ru/MAX-CUT:_вероятностное_округление/Задачи/ex-min-…»)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Задача(она лежала в нерешённых): http://discopal.ispras.ru/MAX-CUT:_вероятностное_округление/Задачи/ex-min-maxmatching-1-2 (почему-то не получается сослаться)

Если воспринимать задание дословно ("найти алгоритм"), то оставить эту ссылку будет достаточно: https://www.lektorium.tv/sites/lektorium.tv/files/additional_files/20090913_algorithmsfornphardproblems_kulikov_lecture02.pdf

Пока "искал алгоритм" посмотрел много интересных мини-лекций у Андрея Михайловича Райгородского про паросочетания и алгоритмы на графах. Например, это: https://ru.coursera.org/lecture/teoriya-grafov/viershinnoie-pokrytiie-tieoriema-kionigha-vtpAg

И да, там открыто для просмотра решение другого человека, которое я случайно себе заспойлерил, так что не вижу смысла его переписывать. Вы вряд ли зачтёте мне эту задачу, но зато креатив.