Информатика · объяснение и практика

Сколько полных назначений разрешает совместимость: перманент без знаков перестановок

Посчитать все полные взаимно однозначные назначения по матрице совместимости и объяснить формулу Райзера через включения и исключения.

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Графы и маршруты · Учебная карта

Главная мысль

Строки и столбцы задают две разные группы одинакового размера. Единица разрешает назначить данную пару. Перманент матрицы совместимости считает способы сопоставить каждому участнику ровно один объект так, чтобы каждый объект использовался один раз.

Метод и постановка

Сначала закрепите смысл строк и столбцов. Даже одинаковые внешние номера обозначают разные роли, например исполнителя и задачу, поэтому единица на диагонали не является петлёй графа. Матрица не обязана быть симметричной. Каждая перестановка столбцов задаёт ровно одно полное назначение: из каждой строки выбирается её собственный столбец, а повторов столбцов нет.

Произведение выбранных нулей и единиц равно единице только для полностью разрешённой перестановки. Сумма таких произведений по всем перестановкам и есть перманент. В отличие от определителя знаки перестановок здесь не чередуются: допустимые назначения не должны взаимно уничтожаться из-за порядка меток. Поэтому обращать матрицу или брать модуль определителя как общий метод подсчёта нельзя.

Проверка и границы вывода

Формула Райзера рассматривает подмножества столбцов. Для фиксированного подмножества сумма в каждой строке считает доступные в нём варианты, а произведение строковых сумм считает независимые выборы строк с возможными повторениями столбца. Включения и исключения по всем подмножествам устраняют выборы, которые не используют весь набор столбцов. При равном числе строк и столбцов использование всех столбцов автоматически исключает повторы.

Промежуточные знаковые вклады могут быть отрицательными; итоговое количество неотрицательно и не превосходит факториала размера. Для маленькой матрицы независимая проверка перебирает перестановки напрямую, то есть использует другое перечисление объектов. Нулевой результат не означает неверный ввод: полного назначения может не быть при существовании частичных пар. Поиск одного максимального паросочетания отвечает на вопрос о достижимом размере, но не сообщает, сколько полных вариантов существует. Инструмент ограничивает размер матрицы, поскольку даже этот способ требует экспоненциального числа подмножеств.

Пример

Для матрицы [[1,1,0],[1,0,1],[0,1,1]] допустимы назначения столбцов по строкам (1,3,2) и (2,1,3). Другие четыре перестановки используют хотя бы одну запрещённую ячейку. Ответ равен двум.

В матрице из четырёх единиц размера два на два также два полных назначения, хотя её определитель равен нулю. Этот отдельный контроль сразу опровергает подмену перманента определителем и не зависит от знаков в реализации Райзера.

От чтения к действию

А теперь — вы

У матрицы два на два все четыре ячейки разрешены. Сколько полных взаимно однозначных назначений?

Частые вопросы

Перманент равен определителю?

Нет. В сумме по перестановкам у перманента все знаки положительные; определитель может обнулиться при наличии нескольких назначений.

Нулевой ответ — ошибка данных?

Нет. Для корректной матрицы это означает отсутствие полного назначения; частичное паросочетание всё ещё может существовать.

Углублённый разбор

Чётность перманента и односторонний тест назначения

Определитель не считает назначения над целыми, но по модулю два его знаки исчезают. Это позволяет быстро сертифицировать нечётность числа полных назначений и тем самым их существование, сохраняя важное ограничение обратного вывода.

Перед началом: Перманент бинарной матрицы; Арифметика GF(2).

Два разных полинома совпадают после изменения поля

Перманент суммирует произведения по всем перестановкам с положительными знаками. Определитель использует те же произведения, но умножает их на знак перестановки. В поле GF(2) числа 1 и−1 совпадают, поэтому detA≡perA по модулю 2. Это точное тождество для любой квадратной целочисленной матрицы после редукции коэффициентов.

Для бинарной матрицы perA равен количеству допустимых полных назначений. Следовательно, detA=1 в GF(2) означает нечётное положительное число назначений. Проверка обратимости бинарной матрицы становится достаточным сертификатом существования. Но она не сообщает, равно ли число вариантов 1,3 или большему нечётному числу.

Нулевой определитель имеет одностороннее значение

Если detA=0 в GF(2), число назначений чётно. Оно может быть 0,2,6 или другим чётным числом. Поэтому тест не решает задачу существования в обе стороны. Линейная зависимость строк по модулю 2 не равносильна невозможности полного двудольного паросочетания, которое задаётся иной комбинаторной структурой.

Именно это отличает такой сертификат от полноценного алгоритма максимального паросочетания. При ответе 1 существование доказано;при 0 нужен другой метод, если цель — узнать наличие. Если цель состоит только в чётности, оба ответа точны. Название задачи должно сохраняться в отчёте, чтобы полезный односторонний вывод не превратился в ложный двусторонний критерий.

Исключение выполняется в поле, а не обычным делением

В GF(2) сложение совпадает с XOR, а единственный ненулевой ведущий элемент равен 1. Строковые исключения можно выполнять побитно, сохраняя точность. Полный ранг означает определитель 1;недостаточный ранг —0. Округлений и порога «почти ноль»в этой постановке нет.

Для независимой проверки небольшой матрицы следует перечислить все перестановки столбцов, отобрать разрешённые и сравнить чётность их количества. Этот маршрут не использует строковое исключение и обнаруживает ошибку в выборе поля. Обычный вещественный определитель либо его модуль нельзя без редукции выдавать за полученную чётность.

Нечётный сертификат и неопределённый ноль

Условие. Для A=[[1,1,0],[1,1,1],[0,1,1]] найдите чётность назначений. Сравните с матрицей B размера 3×3, состоящей из единиц.

  1. У A целый определитель равен−1, поэтому в GF(2) он равен 1. Число полных назначений нечётно и положительно.
  2. Прямой перебор находит три перестановки столбцов:(1,2,3),(2,1,3),(1,3,2). Это подтверждает нечётность, но количество 3 не равно модулю определителя 1.
  3. У B три одинаковые строки, поэтому определитель нулевой и в GF(2). Однако все 3!=6 назначений разрешены.
  4. Таким образом, нулевой ответ теста не исключает существование. Он даёт ровно чётность, а не число и не отрицательный сертификат паросочетания.

Ответ. У A чётность 1 и три назначения;у B чётность 0, но шесть назначений.

Проверка. Два независимых перечисления шести перестановок дают 3 и 6 разрешённых вариантов. Их остатки по 2 совпадают с определителями, не совпадая с целыми значениями либо модулем−1.

Где легко ошибиться. Нулевой определитель в GF(2) не означает отсутствие назначения. Сохраняйте односторонность вывода: ненулевой сертификат доказывает существование, нулевой лишь чётность.

Проверьте понимание

Что означает detA=0 в GF(2) для бинарной матрицы?

Вопросы к этой главе

Можно использовать любой простой модуль?

Равенство знаков 1 и−1 характерно для характеристики 2. При нечётном модуле определитель по-прежнему содержит различающиеся знаки и в общем случае не совпадает с перманентом.

Тест обещает единственность при ответе 1?

Нет. Он допускает любое нечётное число решений. Для единственности понадобится более сильный структурный либо полный счётный сертификат.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • NIST DLMF: §1.3 and §26.15

    Прочитаны определитель со знаками перестановок и его разложение. Сравнение с перманентом в GF(2), односторонний вывод и собственные матрицы главы доказаны отдельно.

Какие единицы матрицы входят хотя бы в одно полное назначение

Единица матрицы совместимости может не входить ни в одно полное назначение. Одно найденное паросочетание и чередующиеся циклы позволяют классифицировать такие клетки без повторного полного поиска для каждой из них.

Перед началом: Полное паросочетание; Сильная компонента.

Относительно одного назначения переобозначьте столбцы

Пусть квадратная бинарная матрица имеет полное паросочетание M. Перенумеруем столбцы так, чтобы M состояло из диагональных клеток(i,i). Построим направленный граф индексов: каждая недиагональная разрешённая клетка(i,j) даёт дугу i→j. Диагональные клетки уже входят в M и потому автоматически допустимы хотя бы в одном полном ответе.

Если i→j лежит на направленном цикле, можно сдвинуть назначения вдоль этого цикла: каждая строка получит следующий столбец, а остальные сохранят диагональные пары. Все столбцы останутся различными. Поэтому каждая клетка такого цикла входит в некоторое полное назначение, даже если не использовалась в исходном M.

Разность двух назначений доказывает необходимость цикла

Сравним M с любым другим полным назначением M′. Их симметрическая разность распадается на непересекающиеся чётные циклы, где рёбра двух назначений чередуются. После стягивания диагональных пар каждый такой цикл становится направленным циклом графа индексов. Значит любая недиагональная клетка, используемая M′, обязательно лежит на таком цикле.

Для дуги i→j это равносильно существованию обратного пути j→i, то есть принадлежности концов одной сильной компоненте. Так все недиагональные клетки классифицируются одним разбиением на компоненты. Дуга между разными компонентами может быть разрешена матрицей, но не поддерживается ни одним полным назначением.

Поддерживаемая клетка не обязана быть обязательной

Условие «входит хотя бы в одно»отличается от «входит во все». Недиагональная поддерживаемая клетка не является обязательной, поскольку исходное M её не использует. Диагональная клетка может исчезнуть при переключении цикла через её индекс. Если такого нетривиального цикла нет, она остаётся вынужденной.

Предпосылка полного M существенна. В прямоугольной задаче со свободными значениями появляются ещё чередующиеся пути, и описанного критерия только циклов недостаточно. Также отсутствие полного паросочетания нельзя исправить классификацией его несуществующих диагональных пар: сначала решается задача существования, затем фильтрация допустимых клеток.

Разрешённый переход без обратного пути

Условие. В матрице 5×5 разрешены все клетки двух блоков строк/столбцов{1,2}и{3,4}, клетка(5,5) и дополнительная(2,3). Классифицируйте лишнюю клетку и обязательность(5,5).

  1. Диагональ является полным M. В графе индексов есть циклы 1↔2 и 3↔4, переход 2→3 и изолированный индекс 5.
  2. Сильные компоненты равны{1,2},{3,4},{5}. Из 3 нет пути обратно в 2, поэтому(2,3) не входит ни в одно полное назначение.
  3. Каждый из двух блоков допускает две перестановки, и их независимый выбор даёт четыре полных назначения. Ни одно не использует межблочный переход.
  4. Строка 5 имеет единственный столбец 5, поэтому(5,5) входит во все четыре ответа. Клетки внутри двух блоков поддерживаются, но по отдельности не обязательны.

Ответ. (2,3) не поддерживается; (5,5) обязательна;полных назначений четыре.

Проверка. Полный перебор 120 перестановок даёт ровно четыре ответа. Частота(2,3) равна 0,(5,5) равна 4, а каждой из восьми внутриблочных клеток —2.

Где легко ошибиться. Разрешённая клетка и клетка, поддерживаемая полным назначением, не одно и то же. Критерий сильных компонент применяется после нахождения полного паросочетания и согласованной перенумерации.

Проверьте понимание

Какая разрешённая клетка не используется ни одним полным ответом?

Вопросы к этой главе

Почему переключение цикла не повторяет столбец?

Цикл переставляет один и тот же набор индексов циклически. Каждый его столбец получает ровно одна строка, а вне цикла назначения не меняются.

Можно вычеркнуть неподдерживаемые клетки перед подсчётом?

Да. Они не входят ни в один считаемый полный объект, поэтому их удаление сохраняет множество полных назначений и перманент, хотя меняет исходную матрицу совместимости.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Google OR-Tools: all_different.cc

    Первичная реализация разработчиков: прочитаны построение максимального паросочетания и фильтрация через strongly connected components. Глава ограничена квадратной системой с уже полным паросочетанием;собственное стягивание пар и пример не копируют программный тест.

Гафниан считает совершенные паросочетания общего графа

Гафниан складывает веса всех разбиений вершин на непересекающиеся пары. Он считает совершенные паросочетания общего неориентированного графа без искусственного деления вершин на две доли. Вес объекта равен произведению весов его рёбер, а не их сумме.

Перед началом: Совершенное паросочетание; Симметричная матрица весов графа.

Разбиение на пары не является перестановкой назначений

Пусть A — симметричная матрица размера 2n с нулевой диагональю. Для каждого разбиения множества индексов на n неупорядоченных пар берётся произведение соответствующих элементов A. Сумма этих произведений называется гафнианом. Каждое разбиение учитывается один раз: перестановка пар и обмен концов одной пары нового объекта не создают.

Если элементы A равны нулю или единице, произведение равно единице ровно для совершенного паросочетания разрешённого графа. При положительных весах получается взвешенный перечислитель. Он отличается от перманента общей матрицы: назначение строки столбцу может образовать длинный цикл или использовать вершину одновременно в нескольких ролях, чего разбиение на пары не допускает.

Фиксация партнёра исключает повторный счёт

Выберем наименьшую оставшуюся вершину i. В каждом полном спаривании у неё единственный партнёр j. Поэтому гафниан остатка равен сумме Aij, умноженных на гафниан матрицы после удаления i,j. Ветви для разных j не пересекаются, а любое совершенное спаривание попадает в одну из них.

Пустой остаток имеет значение один: все необходимые пары уже выбраны, и пустое произведение завершает одну допустимую ветвь. Нечётное число оставшихся вершин даёт ноль. Эта рекурсия удобна для небольших точных расчётов и запоминания результатов по маске оставшихся вершин. Простое вычисление остаётся экспоненциальным; оно не превращает общий подсчёт в полиномиальную процедуру.

Знаки и веса меняют смысл ответа

В гафниане отсутствуют чередующиеся знаки. Поэтому положительные вклады разных спариваний не уничтожают друг друга, как могут уничтожаться численные слагаемые пфаффиана. Для произвольных отрицательных или комплексных весов сокращения возможны уже из-за самих весов; тогда ненулевое число больше нельзя читать как обычное количество объектов.

В примере удобно отдельно перечислить поддерживаемые паросочетания и их произведения. Это проверяет сразу две потенциальные ошибки: повторный учёт перестановок одних пар и подмену взвешенной суммы количеством ненулевых вариантов. Для симметричной матрицы направление записи ребра не должно менять ни одну из этих величин.

Шесть допустимых спариваний дают сумму тридцать два

Условие. На вершинах 1,…,6 ненулевые веса равны 12:2,13:1,16:1,24:3,25:1,34:1,35:2,46:1,56:4. Остальные веса нулевые. Найдите гафниан и обычное число совершенных паросочетаний поддержки.

  1. Партнёрами вершины 1 могут быть только 2,3,6. Эти три случая непересекаются и покрывают все ненулевые спаривания.
  2. При паре 12 остаток 3456 даёт 34·56+35·46=1·4+2·1=6. С учётом веса 12 вклад равен 2·6=12.
  3. При паре 13 остаток 2456 даёт 24·56+25·46=3·4+1·1=13. Вес пары 13 равен единице, вклад остаётся 13.
  4. При паре 16 остаток 2345 даёт 24·35+25·34=3·2+1·1=7. Полная сумма равна 12+13+7=32.
  5. Ненулевых спариваний шесть, их веса равны 8,4,12,1,6,1. Сложение снова даёт 32, тогда как замена всех ненулевых весов единицами дала бы 6.

Ответ. Взвешенный гафниан равен 32; поддержка графа имеет 6 совершенных паросочетаний.

Проверка. Перебор всех 15 разбиений шести вершин на пары оставляет ровно шесть ненулевых произведений. Независимое перечисление перестановок с канонизацией пар подтверждает тот же список без кратного счёта.

Где легко ошибиться. Не суммируйте веса рёбер внутри спаривания. Гафниан использует произведение, а затем складывает вклады разных полных разбиений.

Проверьте понимание

Чему равен взвешенный гафниан матрицы из примера?

Вопросы к этой главе

Зачем пустому остатку приписывать единицу?

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

Когда гафниан превращается в перманент?

Если граф двудольный и ненулевые элементы лежат только в двух перекрёстных блоках B и Bᵀ, каждое полное спаривание является биекцией долей. Тогда гафниан такой блочной матрицы равен per(B).

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

Ладейный многочлен считает назначения всех размеров

Перманент квадратной матрицы считает только полные назначения. Ладейный многочлен сохраняет количества совместимых назначений каждого размера, включая неполные и пустое. Разделение по использованию одной выбранной клетки даёт рекурсию с двумя разными остаточными досками. Коэффициент показывает число наборов пар, а степень многочлена — максимальный достижимый размер, но эти два вида информации нельзя смешивать.

Перед началом: Паросочетание строк и столбцов; Коэффициенты производящего многочлена.

Один коэффициент соответствует одному размеру назначения

Конечная, возможно прямоугольная, таблица разрешённых пар; выбранные клетки не делят строку или столбец; допускается пустое назначение.

Пусть B — набор разрешённых клеток. Обозначим r_k число способов выбрать k клеток, не повторяя ни строку, ни столбец. Их порядок не важен: назначение является множеством пар. Ладейный многочлен R_B(z)=Σr_k z^k имеет r₀=1, поскольку пустой набор допустим ровно одним способом.

Коэффициент r₁ равен числу разрешённых клеток. Старшая ненулевая степень равна размеру максимального паросочетания, но старший коэффициент считает, сколько таких паросочетаний существует. Для квадратной n×n матрицы rₙ совпадает с перманентом; остальные коэффициенты он сам по себе не сообщает.

Использование клетки исключает всю её строку и столбец

Выберем разрешённую клетку q. В назначениях без q просто удаляем эту клетку, сохраняя другие клетки её строки и столбца. В назначениях с q удаляем уже всю её строку и весь столбец: остальные пары не могут с ними пересекаться. Получаем R_B(z)=R_{B\q}(z)+zR_{B\(row(q)∪col(q))}(z).

Множитель z означает одну уже взятую пару. Две ветви непересекаются и охватывают все назначения, поэтому рекурсия точна. Пустая доска имеет многочлен 1, даже если в исходном прямоугольнике остались пустые строки. Если вместо удаления клетки в первой ветви тоже убрать её строку, будут потеряны назначения через другие клетки этой строки.

Произведение требует независимых строк и столбцов

Если B разбита на две части, которые не имеют общих строк и общих столбцов, то R_B=R₁R₂. Коэффициенты перемножаются свёрткой: независимо выбираем i пар из первой части и k−i из второй. Простого отсутствия общей клетки недостаточно, потому что две разные клетки одной строки конфликтуют.

Рекурсия применима к небольшим разреженным таблицам, но без дополнительных свойств не даёт полиномиального общего подсчёта. Для проверки короткого примера можно независимо перечислить подмножества разрешённых клеток и отфильтровать повторы строк и столбцов. Это другое перечисление, чем рекурсивное удаление, и оно проверяет каждый коэффициент сразу.

Шесть разрешённых пар дают разные количества частичных решений

Условие. Строки A,B,C и столбцы 1,2,3,4. Разрешены A1,A2,B2,B3,C1,C4. Найдите ладейный многочлен, число двухпарных и полных по строкам назначений. Для рекурсии выберите клетку A2.

  1. Без A2 остаются A1,B2,B3,C1,C4. Для этой доски r₀=1,r₁=5,r₂=7,r₃=2, поэтому первая ветвь равна 1+5z+7z²+2z³.
  2. При использовании A2 удаляем строку A и столбец 2. Остаются B3,C1,C4. Их многочлен равен 1+3z+2z²; после учёта выбранной клетки вклад равен z+3z²+2z³.
  3. Складываем ветви: R_B=1+6z+10z²+4z³. Следовательно двухпарных назначений десять, полных по всем трём строкам четыре.
  4. Проверим старший коэффициент напрямую: из восьми независимых выборов по два варианта на строку два запрещены конфликтом A1,C1 и ещё два — A2,B2. Эти группы не пересекаются, остаётся четыре решения.

Ответ. R_B(z)=1+6z+10z²+4z³. Двухпарных назначений 10, трёхпарных 4; общее число частичных назначений с пустым равно 21.

Проверка. Независимый перебор 64 подмножеств шести разрешённых клеток даёт коэффициенты 1,6,10,4. Для двух пар можно отдельно сложить вклады пар строк: AB даёт 3, AC даёт 3, BC даёт 4.

Где легко ошибиться. Не умножайте многочлены частей, которые используют общий столбец или строку. Тогда произведение посчитает конфликтующие выборы как независимые.

Проверьте понимание

Каков коэффициент при z² у ладейного многочлена разобранной таблицы?

Вопросы к этой главе

Ладьи считаются различимыми?

Нет. Считается набор занятых клеток. Перестановка двух воображаемых названий ладей не создаёт новое назначение; дополнительный множитель k! здесь был бы ошибкой.

Почему трёхпарное назначение названо полным, хотя столбцов четыре?

В worked полнота явно означает назначить каждой из трёх строк по одному столбцу. Один столбец останется свободным. Для квадратной таблицы полнота одновременно охватывала бы обе стороны.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • University of Lethbridge — Rook Polynomials, правила I–III

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

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться