9.2. Реберные покрытия

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

Реберное покрытие Р графа G минимально, если он не имеет такого реберного покрытия Р, что Число ребер в минимальном реберном покрытии графа G называется числом реберного покрытия этого графа и обозначается через Например, в графе на рис. 9.1 множество образует минимальное реберное покрытие.

Напомним, что числа вершинного и реберного покрытий обозначаются через соответственно; аналогично числа независимости и паросочетания обозначаются через и а соответственно.

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

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

В следующей теореме, являющейся реберным аналогом следствия 9.1.1, мы связываем величины и Этот результат получен Галлаи [9.3].

Теорема 9.4. Для простого графа G на вершинах без изолированных вершин

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

. Таким образом, .

    (9-3)

Пусть теперь P имеет связных компонент, т. е. . Выберем по одному ребру из каждой компоненты Р. Пусть М будет множеством из выбранных ребер. Очевидно, что М является паросочетанием и поэтому Таким образом,

Объединяя выражения (9.3) и (9.4), получаем

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

Таким образом,

В общем случае равенство в выражении (9.5) не имеет места. Однако, когда граф G двудольный, это равенство мы докажем в следующей теореме, аналогичной теореме 9.2.

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

Доказательство. Пусть граф G имеет вершин. Тогда, согласно следствию , а по теореме 9.4 . Но по теореме Поэтому получаем

Теоремы 9.2 и 9.5 являются эквивалентными формулировками теоремы Холла (упражнения 9.5 и 9.6).