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

Паросочетание: как чередующийся путь увеличивает число пар

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

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

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

В маршруте Графы, разрезы и динамические запросы · 10 тем

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

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

Свободного прямого назначения может не оказаться

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

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

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

Пусть А может выполнять задания X и Y,а Б — только X. Сначала выбрали пару А−X. Теперь Б не может напрямую занять свободное Y,поскольку такого ребра нет, а X уже занято. Но путь Б−X−А−Y чередует невыбранное ребро, выбранное и снова невыбранное.

Оба конца пути свободны: Б ещё не назначен, Y не занято. Убираем А−X и добавляем Б−X вместе с А−Y. Каждая вершина снова участвует максимум в одной паре, а число пар выросло с одной до двух. Порядок промежуточных действий в реализации должен сохранять согласованность итогового назначения.

Пример

ДопустимыА−X,А−Y,Б−X. Было{А−X}. После переключения пути Б−X−А−Y стало{Б−X,А−Y}.

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

Максимальное число и невозможность простого добавления

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

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

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

А теперь — вы

Увеличивающий путь содержит три невыбранных ребра и два выбранных. Как изменится число пар после переключения?

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

Увеличивающий путь может начинаться занятой вершиной?

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

Наибольшее число назначений означает наилучшие предпочтения?

Нет. Для стоимости или предпочтений требуется дополнительная целевая функция, которой в этой модели нет.

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

Нечётные компоненты ограничивают размер общего паросочетания

В общем графе максимальное паросочетание ограничивают нечётные компоненты после удаления выбранного множества вершин. Формула Татта — Бержа утверждает, что лучшая такая граница точна. Она даёт сертификат оптимальности даже при наличии нечётных циклов, когда двудольный аргумент Холла неприменим.

Перед началом: Паросочетание; Компонента связности.

Нечётная компонента требует внешнего партнёра

Для конечного простого неориентированного графа G обозначим o(G−S) число компонент нечётного размера после удаления S. Внутреннее паросочетание каждой такой компоненты оставляет хотя бы одну вершину. Покрыть её извне можно только ребром в S: между различными компонентами G−S рёбер нет. Каждая вершина S участвует не больше чем в одном ребре паросочетания.

Следовательно в любом паросочетании остаётся не меньше o(G−S)−|S| непокрытых вершин. Если выражение отрицательное, оно просто даёт слабую границу; для S=∅ оно неотрицательно. Так размер любого паросочетания не превосходит (|V|−o(G−S)+|S|)/2. Один удачный выбор S вместе с конструкцией соответствующего размера уже способен доказать оптимальность.

Формула делает лучшую нечётную преграду точной

Теорема Татта — Бержа утверждает ν(G)=(|V|−def(G))/2, где def(G)=max_S(o(G−S)−|S|). Дефицит равен минимальному числу непокрытых вершин, а не числу недостающих рёбер. Поэтому множитель 1/2 в формуле существенен: каждое ребро покрывает две вершины. Все сравниваемые выражения имеют правильную чётность относительно |V|.

В частности, совершенное паросочетание существует ровно тогда, когда o(G−S)≤|S| для всех S. Для отрицательного ответа достаточно одного нарушающего множества, а положительное утверждение по этой формулировке требует всех S либо явного совершенного паросочетания. Не следует проверять лишь удаление одной вершины: более крупный барьер может обнаружить дефицит, который малые удаления не показывают.

Сертификат отделяет проверку от поиска

Поиск максимального паросочетания общего графа может требовать обработки нечётных циклов, но проверка пары свидетельств проще. Список попарно непересекающихся рёбер даёт нижнюю границу. Список компонент G−S, их размеры и величина o−|S| даёт верхнюю. Если они совпали, не нужно перебирать все S, чтобы удостоверить конкретный ответ. Полный перебор остаётся полезной независимой проверкой маленького примера, а не обязательным производственным алгоритмом.

Барьер из двух вершин

Условие. Есть вершины u,v,x,y,a,b,c,d,e,f. Треугольники abc и def имеют все свои рёбра; дополнительно есть uv,ux,ua,vy,vd. Других рёбер нет. Найдите максимум паросочетания и минимум непокрытых вершин.

  1. Удалим S={u,v}. Остаются четыре нечётные компоненты: {x},{y},{a,b,c},{d,e,f}. Поэтому o(G−S)−|S|=4−2=2.
  2. Любое паросочетание оставляет минимум 2 вершины и имеет не больше(10−2)/2=4 рёбер.
  3. Возьмём рёбра ux,vy,ab,de. Они попарно не имеют общих концов и покрывают 8 вершин; c,f остаются свободными.
  4. Получены нижняя граница 4 и верхняя 4. Следовательно ν=4, минимальное число непокрытых равно 2, а предъявленный S достигает максимального дефицита.

Ответ. Максимум 4 ребра; минимум 2 непокрытые вершины; S={u,v} — точный нечётный барьер.

Проверка. Независимый перебор всех подмножеств 11 рёбер подтверждает максимум 4. Отдельный перебор 1024 множеств S находит максимальный дефицит 2, не используя найденное паросочетание.

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

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

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

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

Почему две треугольные компоненты не могут полностью покрыться внутри себя?

У каждой 3 вершины, а внутренние рёбра паросочетания покрывают чётное число. Одна вершина обязательно останется для внешнего партнёра либо будет непокрыта.

Нужно ли доказать максимальность S отдельным перебором?

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

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

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

  • Jan Vondrák: CS369P Lecture4, §1.5

    Прочитаны Definition15 odd(H), Lemma16 о непокрытых вершинах и Theorem17/Corollary18 Татта — Бержа. Собственный граф с двухвершинным барьером, двумя одиночными и двумя треугольными компонентами проверяется полным перебором; алгоритм blossom не излагается.

Кососимметричная матрица Татта проверяет общее паросочетание

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

Перед началом: Кососимметричная матрица; Многочлен над конечным полем.

Одна переменная на неориентированное ребро

Пусть простой граф имеет чётное число n пронумерованных вершин. Над полем нечётной характеристики строим матрицу T: при i<j ставим Tᵢⱼ=xᵢⱼ, если ребро есть, иначе 0; ниже диагонали ставим отрицание того же элемента. Диагональ нулевая. Теорема Татта утверждает: detT не является тождественным нулём ровно тогда, когда граф имеет совершенное паросочетание.

Объяснение удобно через пфаффиан: каждый его моном соответствует разбиению всех вершин на рёберные пары, со знаком. Разные совершенные паросочетания используют разные множества переменных, поэтому дают разные мономы и не сокращаются символически. Поскольку detT=Pf(T)², ненулевость сохраняется. Число паросочетаний здесь не равно значению определителя: он служит тестом существования, а не суммой всех объектов без знаков.

Односторонняя ошибка возникает только при обнулении ненулевого полинома

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

При независимом равномерном выборе каждой переменной из конечного поля F_q лемма Шварца — Зиппеля ограничивает вероятность такой неудачи величиной n/q, поскольку степень detT не больше n. Это верхняя оценка по заявленному распределению, а не точная доля ошибок любой детерминированной последовательности. Повторение независимых проб уменьшает вероятность совместной неудачи; одинаковая повторная подстановка новой информации не даёт.

Метки рёбер нельзя заранее склеивать

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

Паросочетание есть, одна проба нулевая

Условие. Для полного графа K₄ выпишите пфаффиан. Сравните подстановки всех шести переменных равными 1 и подстановку x₁₃=2 при остальных 1 над F₁₀₁.

  1. Три совершенных паросочетания дают Pf=x₁₂x₃₄−x₁₃x₂₄+x₁₄x₂₃. Это ненулевой формальный многочлен с тремя различными мономами.
  2. При всех значениях 1 пфаффиан равен 1−1+1=1. Определитель равен 1, и проба доказывает существование совершенного паросочетания.
  3. При x₁₃=2 и остальных 1 пфаффиан равен 1−2+1=0; определитель тоже 0. Граф остался тем же, и пары {12,34}, {13,24}, {14,23} по-прежнему существуют.
  4. Следовательно вторая проба не решает отрицательный вопрос. Для независимой равномерной пробы над F₁₀₁ общая оценка неудачи det-теста равна не больше 4/101; конкретная заранее заданная плохая проба не имеет собственной случайной вероятности.

Ответ. Первая подстановка подтверждает существование, вторая является неудачной нулевой пробой при существующем паросочетании.

Проверка. Прямой перебор всех разбиений четырёх вершин на пары находит 3 объекта. Точный определитель 4×4 по перестановкам независимо даёт 1 и0 для двух матриц; это согласует алгебраическую и комбинаторную стороны.

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

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

Что доказывает нулевой результат второй подстановки для K₄?

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

Почему поле имеет нечётную характеристику?

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

Что делать при нечётном числе вершин?

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

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

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

  • Avrim Blum: 15-451 Lecture27, §3

    Прочитаны Schwartz–Zippel и определение кососимметричной матрицы Татта для общего графа. Собственные две подстановки K4, одна вырожденная, проверены определителем и тремя совершенными паросочетаниями. MIT6.842 lec4 прочитан, но его bipartite matrix не используется как источник общего skew-теста.

Венгерский алгоритм: равенство цены назначения и суммы потенциалов

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

Перед началом: Двудольное паросочетание и чередующийся путь; Сумма стоимости полного назначения.

Потенциалы строк и столбцов дают нижнюю границу

Для квадратной матрицы цен C выбираем по одной клетке в каждой строке и каждом столбце. Числа ui,vj называем допустимыми потенциалами, если ui+vj≤Cij для всех клеток. Суммируя эти неравенства по любому полному назначению, получаем его цену не меньше суммы всех ui и всех vj. Каждый потенциал встречается ровно один раз.

Клетка с Cij−ui−vj=0 называется точной. Если удалось найти полное назначение только по точным клеткам, его цена совпала с двойственной нижней границей. Это немедленно доказывает оптимальность. Отрицательные потенциалы столбцов допустимы: ограничения накладываются на суммы ui+vj, а не на знаки отдельных чисел.

Дефицит точных рёбер направляет обновление

Начать можно с минимумов строк ui=minj Cij и нулевых vj. Если точные клетки ещё не содержат полного паросочетания, строим чередующееся дерево от свободной строки: вперёд по точным неназначенным клеткам, обратно по занятым. Обозначим достигнутые строки ZR, достигнутые столбцы ZC. Пока свободный столбец не достигнут, увеличить паросочетание нельзя.

Величину δ выбираем как минимальный запас Cij−ui−vj среди i∈ZR,j∉ZC. Прибавим δ к потенциалам строк ZR и вычтем δ из потенциалов столбцов ZC. На пересечении двух достигнутых множеств сумма не меняется. На выходе из достигнутых строк запас уменьшается не больше чем до нуля. На входе в достигнутые столбцы запас возрастает. Все ограничения сохраняются.

Новое точное ребро продолжает поиск

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

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

Один двойственный шаг устраняет конфликт двух минимумов

Условие. Матрица цен имеет строки (5,4,3), (1,7,3), (5,6,2). Найдите оптимальное назначение и потенциалы. Строки и столбцы нумеруются с нуля.

  1. Начальные потенциалы u=(3,1,2), v=(0,0,0). Точные клетки равны (0,2),(1,0),(2,2). Выбор всех трёх минимумов недопустим: строки 0 и 2 требуют один столбец.
  2. Берём частичное назначение (0,2),(1,0), свободна строка 2. Её чередующееся дерево достигает столбца 2 и занятой им строки 0: ZR={2,0}, ZC={2}.
  3. Запасы к столбцам вне ZC равны 3,4 для строки 2 и 2,1 для строки 0. Значит, δ=1. Получаем u=(4,1,3), v=(0,0,−1).
  4. Новая точная клетка (0,1) выводит к свободному столбцу 1. Переключаем путь: строка 2 получает столбец 2, строка 0 — столбец 1, строка 1 сохраняет столбец 0.
  5. Цена назначения равна 4+1+2=7. Сумма потенциалов равна 4+1+3−1=7, а все девять неравенств ui+vj≤Cij выполнены. Совпадение удостоверяет глобальный минимум.

Ответ. Оптимальное назначение столбцов по строкам равно (1,0,2), цена 7; двойственная граница также равна 7.

Проверка. Перебор всех шести перестановок столбцов независимо подтверждает минимум 7. Проверка девяти ограничений подтверждает потенциалы; попытка увеличить их на δ=2 нарушила бы клетку (0,1).

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

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

Каков допустимый максимальный шаг δ для указанного чередующегося дерева?

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

Почему потенциал столбца стал отрицательным?

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

Почему берётся минимальный выходящий запас?

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

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

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

  • D. Bertsekas: A new algorithm for the assignment problem

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

Нечётный цветок сжимается при поиске увеличивающего пути

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

Перед началом: Чередующийся увеличивающий путь относительно паросочетания; Чётные и нечётные уровни дерева поиска.

У основания цветка сходятся два невыбранных ребра

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

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

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

Сжатая вершина должна помнить исходные точки входа

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

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

Размер matching проверяется после полного раскрытия

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

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

Короткая дуга внутри цветка имеет неправильную чётность

Условие. Вершины r,x,a,b,c,d,e,z. Рёбра rx,xa,ab,bc,ca,bd,de,ez; текущее паросочетание M={xa,bc,de}. Свободны r,z. Сожмите цветок abc с основанием a и раскройте увеличивающий путь.

  1. Стебель r—x—a имеет невыбранное rx и выбранное xa. В треугольнике abc выбранным является bc, а ab,ac невыбранные; основание a находится на чётном уровне.
  2. После сжатия abc в B остаётся паросочетание {xB,de}. Путь r—x—B—d—e—z чередует невыбранное, выбранное, невыбранное, выбранное, невыбранное ребро.
  3. Внешняя дуга B—d исходно выходила из b. Между a и b нельзя взять только ab: за ним шло бы ещё одно невыбранное bd. Берём a—c—b, где ac невыбрано, cb выбрано.
  4. Полный путь r—x—a—c—b—d—e—z имеет семь рёбер с правильным чередованием. Удаляем xa,bc,de, добавляем rx,ac,bd,ez. Получены четыре непересекающиеся пары, покрывающие все восемь вершин.

Ответ. Раскрытый увеличивающий путь r,x,a,c,b,d,e,z даёт совершенное паросочетание {rx,ac,bd,ez} размера 4.

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

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

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

Какой внутренний путь от a к точке выхода b сохраняет чередование в разобранном увеличении?

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

Почему треугольник здесь нельзя обработать как двудольные слои?

Из a путь через ab и выбранное bc достигает c на чётном уровне, но ребро ac соединяет уже две чётные вершины того же дерева. Такая ситуация требует цветка, а не произвольного запрета повторного посещения.

На сколько выросло паросочетание после раскрытия?

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

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

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

  • MIT 18.434 — Non-bipartite matching, flower and shrinking

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

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

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

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