Главная > Методы обработки данных > Графы, сети и алгоритмы
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

8.7. Паросочетания графов общего вида

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

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

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

1. Цикл четной длины, ребра которого входят поочередно в

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

Доказательство. Рассмотрим произвольную вершину

Случай где означает множество вершин, инцидентных ребрам . В этом случае v — концевая вершина ребра в

Рис. 8.9.

Рис. 8.10.

Поскольку — паросочетание, никакое другое ребро из не инцидентно вершине v. Более того, никакое ребро из не инцидентно вершине v, поскольку -Следовательно, в этом случаа степень вершины s в G равна 1.

Случай . В этом случае вершине v инцидентны одно ребро и одно ребро . Следовательно, степень вершины v равна 2.

Поскольку рассмотренные случаи исчерпывают возможные варианты, можно сделать вывод, что максимальная степень в подграфе G равна 2. Поэтому связная компонента может принадлежать только к одному из описанных типов.

Например, рассмотрим два паросочетания графа G на рис. 8.9. Тогда а граф G будет таким, как показано на рис. 8.10. Граф G содержит компоненты двух типов, описанных в теореме 8.19.

В следующей теореме мы формулируем характеризацию Бержа [8.21] максимальных паросочетаний в терминах чередующихся цепей.

Теорема 8.20 (Берж). Паросочетание М максимально тогда и только тогда, когда между любыми двумя не насыщенными в нем вершинами не существует чередующейся цепи.

Доказательство.

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

Можно рассмотреть, например, паросочетание в графе на рис. 8.9. Между ненасыщенными вершинами имеется чередующаяся цепь Если заменить в М темные ребра на светлые получим паросочетание содержащее на одно ребро больше, чем М.

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

Так как то очевидно, что тогда и только тогда, когда

Пусть G — граф на множестве ребер

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

Теперь рассмотрим произвольную компоненту графа G, являющуюся путем. Снова по теореме 8.19 ребра в нем входят поочередно в Кроме того, концевые вершины такого пути не насыщены в М или М. Предположим, что путь имеет нечетную длину, тогда концевые вершины пути инцидентны ребрам, находящимся в одном паросочетании. Это означает, что по отношению к одному из паросочетаний существует чередующаяся цепь, соединяющая ненасыщенные вершины. Но это противоречит тому, что и М, и М удовлетворяют условиям теоремы. Поэтому каждая компонента графа G, являющаяся путем, содержит четное число ребер и, следовательно, одинаковое число ребер из

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

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

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

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

сочетание в графе G, которое насыщает все вершины X степени . Аналогично существует паросочетание в графе G, которое насыщает все вершины Y степени А. Сейчас возникает вопрос: существует ли паросочетание двудольного графа, которое насыщает все вершины максимальной степени как X, так и К? Для ответа на этот вопрос нам необходим следующий результат, полученный Мендельсоном и Далмеджем [8.22].

Теорема 8.21. (Мендельсон и Далмедж). Пусть -двудольный граф, a -паросочетание, которое «сочетает» Тогда существует паросочетанне которое насыщает .

Доказательство. Рассмотрим двудольный граф Любая вершина этого графа имеет степень 1 или 2, следовательно, любая его компонента является путем или циклом, ребра которых входят поочередно в Мхи (См. доказательство теоремы 8.19.)

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

Если мы положим то легко видеть, что является паросочетанием, насыщающим Это и есть требуемое паросочетание

Теорема 8.22. В двудольном графе имеется паросочетание, насыщающее все вершины максимальной степени.

Доказательство. Рассмотрим двудольный граф . Пусть ХХ и содержат все вершины графа G максимальной степени. Как мы видели ранее, существует паросочетание насыщающее все вершины X, и паросочетание насыщающее все вершины К. По теореме 8.21 существует паросочетание МЯМХ насыщающее все вершины и К, являющееся поэтому требуемым паросочетанием, которое насыщает все вершины графа G максимальной степени.

Следствие 8.22.1. Множество ребер двудольного графа с максимальной степенью Д можно разбить на Д паросочетаний.

Доказательство. Рассмотрим двудольный граф с максимальной степенью Д. По теореме 8.22 существует паросочетание насыщающее все вершины степени Д. Тогда двудольный имеет максимальную степень Этот граф имеет паросочетание насыщающее каждую вершину степени Повторяя этот процесс, мы построим последовательность непустых паросочетаний УИД, которые образуют разбиение Е.

Применение теорем 8.21, 8.22 и следствия 8.22.1 рассматривается в разд. 15.6.

Вернемся к изучению паросочетаний в графах общего вида.

Паросочетание, насыщающее все вершины графа G, называется совершенным паросочетанием этого графа

Мы заканчиваем этот раздел теоремой Татта [8.23], дающей условия существования совершенного паросочетания графа. Используемое нами доказательство предложил Андерсон [8.24].

Компонента графа называется нечетной, если она содержит нечетное число вершин, и в противном случае — четной. Если

подмножество вершин графа G, то через будем обозначать число нечетных компонент графа

Теорема 8.23. (Татт). Граф имеет совершенное паросочетание тогда и только тогда, когда

Доказательство. Необходимость. Допустим, что граф G имеет совершенное паросочетание М. Пусть будут нечетными компонентами графа для некоторого Так как каждая компонента - нечетная, некоторая вершина - в ней должна паросочетаться в М с некоторой вершиной . Таким образом, S имеет не менее k вершин, и, следовательно,

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

Доказательство достаточности проведем индукцией по где . Используем теорему Холла (8.13) и тот простой факт, что

Случай — тривиален. Допустим, что результат верен для любых графов, имеющих менее 21 вершин. Рассмотрим теперь граф G на 21 вершинах, удовлетворяющий условию (8.19). Здесь мы имеем два случая.

Случай 1. Допустим, что для любого Рассмотрим любое ребро графа . Пусть Пусть обозначает число нечетных компонент в графе для любого подмножества Т вершин Тогда если бы то мы получим что противоречит условию (8.19). Поэтому по индукции графы G, а следовательно, и G имеют совершенное паросочетание.

Случай 2. Пусть существует такое множество , что Допустим, что — такое максимальное множество. Заметим сначала, что в графе нет четных компонент. Если бы в нем была четная компонента, мы могли бы удалить из нее вершину и добавить ее к . Это привело бы к увеличению по крайней мере на 1 числа четных компонент. Поэтому Условие (8.19) требует, чтобы Поэтому Но это противоречит максимальности 5. Следовательно, четных компонент в графе нет.

Пусть нечетных компонент графа Покажем теперь, что мы можем взять по вершине из каждой этой компоненты и паросочетать их с вершинами . Если бы это было невозможно, тогда по теореме Холла существовало бы k нечетных компонент, которые связывались в графе G только с вершинами S. Но если Т — такое множество из h вершин, то мы получаем что противоречит условию (8.19). Таким образом, из каждой компоненты мы можем взять вершину - и паросочетать ее с вершиной .

Следовательно, каждый подграф имеет четное число вершин. Если мы покажем, что каждый G; имеет совершенное паросочетание, доказательство будет завершено.

Если содержит такое множество вершин R, что где — число нечетных компонент в то по поэтому

Но условие (8.19) требует, чтобы Поэтому что противоречит условию максимальности . Таким образом, по индукции имеет совершенное паросочетание.

Другое доказательство с использованием теоремы 8.20 дал Ловац [8.25].

<< Предыдущий параграф Следующий параграф >>
Оглавление