2.2. Цветки

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

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

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

Цветущее дерево — это альтернирующее дерево относительно данного паросочетания, для которого существует ребро соединяющее две внешние вершины дерева:

Рис. 12.7. Дерево с цветком.

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

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

Пример сложной формации цветков и их срезание показаны на рис. 12.8а графе на рис. 12.8а паросочетание

Рис. 12.8а. Срезание цветка Ребра в альтернирующем дереве, входящие в паросочетание. Ребра в альтернирующем дереве, не входящие в паросочетание Другие ребра графа.

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

Рис. 12.86. Срезание

штрих-пунктирной замкнутой линией, после срезания дает псевдовершину как это показано на рис. 12.86. Дерево на рис. 12.86 все еще является цветущим с цветком так как существует ребро После срезания цветка «остается» вершина и получается новый граф, изображенный на рис. Дерево на рис. 12.8в опять будет цветущим ввиду существования ребра цветком в нем будет После срезания цветка «остается» вершина и граф, изображенный на рис. 12.8г.

Рис. 12.8в. Срезание

Рис. 12.8г. Альтернирующее дерево после срезания цветков.

Больше цветков нет, и, значит, будет крайним цветком.

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

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

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

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

Важность цветков и циклов (цепей) с нечетным числом ребер в задачах о паросочетаниях можно оценить, анализируя следующий факт: при отсутствии таких циклов формулировка ЗМП на языке линейного программирования, даваемая соотношениями (12.2) и (12.3), приводит к собственно целочисленному решению, так что ограничения (12.4) становятся излишними [8, 16, 17]. Графы, не содержащие циклов с нечетным числом ребер, являются двудольными графами; они рассматриваются в последующих параграфах. Общие свойства полиэдров, определяемых соотношениями (12.3), содержатся в следующей теореме Балински [1].

Теорема 3. Все вершины, выпуклого полиэдра, задаваемого неравенствами

где матрица инциденций графа, имеют координаты со значениями 0, 1/2 или 1.

Случай нецелочисленных значений (а именно значения 1/2) отвечает циклам с нечетным числом ребер.

Рис. 12.9.

Если, например, граф состоит из единственного такого цикла, как показано на рис. 12.9, то решение задачи линейного программирования (12.2) и (12.3)

для ЗНП таково: для Значение этого решения будет 2 у, в то время как очевидно, что наибольшее паросочетание для графа на рис. 12.9 содержит два ребра.