Число полных двудольных назначений: перманент по Райзеру
Посчитать все допустимые взаимно однозначные назначения по квадратной матрице совместимости 0/1, используя включения и исключения по подмножествам столбцов.
Ваш пример
Разбор примера
Полных назначений: 2
| Размер подмножества | Суммарный знаковый вклад |
|---|---|
| 0 | 0 |
| 1 | 0 |
| 2 | -6 |
| 3 | 8 |
- Использованы все 2^n подмножеств столбцов.
- Каждое полное назначение использует каждую строку и каждый столбец ровно один раз.
- Отрицательные промежуточные суммы являются включениями и исключениями, а не отрицательными количествами.
Метод и условия расчёта
Для каждого подмножества столбцов перемножаем суммы доступных вариантов по строкам.
Чередующаяся сумма со знаком (−1)^(n−|S|) удаляет назначения с повторным использованием столбца.
Теория к методу
Строки и столбцы задают две разные группы одинакового размера. Единица разрешает назначить данную пару. Перманент матрицы совместимости считает способы сопоставить каждому участнику ровно один объект так, чтобы каждый объект использовался один раз.
Сначала закрепите смысл строк и столбцов. Даже одинаковые внешние номера обозначают разные роли, например исполнителя и задачу, поэтому единица на диагонали не является петлёй графа. Матрица не обязана быть симметричной. Каждая перестановка столбцов задаёт ровно одно полное назначение: из каждой строки выбирается её собственный столбец, а повторов столбцов нет.
Пример: Для матрицы [[1,1,0],[1,0,1],[0,1,1]] допустимы назначения столбцов по строкам (1,3,2) и (2,1,3). Другие четыре перестановки используют хотя бы одну запрещённую ячейку. Ответ равен двум.
В матрице из четырёх единиц размера два на два также два полных назначения, хотя её определитель равен нулю. Этот отдельный контроль сразу опровергает подмену перманента определителем и не зависит от знаков в реализации Райзера.
Вопросы по теме
Перманент равен определителю?
Нет. В сумме по перестановкам у перманента все знаки положительные; определитель может обнулиться при наличии нескольких назначений.
Нулевой ответ — ошибка данных?
Нет. Для корректной матрицы это означает отсутствие полного назначения; частичное паросочетание всё ещё может существовать.
Графы и маршруты: объяснения, примеры и практика
Основа объяснения
Объяснения и примеры подготовлены для erudeet. По ссылкам можно сверить определения и условия модели.