2. Наибольшие паросочетания

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

2.1. Альтернирующие цепи и деревья

Альтернирующая относительно цепь — это простая цепь, ребра которой попеременно лежат или не лежат в паросочетании Примером такой цепи является цепь в графе на рис. 12.3. Аугменталъная относительно цепь — это такая альтернирующая цепь, начальная и конечная вершины

которой экспонированы. Цепь дает пример аугментальной цепи в графе, изображенном на рис. 12.3.

Рис. 12.3. Паросочетание

Основная относящаяся к паросочетаниям теорема может быть сформулирована так.

Теорема Паросочетание будет наибольшим паросочетанием тогда и только тогда, когда в не существует никакой аугментальной относительно цепи.

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

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

степень, большую чем 2, так как в противном случае два или более ребер из (или являются смежными, что противоречит определению паросочетания. Таким образом, подграф состоит из одной или более компонент, и каждая из них есть либо изолированная вершина, либо простая цепь, либо простой цикл, как это изображено на рис. 12.4.

Цепь типа (б) существовать не может, так как она является аугментальной цепью относительно это противоречит первоначальному предположению.

Рис. 12.4. (см. скан)

Цепь типа (в) не может существовать, так как она является аугментальной относительно что противоречит предположению о максимальности Цикл типа с нечетным числом ребер не может существовать, так как тогда либо два ребра из либо два ребра из были бы смежными друг с другом. Остаются возможными графы следующих видов: (а), (г) и циклы типа с четным числом ребер. Для каждого из таких графов число ребер в равно числу ребер в Так как это справедливо для любой связной компоненты к

графа то

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

следовательно, наибольшее паросочетание.

Рассмотрим в качестве примера граф, изображенный на рис. 12.3. Ребра, образующие паросочетание в этом графе, выделены жирными линиями.

Рис. 12.5. Наибольшее паросочетание

Множество ребер в аугментальной цепи не лежащих в дает новое паросочетание изображенное на рис. 12.5. Здесь уже нет экспонированных вершин и поэтому не существует никаких аугментальных относительно цепей. Следовательно, по теореме наибольшее паросочетание.

Альтернирующим деревом относительно данного паросочетания называется дерево для которого

(а) одна вершина, называемая корнем дерева является экспон ированной;

(б) все начинающиеся в корне цепи являются альтернирующими;

(в) все максимальные цепи, начинающиеся в корне дерева содержат четное число рёбер.

Разобъем все вершины дерева на два класса: класс внешних вершин, I — класс внутренних вершин. Корень дерева

отнесен к классу Вершины вдоль любой цепи, начинающейся в корне, будут поочередно отнесены к классам Таким образом, если вершина расположена в «конце» цепи с нечетным числом ребер, начинающейся в корне, то эта вершина будет отнесена к I, а если она лежит в «конце» цепи с четным числом ребер, начинающейся в корне, то будет отнесена к На рис. 12.6 изображено альтернирующее дерево. Здесь все вершины, лежащие в конце максимальных цепей, начинающихся с корня, в соответствии с условием (в) будут «внешними».

Рис. 12.6. Альтернирующее дерево. I — внутренние вершины, Ф - внешние вершины.

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

Аугменталъное дерево — это альтернирующее дерево относительно данного паросочетания, удовлетворяющее условию: существует ребро от какой-нибудь внешней вершины дерева до некоторой экспонированной вершины не принадлежащей дереву. Единственная цепь, идущая от корня дерева до вершины и далее — по ребру будет тогда аугментальной цепью.