0
1

Доказать корректность работы алгоритма построения максимального паросочетания

задан 28 Дек '16 15:47

@Rays: алгоритмов построения максимального паросочетания имеется огромное количество. Какой из них Вы имеете в виду, угадать невозможно. Это вопрос типа "кто написал 40-ю симфонию?" :)

(28 Дек '16 15:59) falcao

@falcao: Как ни странно, но задача звучит именно так. Есть общий псевдокод к данному алгоритму: ПОВТОРЯТЬ-ПОКА (есть путь от источника к стоку){ ПОСТРОИТЬ путь; ИЗМЕНИТЬ НАПРАВЛЕНИЯ РЕБЕР вдоль этого пути; УДАЛИТЬ фиктивные ребра в этом пути (начальное и конечное ребра пути); } КОНЕЦ ЦИКЛА

(28 Дек '16 16:16) Rays

@Rays: задача может звучать так -- для тех, кому только что сообщили тот конкретный алгоритм, корректность которого требуется проверить. Для постороннего слушателя она так звучать не должна, потому что алгоритмов много. Эта теория очень сильно разработана, но в ней чуть ли не каждый день появляются новые алгоритмы, или модификации чего-то известного. Даже для классических алгоритмов (типа Форда - Фалкерсона) нужно описывать детали конкретной реализации.

По тому краткому описанию, которое Вы добавили в комментарии, что-то можно будет попытаться сделать.

(28 Дек '16 16:42) falcao

Я думаю, проще всего дать ссылку. См. стр. 166 и далее. Достаточно посмотреть второе её доказательство. Далее описывается алгоритм, который в частном случае подходит для построения максимального паросочетания.

(29 Дек '16 2:28) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,948
×1,153
×676

задан
28 Дек '16 15:47

показан
751 раз

обновлен
29 Дек '16 2:28

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru