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

Материал из DISCOPAL
Перейти к: навигация, поиск

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

StasFomin 18:46, 15 мая 2019 (MSK): Ну что за лень.

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

И ещё тут полезная информация и доказательство есть: http://www.math.nsc.ru/LBRT/k5/Kononov/Kononovs_teaching_book.pdf

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

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

StasFomin 18:46, 15 мая 2019 (MSK): Зачтем, даже с повышенным баллом. Ведь обучался, смотрел полезные лекции, гуд.