Тапсырма № 27 · ЕГЭ

Паросочетание

Набор рёбер графа без общих вершин

2 мин чтенияҚиындық: Обновлено 29 қыркүйек 2026

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

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

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

Как описывают паросочетание

Если в паросочетании \(k\) рёбер, то оно покрывает \(2k\) вершин. Одну вершину нельзя использовать сразу в двух выбранных рёбрах. Поэтому поиск паросочетания часто означает распределение объектов по парам: каждый объект может участвовать не более чем в одной паре.

\[M \subseteq E, \qquad \forall e_1,e_2\in M\ (e_1\ne e_2 \Rightarrow e_1\cap e_2=\varnothing)\]

Здесь \(E\) — множество всех рёбер графа, а \(M\) — выбранное паросочетание. Если удаётся покрыть все вершины, получается совершенное паросочетание. В двудольном графе рёбра соединяют вершины из разных долей, поэтому паросочетание можно рассматривать как набор допустимых пар «объект — назначение».

№

Пример

Пусть рёбра графа: \(AB\), \(AC\), \(BD\), \(CE\). Набор \(\{AB, CE\}\) является паросочетанием: рёбра используют вершины \(A,B,C,E\), и общих вершин у них нет. Набор \(\{AB, AC\}\) паросочетанием не является, потому что оба ребра содержат вершину \(A\).

Не путайте

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

Проверь себя

Какой набор рёбер является паросочетанием?

Главное за минуту

Главное

Паросочетание — набор рёбер без общих вершин.
Паросочетание из \(k\) рёбер покрывает \(2k\) вершин; совершенное паросочетание покрывает все вершины графа.
В задачах распределения паросочетание задаёт пары, в которых каждый объект участвует не более одного раза.