Теорема. Пусть A — какое-то множество подмножеств E, а I — множество частичных трансверсалей

Пусть A — какое-то множество подмножеств E, а I — множество частичных трансверсалей множества A. Тогда пара E, I — матроид.

Доказательство. Каждое подмножество частичного трансверсаля — частичный трансверсаль. Пустое множество также частичный трансверсаль. Поэтому первые два свойства матроидов выполняются. Для доказательства третьего свойства матроидов построим двудольный граф. Он, а также максимальное паросочетание в нем изображены на рисунке. Пусть вершины слева будут соответствовать элементам множества E, а вершины справа — элементам множества A. Ребро из левой доли в правую есть тогда и только тогда, когда соответствующий элемент левой доли принадлежит сответствующему элементу правой доли. Частичный трансверсаль соответствует паросочетанию в графе. Пусть X и Y будут частичными трансверсалями и |X| = |Y| + 1. Раскрасим ребра из паросочетания, соответствующего X в синий цвет, а соответствующего Y — в красный. Причем ребра, соответствующие двум паросочетаниям, будут окрашены в пурпурный цвет. Таким образом, получится |X − Y| ребер синего цвета, |Y − X| ребер красного цвета, и будет выполняться соотношение |X − Y| = |Y − X| + 1. Рассмотрим подграф H, индуцированный красными и синими ребрами из исходного графа. Каждая вершина соответствует либо двум ребрам — синему и красному, либо одному — синему или красному. Понятно, что любая компонента связности представляет собой либо путь, либо цикл, состоящий из чередующихся красных и синих ребер. Так как граф двудольный, любой цикл состоит из четного числа ребер. Так как синих ребер на одно больше, чем красных, то должен существовать путь, начинающийся и оканчивающийся синим ребром. Обозначим этот путь H′. Поменяем в H′ синий и красный цвета. Получаем, что ребра, окрашенные в красный и пурпурный цвета образуют паросочетание в графе. Дальше легко показать, что подмножество E соответствующее этому новому паросочетанию имеет вид Y ∪ {x}, где x — это некоторый элемент из X − Y.

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

Жадный алгоритм

Взвешенный матроид — матроид, на элементах множества E задана положительная весовая функция w.

А теперь сам алгоритм: B_G = Ø. Пока существует e ∉ B_G, такой что B_G ∪ {e} ∈ I и w(e) — максимально, B_G:= B_G ∪ {e}.

Лемма

Жадный алгоритм стоит независимое множество максимального веса.

Доказательство. Так как все веса положительные, то множество максимального веса будет базой матроида. Пусть B_G = {e₁, e₂, e₃, …, e_r}, причем выписаны они в том порядке, в каком алгоритм выбирал их. Тогда w(e₁) ≥ w(e₂) ≥ … ≥ w(e_r). Рассмотрим базу B = {f₁, f₂, f₃, …, f_r}, причем элементы тоже упорядочены по убыванию. Пусть она будет базой максимального веса. Далее будет доказано, что всегда будет выполняться неравенство w(e_k) ≥ w(f_k).

Будем доказывать от противного. Пусть k + 1 будет наименьшим индексом, для которого это соотношение не будет выполняться — w(e_k+1) < w(f_k+1). Рассмотрим два множества — Y = {e₁, e₂, e₃, …, e_k}, X = {f₁, f₂, f₃, …, f_k+1}. По третьему свойству матроидов Y ∪ {f_i} ∈ I для какого-то i ∈ {1, 2, …, k + 1}. Но w(f_i) ≥ w(f_k+1) ≥ w(e_k+1). Но алгоритм должен был выбрать f_i в предпочтение e_k+1. Получили противоречие. Поэтому w(e_i) ≥ w(f_i). Так как было сделано предположение, что B — маскимального веса, то из этого следует что алгоритм действительно строит независимое множество максимального веса.

Дата добавления: 2015-07-07