Покажите, как найти максимальное паросочетание в двудольном графе, используя потоковый алгоритм в соответствующей сети

задан 2 Май '16 22:38

10|600 символов нужно символов осталось
1

Добавляем вершины s и t. Из s выводим ориентированные рёбра с пропускной способностью 1 во все вершины первой доли графа. Из вершин второй доли выводим такие же стрелки в t. Рёбра самого графа ориентируем от первой доли ко второй с теми же пропускными способностями.

Теперь, находя максимальный поток из s в t, мы автоматически получаем максимальное паросочетание в двудольном графе. Оно состоит в точности из тех рёбер, через которые проходит поток (в данном случае он через любое ребро всегда или нулевой, или единичный).

ссылка

отвечен 3 Май '16 0:01

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×413
×167
×100
×8

задан
2 Май '16 22:38

показан
307 раз

обновлен
3 Май '16 0:01

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

по почте:

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

по RSS:

Ответы

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

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