Паросочетания. Найдите дефицит, множество с максимальным дефицитом границы, и максимальное паросочетание в двудольном графе, состоящем из дуг: A->c A->h B->b B->i C->c C->e C->h D->b D->c D->f E->c E->f F->d F->i G->a G->f G->i H->e H->g H->h I->b I->f
J->b J->d J->f J->j

задан 16 Май '14 22:08

Или хотя бы дайте ссылку на источник, где такие задачи разбираются.

(16 Май '14 22:09) Тоссер
10|600 символов нужно символов осталось
0

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

Можно нарисовать таблицу $%10\times10$%, строки которой помечены буквами A, B, ..., J, а столбцы -- буквами a, b, ..., j. Все дуги изображаются клетками таблицы. Например, для дуги $%A\to c$% отмечаем клетку, расположенную на пересечении строки $%A$% и столбца $%c$%.

Теперь надо найти максимальное число отмеченных клеток, расположенных в разных строках и разных столбцах. Начать надо с анализа того, нет ли строк или столбцов с одной отмеченной клеткой. Такая клетка имеется: это $%(J;j)$%: в последнем столбце она всего одна. Значит, объединяем их в пару, и удаляем из рассмотрения строку и столбец, её содержащие. Далее смотрим, какие имеются ещё пары, выявляемые этим способом однозначно. Таковой оказывается пара $%(F;d)$%, и так далее. В данной задаче после 7 шагов мы находим однозначно 7 пар, и остаётся 3 строки и 3 столбца, для которых паросочетание легко найти (причём несколькими способами).

Поскольку паросочетание удалось построить для всех строк и столбцов (а могло быть и не так), дефицит двудольного графа равен нулю (всем всего хватило). Множеством с максимальным дефицитом будет являться множество всех 10 вершин $%\{A;B;\ldots;J\}$%.

ссылка

отвечен 17 Май '14 7:57

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

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

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

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

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

отмечен:

×1,699

задан
16 Май '14 22:08

показан
861 раз

обновлен
17 Май '14 7:57

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

по почте:

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

по RSS:

Ответы

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

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