8.5. Паросочетания

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

Имеется конечное множество юношей, у каждого из которых есть несколько подруг. При каких условиях можно поженить юношей так, чтобы каждый женился на одной из своих подруг? (Разумеется, никакая девушка не выходит замуж более чем за одного юношу!)

Эта задача ставится в теоретико-графовых терминах следующим образом:

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

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

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

Два ребра называются независимыми, если они не имеют общей вершины. Говорят, что ребра независимы, если каждая их пара не имеет общей вершины.

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

Рис. 8.7.

Рис. 8.8.

Очевидно, максимальное по включению паросочетание — это максимальное по включению множество независимых ребер. Так, в графе на рис. 8.8 максимальным по включению паросочетанием является в то время как таковым не является.

Паросочетание с наибольшим числом ребер называется максимальным паросочетанием. Множество — это максимальное паросочетание в графе на рис. 8.8. Число ребер в максимальном паросочетании графа G будет называться числом паросочетания графа G и обозначаться через

Вершина называется насыщенной в паросочетании М, если она концевая вершина ребра М. Например, вершина v паросочетания в графе на рис. 8.8 насыщенна.

Далее двудольный граф с разбиением (X, Y) будем обозначать тройкой (X, Y, Е).

Будем говорить, что множество X паросочетается с Y в двудольном графе (X, Y, Е), если существует такое паросочетание М,

что каждая вершина X насыщена в М. Паросочетание М в этом случае называется полным паросочетанием .

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