Задание № 27 · ЕГЭ

Совершенное паросочетание

Паросочетание, в котором каждая вершина графа занята ровно одним ребром

2 мин чтенияСложность: Обновлено 29 сентября 2026

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

Совершенное паросочетаниеСлово «совершенное» означает, что паросочетание покрывает не часть, а все вершины графа.

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

\[|M|=\frac{|V|}{2}\]

Здесь \(V\) — множество вершин графа, а \(M\) — совершенное паросочетание. Из формулы следует важное необходимое условие: число вершин должно быть чётным. Однако чётности недостаточно: нужные рёбра могут отсутствовать.

№

Пример

В графе с вершинами \(A\), \(B\), \(C\), \(D\) выбраны рёбра \(AB\) и \(CD\). Они не имеют общих концов и покрывают все четыре вершины, поэтому образуют совершенное паросочетание. Если выбрать только \(AB\), вершины \(C\) и \(D\) останутся непокрытыми — это обычное паросочетание, но не совершенное.

Не путайте

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

Проверьте себя

В графе 6 вершин выбраны рёбра \(AB\), \(CD\) и \(EF\). Является ли этот набор совершенным паросочетанием?

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

Главное

Совершенное паросочетание покрывает каждую вершину ровно один раз.
При \(|V|\) вершинах оно содержит \(|V|/2\) рёбер, поэтому число вершин должно быть чётным.
Проверка: выбранные рёбра не имеют общих концов и вместе содержат все вершины графа.