(

x =

1; если x 2 S

0; если x 62S

Кроме того, заменим обозначение дизъюнкции x _ y на сложение x+y, конъюнкции x^y – на умножение xy. Тогда высказывание ((10.1)) “S есть вершинно-реберное покрытие” запишется в виде

Qm [x1I(x1; uj) + x2I(x2; uj) + ¢ ¢ ¢ + xnI(xn; uj)] = 1.

j=1

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

Определение. Множество W µ U попарно несмежных ребер графа G = (X; U; P ) и порожденный им суграф называется паросочетанием.

Паросочетание максимальное, если оно не содержится ни в каком другом паросочетании, и наибольшее, если оно максимальное и содержит наибольшее число ребер среди всех максимальных паросочетаний графа G. Обычно рассматривается задача нахождения наибольшего паросочетания. Число ребер наибольшего паросочетания графа G обозначим через ¼(G).

Примеры 10.6. На графах, изображенных на рисунках, ребра наибольших паросочетаний выделены жирными линиями. Очевидно, что число ребер в паросочетании jW j · bn=2c (bxc – целая часть числа x), так как каждое ребро “покрывает” 2 вершины. Для звездного графа (веера) jW j = 1. J

Теорема 10.2 (Галлаи) Для графа без петель и изолированных вершин

¶(G) + ¼(G) = n(G),

где ¶(G) – число ребер наименьшего реберного покрытия.

До к а з а т е л ь с т в о . Зафиксировав граф G, обозначим

¶= ¶(G); ¼ = ¼(G); n = n(G).

Для доказательства теоремы покажем

1.¶ + ¼ · n,

2.¶ + ¼ ¸ n.

1. Пусть W ? – наибольшее паросочетание. W ? покрывает 2jW ?j вершин графа G, а X0 – множество вершин, не покрытых паросочетанием (не инцидентных ни одному ребру из W ?)

X0 µ X; jX0j = n ¡ 2jW ?j.

Если X0 6= ?, то для каждого x 2 X0 выберем одно ребро, инцидентное x и смежное какому-либо ребру из W ?. Выбранное множество ребер обозначим U0. При этом jX0j = jU0j. Очевидно, что V = U0 [ W ? образует некоторое реберное покрытие.

Если V ? – наименьшее реберное покрытие, то jV ?j · jV j = n ¡ 2jW ?j + jW ?j = n ¡ jW ?j = n ¡ ¼,

откуда

¶ + ¼ · n.

2. Пусть V ? – наименьшее реберное покрытие графа G. Заметим, что суграф, порожденный ребрами V ? имеет k > 1 компонент связности. В каждой из компонент никакие две вершины со степенью больше 1 не могут быть смежны в V ? (так как в противном случае при удалении соединяющего их ребра получим другое реберное покрытие с меньшим числом элементов). Это означает, что каждая компонента представляет собой веер (звездный граф), может быть однореберный. Тогда

¶ = jV ?j = n ¡ k.

Действительно, пусть ni – число вершин в i-й компоненте; каждый веер – дерево и число ребер в нем равно ni ¡ 1;

Pk (ni ¡ 1) = n ¡ k (так как V ? покрывает все вершины).

i=1

Теперь образуем множество W из ребер, выбранных по одному из каждой компоненты V ?. Очевидно, W – паросочетание и jW ?j ¸ jW j = k = n ¡ ¶,

¼ ¸ n ¡ ¶,

откуда ¶ + ¼ ¸ n.

Таким образом, мы доказали оба неравенства и тем самым – утверждение теоремы. £

З а м е ч а н и . Из доказательства теоремы следует, что из наибольшего паросочетания легко получить наименьшее реберное

покрытие, и наоборот. Действительно, пусть найдено наибольшее паросочетание W ?. Чтобы получить наименьшее реберное покрытие V ? нужно к ребрам W ? добавить ребра, покрывающие те вершины, которые не покрываются паросочетанием W ?.

Наоборот, для того чтобы получить наибольшее паросочетание W ? из наименьшего реберного покрытия V ? достаточно выбрать по одному ребру из каждой компоненты V ?. I

Определение. Паросочетание, которое является реберным покрытием, называется совершенным.

Другими словами, реберное покрытие, состоящее из однореберных компонент, есть совершенное паросочетание.

10.3.0.5 Чередующиеся цепи

Пусть W – паросочетание в обыкновенном графе G = (X; U) .

Ребра паросочетания и инцидентные им вершины назовем сильными, а остальные ребра и вершины – слабыми

(темные и светлые, жирные и тонкие, синие и красные и т.д.)

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

Определение. Чередующаяся цепь, соединяющая две различные вершины, называется увеличивающей цепью (W -увеличитель, аугментальная цепь).

Это название происходит из того факта, что если в графе G есть увеличивающая цепь, то можно построить паросочетание с большим´ числом ребер, чем в W .

В самом деле, в такой цепи число слабых ребер на единицу больше, чем число сильных. Заменив слабые ребра на сильные, то есть исключив из W сильные ребра и включив в W слабые ребра увеличивающей цепи, получим новое паросочетание W 0 с числом ребер на единицу больше:

jW 0j = jW j + 1

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

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

W 0 = (W n W \ P ) [ (P n W \ P ) = (W [ P ) n W \ P

является паросочетанием, полученным в результате замены ребер из P \W (входящих в W ) на ребра из P nW \P (не входящих в W ). Так как конечные вершины цепи слабые, то есть конечные ребра из P не входят в W , то число ребер в P n W \ P на единицу больше чем в W \ P . Отсюда jW 0j = jW j + 1, то есть паросочетание не было наибольшим.

°( (от противного). Пусть W – паросочетание, относительно которого нет увеличивающей цепи. Предположим, что W не наибольшее и существует W ¤ – наибольшее паросочетание. Построим суграф GW на множестве ребер

W [ W ¤ n W \ W ¤

Никакая вершина в GW не может иметь степень большую´ чем 2. В противном случае два или более ребер из W или из W ¤ будут смежными, что противоречит определению паросочетания.

Таким образом, суграф GW состоит из одной или более компонент, каждая из которых либо пустая, либо есть простая цепь, либо простой цикл, как это изображено на рисунке. Цепи типа 2 и 3 в GW существовать не могут, так как являются увеличивающими относительно W ¤ и W сответственно. Цикл типа 5 с нечетным числом ребер не может существовать в GW , так как тогда либо два ребра из W , либо два ребра из W ¤ были бы смежными, что противоречит определению паросочетания.

Остаются возможными компоненты суграфа GW типа 1 (пустые), типа 4 и циклы типа 5 с четным числом ребер. Для каждого из таких суграфов число ребер из W ¤ равно числу ребер из W . Следовательно, jW j = jW ¤j, то есть W – наибольшее паросочетание. £

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

Начиная с некоторого произвольного паросочетания W строить последовательность паросочетаний W1; W2; : : :, всякий раз отыскивая увеличивающую чередующуюся цепь и увеличивая паросочетание.