Как найти максимальное паросочетание в двудольном графе

const int maxn;

vector<int> g[maxn]; // будем хранить только рёбра из левой доли в правую
int mt[maxn]; // с какой вершиной сматчена вершина правой доли (-1, если ни с какой)
bool used[maxn]; // вспомогательный массив для поиска пути dfs-ом

// dfs возвращает, можно ли найти путь из вершины v
// в какую-нибудь вершину правой доли
// если можно, то ещё и проводит чередование
bool dfs(int v) {
    if (used[v])
        return false;
    used[v] = true;
    for (int u : g[v]) {
        // если вершина свободна, то можно сразу с ней соединиться
        // если она занята, то с ней можно соединиться только тогда,
        // когда из её текущей пары можно найти какую-нибудь другую вершину
        if (mt[u] == -1 || dfs(mt[u])) {
            mt[u] = v;
            return true;
        }
    }
    return false;
}


// где-то в main:

memset(mt, -1, sizeof mt);
for (int i = 0; i < n; i++) {
    memset(used, 0, sizeof mt);
    if (dfs(i))
        cnt++;
}

В теории графов паросочетание, или независимое множество рёбер в графе, — это набор попарно несмежных рёбер.

Определение[править | править код]

Пусть дан граф G = (V,E), паросочетание M в G — это множество попарно несмежных рёбер, то есть рёбер, не имеющих общих вершин, т.е. .

Связанные определения[править | править код]

Максимальное паросочетание — это такое паросочетание M в графе G, которое не содержится ни в каком другом паросочетании этого графа, то есть к нему невозможно добавить ни одно ребро, которое бы являлось несмежным ко всем рёбрам паросочетания. Другими словами, паросочетание M графа G является максимальным, если любое ребро в G имеет непустое пересечение, по крайней мере, с одним ребром из M. Ниже приведены примеры максимальных паросочетаний (красные рёбра) в трёх графах^[1].

Наибольшее паросочетание (или максимальное по размеру паросочетание^[2])— это такое паросочетание, которое содержит максимальное количество рёбер.
Число паросочетания^[3]
графа  — это число рёбер в наибольшем паросочетании. У графа может быть множество наибольших паросочетаний. При этом любое наибольшее паросочетание является максимальным, но не любое максимальное будет наибольшим. Следующие три рисунка показывают наибольшие паросочетания в тех же трёх графах^[1].

Некоторые авторы используют термин «максимальное паросочетание» для наибольшего паросочетания^[4][5][6][7].

Совершенным паросочетанием (или 1-фактором) называется паросочетание, в котором участвуют все вершины графа. То есть любая вершина графа инцидентна ровно одному ребру, входящему в паросочетание. Фигура (b) на рисунке выше является примером такого паросочетания. Любое совершенное паросочетание является наибольшим и максимальным. Совершенное паросочетание является также рёберным покрытием минимального размера. В общем случае , где — число рёберного покрытия графа , иными словами, размер наибольшего паросочетания не превосходит размера наименьшего рёберного покрытия.

Почти совершенным паросочетанием называется паросочетание, в котором не участвует ровно одна вершина. Это может произойти, если граф имеет нечётное число вершин. На рисунке выше паросочетание в графе (c) является почти совершенным. Если для любой вершины в графе существует почти совершенное паросочетание, не содержащее именно эту вершину, граф называется факторно-критическим.

Пусть задано паросочетание M.

• чередующийся путь — это путь, в котором рёбра поочерёдно принадлежат паросочетанию и не принадлежат ему.
• пополняющий путь (или увеличивающий путь) — это чередующийся путь, начинающийся и кончающийся свободными вершинами (то есть не участвующими в паросочетании).

Лемма Бержа утверждает, что паросочетание является наибольшим в том и только в том случае, если не существует пополняющего пути.

Свойства[править | править код]

• Число совершенных паросочетаний в двудольном графе равно перманенту его матрицы смежности.
• В любом графе без изолированных вершин число паросочетания и число рёберного покрытия в сумме дают число вершин^[8].
  • В частности, если существует совершенное паросочетание, то оба числа равны |V| / 2.

• Если A и B — два максимальных паросочетания, то |A| ≤ 2|B| и |B| ≤ 2|A|. Чтобы это увидеть, заметьте, что каждое ребро из B A может быть сопряжено максимум двум рёбрам из A B поскольку A — паросочетание. Однако каждое ребро A B сопряжено с ребром B A ввиду того, что B — максимальное. Следовательно,

  

Далее мы имеем

• В частности, отсюда вытекает, что любое максимальное паросочетание является 2-аппроксимацией наибольшего паросочетания, а также 2-аппроксимацией минимального максимального паросочетания. Это неравенство точное. Например, если G — путь с тремя рёбрами и 4 вершинами, минимальный размер максимального паросочетания равен 1, а размер наибольшего паросочетания равен 2.

Многочлен паросочетаний[править | править код]

Производящая функция числа k-рёберных паросочетаний в графе называется многочлен паросочетаний.
Пусть G — граф и m_k — число k-рёберных паросочетаний.
Полиномом паросочетаний графа G будет

Есть другое определение полинома паросочетаний

,

где n — число вершин в графе.
Оба определения имеют свои области применения.

Алгоритмы и вычислительная сложность[править | править код]

Наибольшее паросочетание в двудольном графе[править | править код]

Задачи нахождения паросочетания часто возникают при работе с двудольными графами. Поиск наибольшего паросочетания в двудольном графе^[9]
является, пожалуй, простейшей задачей.
Алгоритм пополняющего пути получает его, находя пополняющий путь из каждой вершины в и добавляя его в паросочетание, если путь будет найден. Альтернативный способ решения заключается в том, что паросочетание будет дополняться до тех пор, пока существуют расширяющие дополняющие пути:

1. Установи .
2. Пока имеются расширяющие пополняющие пути :
   1. , где – симметрическая разность множеств.

Пополняющий путь – это путь вида , для которого истинно при . Пополняющий путь называется расширяющим, если .

Лемма: Для любого графа , паросочетания и пополняющего пути справедливо паросочетание и . Доказательство: Пусть , и – начальная вершина , так что и , а также – последняя вершина , так что и , и – промежуточная вершина , так что . Из этого следует, что в граф будет добавлено на одно ребро больше, чем удалено из него.

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

• является изолированной вершиной или
• является циклом четной длины или
• является путем четной длины или
• является путем нечетной длины

Вершины в происходят попеременно из и . Пусть

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

Найти дополняющий путь можно следующим образом:

1. Даны двудольный граф и паросочетание .
2. Создай , где
   1. 
   2. 
3. Поиск дополняющего пути сводится к поиску в из свободной вершины в свободную вершину .

Поскольку пополняющий путь может быть найден за – время поиска в глубину, время работы алгоритма составит . Это решение эквивалентно добавлению суперисточника с рёбрами ко всем вершинам , и суперстока с рёбрами из всех вершин (трансформация графа займет , и поиску максимального потока из в . Все рёбра, по которым идёт поток из в , образуют максимальное паросочетание, а размер наибольшего паросочетания будет равен величине потока. Несколько быстрее работает алгоритм Хопкрофта — Карпа, работающий за время . Другой подход базируется на алгоритме быстрого умножения матриц и даёт сложность ^[10], что в теории лучше для достаточно плотных графов, но на практике алгоритм медленнее.^[11]

Во взвешенном двудольном графе[править | править код]

Во взвешенном двудольном графе каждому ребру приписывается вес. Паросочетание максимального веса в двудольном графе^[9] определяется как паросочетание, для которого сумма весов рёбер паросочетания имеет максимальное значение. Если граф не является полным двудольным, отсутствующие рёбра добавляются с нулевым весом. Задача поиска такого паросочетания известна как задача о назначениях. Замечательный венгерский алгоритм решает задачу о назначениях и был одним из первых алгоритмов комбинаторной оптимизации. Задача может быть решена с помощью модифицированного поиска кратчайшего пути в алгоритме пополняющего пути.
Если используется алгоритм Беллмана — Форда, время работы будет , или цену ребра можно сдвинуть для достижения времени при применении алгоритма Дейкстры с Фибоначчиевой кучей^[12].
^[13]

Наибольшие паросочетания[править | править код]

Имеется алгоритм полиномиального времени для нахождения наибольшего паросочетания или паросочетания максимального веса в графе, не являющемся двудольным. Следуя Джеку Эдмондсу^[en] его называют методом путей, деревьев и цветов или просто алгоритмом Эдмондса для паросочетаний. Алгоритм использует двунаправленные дуги^[en].
Обобщение той же техники может быть использовано для поиска максимального независимого множества в графах без клешней. Алгоритм Эдмодса был впоследствии улучшен до времени работы , что соответствует алгоритмам для двудольных графов^[14].
Другой (рандомизированный) алгоритм, разработанный Муча и Санковсим (Mucha, Sankowski)^[10], основанный на быстром произведении матриц, даёт сложность .

Максимальные паросочетания[править | править код]

Максимальное паросочетание можно найти простым жадным алгоритмом.
Cамым большим максимальным паросочетанием является наибольшее паросочетание, которое может быть найдено за полиномиальное время. Pеализация с использованием псевдокода:

1. Дан граф .
2. Установи .
3. Пока множество не пустое:
   1. Выбери .
   2. Установи .
   3. Установи .
4. Выведи .

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

Заметим, что наибольшее паросочетание из k рёбер является рёберным доминирующим множеством с k рёбрами. И обратно, если задано минимальное рёберное доминирующее множество с k рёбрами, мы можем построить наибольшее паросочетание с k рёбрами за полиномиальное время. Таким образом, задача нахождения минимального по размеру максимального паросочетания эквивалентна задаче нахождения минимального рёберного доминирующего множества^[15]. Обе эти задачи оптимизации известны как NP-трудные, а их распознавательные версии являются классическими примерами NP-полных задач^[16]. Обе задачи могут быть аппроксимированы с коэффициентом 2 с полиномиальным временм — просто находим произвольное максимальное паросочетание M^[17].

Задачи перечисления[править | править код]

Число паросочетаний в графе известно как индекс Хосойи. Вычисление этого числа является #P-полной задачей. Задача остаётся #P-полной в специальном случае перечисления совершенных паросочетаний в двудольном графе, поскольку вычисление перманента случайной 0-1 матрицы (другая #P-полная задача) — это то же самое, что вычисление числа совершенных паросочетаний в двудольном графе, имеющем заданную матрицу в качестве матрицы смежности. Существует, однако, рандомизированная аппроксимационная схема полиномиального времени для вычисления числа паросочетаний в двудольном графе^[18]. Замечательная теорема Кастелейна^[en], утверждающая, что число совершенных паросочетаний в планарном графе может быть вычислено в точности за полиномиальное время с помощью алгоритма FKT.

Число совершенных паросочетаний в полном графе K_n (с чётным n) задаётся двойным факториалом (n − 1)!!^[19]. Число паросочетаний в полном графе без ограничения, чтобы паросочетание было совершенным, задаётся телефонными номерами^[en][20].

Нахождение всех рёбер, паросочетаемых рёбер[править | править код]

Одной из основных задач в теории паросочетаний является поиск всех рёбер, которые могут быть расширены до наибольшего паросочетания. Лучший детерминированный алгоритм решения этой задачи работает за время ^[21].
Существует рандомизированный алгоритм, решающий задачу за время ^[22].
В случае двудольного графа можно найти наибольшее паросочетание и использовать его для нахождения всех максимально-паросочетаемых рёбер за линейное время^[23];
что даст в результате для общих двудольных графов и для плотных двудольных графов с .
В случае, если одно из наибольших паросочетаний известно заранее^[24], общее время работы алгоритма будет .

Характеристики и замечания[править | править код]

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

Теорема Холла (или теорема о свадьбах) обеспечивает характеризацию двудольных графов, имеющих совершенные паросочетания, а теорема Татта даёт характеризацию произвольных графов.

Совершенное паросочетание порождает остовный 1-регулярный подграф, то есть 1-фактор. В общем случае остовный k-регулярный подграф — это k-фактор.

Приложения[править | править код]

Структурная формула Кекуле ароматических соединений состоит из совершенных паросочетаний их углеродного скелета, показывая местоположение двойных связей в химической структуре. Эти структуры названы в честь Фридриха Августа Кекуле, который показал, что бензол (в терминах теории графов — это цикл из 6 вершин) может быть представлен в виде такой структуры^[25].

Индекс Хосойи — это число непустых паросочетаний плюс единица. Он применяется в вычислительной и математической химии для исследования органических соединений.

См. также[править | править код]

• Рёберная раскраска
• Независимое множество
• Декомпозиция Далмейджа-Мендельсона
• Устойчивое паросочетание
• Оптимальное паросочетание^[en]
• Кососимметический граф^[en]
• Словарь терминов теории графов

Примечания[править | править код]

Литература для дальнейшего чтения[править | править код]

1. László Lovász, Michael D. Plummer. Matching Theory. — North-Holland, 1986. — ISBN 0-444-87916-1.
2. Introduction to Algorithms. — second. — MIT Press and McGraw–Hill, 2001. — ISBN 0-262-53196-8.

1. S. J. Cyvin, Ivan Gutman. Kekule Structures in Benzenoid Hydrocarbons. — Springer-Verlag, 1988.
2. Marek Karpinski, Wojciech Rytter. Fast Parallel Algorithms for Graph Matching Problems. — Oxford University Press, 1998. — ISBN 978-0-19-850162-6.

Ссылки[править | править код]

• Пример решения задачи на YouTube Архивная копия от 22 марта 2016 на Wayback Machine
• Алгоритм поиска наибольшего паросочетания в двудольном графе Архивная копия от 7 января 2012 на Wayback Machine
• A graph library with Hopcroft-Karp and Push-Relabel-based maximum cardinality matching implementation Архивная копия от 25 октября 2005 на Wayback Machine

Паросочетание в двудольном графе

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

Свойства

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

Пример максимального и полного паросочетания, чередующейся цепи

Теорема о максимальном паросочетании и дополняющих цепях

См. также

• Теорема Холла
• Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах
• Связь вершинного покрытия и независимого множества

Источники информации

• Wikipedia — Matching
• Википедия — Паросочетание
• Асанов М. О., Баранский В. А., Расин В. В. — Дискретная математика: Графы, матроиды, алгоритмы. стр. 227-232 ISBN 978-5-8114-1068-2

Паросочетанием в неориентированном
графе G=(V,E) называется произвольное
множество ребер ME,
такое, что никакие два ребра из M не
инцидентны одной вершине. Вершины в G,
не принадлежащие ни одному ребру
паросочетания, называют свободными.
Граф G называют двудольным, если его
множество вершин можно разбить на
непересекающиеся множества – V=XY,
XY=,
причем каждое ребро eE
имеет вид e=(x,y), где xX,
yY. Двудольный граф
будем обозначать G=(X,Y,E).

Задача нахождения наибольшего
паросочетания в двудольном графе
сводится к построению максимального
потока в некоторой сети. Рассмотрим
схему сведения. На рисунке показан
исходный двудольный граф G. Построим
сеть S(G) с источником s и стоком t следующим
образом:

• источник s соединим дугами с вершинами
  из множества X;

• вершины из множества Y соединим дугами
  со стоком t;

• направление на ребрах исходного графа
  будет от вершин из X к вершинам из Y;

• пропускная способность всех дуг
  C[i,j]=1.

Найдем максимальный поток из s в t
для построенной сети. Он существует[11].
Насыщенные дуги потока (они выделены
“жирными” линиями на рисунке соответствуют
ребрам наибольшего паросочетания
исходного графа.

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

Рассмотрим другой метод построения
наибольшего паросочетания в двудольном
графе. Введем понятие чередующейся
цепи из X в Y относительно данного
паросочетания M. Произвольное множество
дуг PE вида:

P={(x₀,y₁), (y₁,x₁),
(x₁,y₂), …, (y_k,x_k),
(x_k,y_k+1)},

где k>0, все вершины различны, x₀
– свободная вершина в X, y_k+1 – свободная
вершина в Y, и каждая вторая дуга
принадлежит M, то есть

PM={(y₁,x₁),
(y₂,x₂), …, (y_k,x_k)}.

Теорема[3]. Паросочетание M в двудольном
графе G наибольшее тогда и только тогда,
когда в G не существует чередующейся
цепи относительно M.

Теорема подсказывает реальный путь
нахождения

наибольшего паросочетания. Пусть найдено
некоторое паросочетание в графе G, на
рисунке оно выделено “жирными” линиями.
Ищем чередующуюся цепь – ее дуги выделены
линиями со стрелками.

Она состоит из “тонких” дуг и “жирных”,
причем начинается и заканчивается в
свободных вершинах. Длина цепи нечетна.
Делаем “тонкие” дуги “жирными” и
наоборот. Паросочетание увеличено на
единицу.

Общая логика.

begin

<ввод и инициализация данных>;

<найти первое паросочетание>;

while <есть чередующаяся цепочка?> do
<изменить паросочетание>;

<вывод результата>;

end.

Очередь за определением данных и
последовательным уточнением логики.
Граф описывается матрицей А[N,M], где N –
количество вершин в множестве X, а M в Y.
Паросочетание будем хранить в двух
одномерных массивах XN и YM. Для рассмотренного
примера XN=[0,1,2,4] и YM=[2,3,0,4,0]. Уточнение
фрагмента “найти первое паросочетание”
не требует разъяснений.

for i:=1 to N do begin {назначение переменных i,
j, pp следует очевидно}

j:=1; pp:=true;

while
(j<=M) and pp do begin

if
(A[i,j]=1) and (YM[j]=0) then begin

XN[i]:=j;YM[j]:=i;

pp:=false;

end;

inc(j);

end;

end;

Как лучше хранить
чередующуюся цепочку, учитывая требование
изменения паросочетания и продумывая
логику её построения? Естественно,
массив, пусть это будет Chain:array[1..NMmax]
of -NMmax.. NMmax, где NMmax – максимальное число
вершин в графе, и его значение для
рассмотренного примера равно [1, -4, 4, -2,
3, -3], то есть вершины из множества YM
хранятся со знаком минус (вспомните
метод построения максимального потока).
Итак, поиск чередующейся цепочки.

function FindChain:boolean;

var p,yk,r:word;

begin

<инициализация данных, в частности
yk:=1;>;

<нахождение свободной вершины в XN>;

if <вершина
не найдена>
then begin FindChain:=false;exit;end;

p:=<номер первой свободной
вершины>;

Chain[yk]:=p;

repeat

r:=<очередная вершина из Chain>;

for <для всех вершин, связанных с r>
do

if <вершина
из XN>

then begin if <ребро
“тонкое”> then

<включить ребро в
цепочку>

end

else begin if <ребро “толстое”> then

<включить ребро в цепочку>

end;

until <просмотрены все вершины из Chain>
or <текущая вершина принадлежит YM, и
она свободна>;

FindChar:=<текущая вершина принадлежит
YM, и она свободна>;

end;

Процесс дальнейшего уточнения логики
вынесем в самостоятельную часть работы.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

Поиск максимального паросочетания

Пусть дан неориентированный граф G = (V, Е). Паросочетанием (matching)
называется подмножество ребер М є Е, такое что для всех вершин v е V в М
содержится не более одного ребра, инцидентного v.

Максимальным паросочетанием называется паросочетание максимальной мощности, т.е. такое паросочетание М, что для любого паросочетания М’: |М| >= |М’|.

Ограничимся рассмотрением задачи поиска максимальных паросочетаний в двудольных графах. Мы предполагаем, что множество вершин можно разбить на два подмножества V = L U R, где L и R не пересекаются, и все
ребра из Е проходят между L и R. Далее мы предполагаем, что каждая вершина из V имеет по крайней мере одно инцидентное ребро.

С помощью метода Форда-Фалкерсона можно найти максимальное паросочетание в неориентированном двудольном графе G = (V,E) за время, полиномиально зависящее от |V| и |Е|. Определим для заданного двудольного графа G соответствующую
транспортную сеть G’ = (V’, Е’) следующим образом. Возьмем в качестве источника s и стока t новые вершины, не входящие в V, и пусть V’ = V U {s, t}. Если
разбиение вершин в графе G задано как V = L U R, ориентированными ребрами G будут ребра Е, направленные из L в R, а также |V| новых ребер. Чтобы завершить построение, присвоим каждому ребру Е’ единичную пропускную способность.

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

Формальное описание     [вверх]

Matching(G)
1. Проверить, является ли граф двудольным.
2. Если граф двудольный, то перейти к пункт 2.1., иначе 
   вывести сообщение о том, что граф недвудольный и завершить работу.
   2.1. Разбить граф на 2 части.
   2.2. Создать 2 вершини, связать стартовую со своеми вершинами 
        из первой части графа, конечную - со всеми вершинами 
        из второй части графа.
   2.3. Модернизировать полученную сеть, изменяя пропускную способность 
        в обратну сторону графа на отрицательные значения.
   2.4. Найти максимальный поток с помощью алгоритма Форда-Фалкерсона.
   2.5. Считать рёбра между двумя частями графа 
        с потоком равным 1 рёбрами паросочитаний.
   2.6. Подсчитать количество рёбер в паросочитании.

Оценка сложности     [вверх]

Поскольку любое паросочетание в двудольном графе имеет мощность не более min(L, R) = О (V), величина максимального потока в G составляет О (V).
Поэтому максимальное паросочетание в двудольном графе можно найти за время O(V*E’) = O(V*E), поскольку |Е’| = o(Е).

Пример     [вверх]

Рассмотрим схему сведения двудольного графа к некоторой сети. На рисунке показан исходный двудольный граф G.

Построим сеть S(G) с источником s и стоком t следующим образом:
* источник s соединим дугами с вершинами из множества X;
* вершины из множества Y соединим дугами со стоком t;
* направление на ребрах исходного графа будет от вершин из X к вершинам из Y;
* пропускная способность всех дуг C[i,j] = 1.
Найдем максимальный поток из s в t для построенной сети. Он существует. Насыщенные дуги потока (они выделены «жирными» линиями на рисунке) соответствуют ребрам наибольшего паросочетания исходного графа. Найденное наибольшее паросочетание не единственное.

Найдём в исходном графе (слева) две доли и запомним их. Таким образом мы получим двудольный граф.

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

Рёбра первоначального графа, через которые поток равен 1, будут рёбрами максимального паросочетания. В данном случае максимальное паросочетание состоит из 2 рёбер: (0;1) и (2;4).

Найдём в исходном графе (слева) две доли и запомним их. Таким образом мы получим двудольный граф.

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

Рёбра первоначального графа, через которые поток равен 1, будут рёбрами максимального паросочетания. В данном случае максимальное паросочетание состоит из 2 рёбер: (0;1) и (2;4).

[вверх]