Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

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

Читайте также:
  1. II закон термодинамики. Теорема Карно-Клаузиуса
  2. Доказательство. Теорема.
  3. Интегральная теорема Лапласа
  4. Котельников теоремасы бойынша санақ шығарудың жиілігін таңдау
  5. ЛЕКЦИЯ 12. ТЕОРЕМА О ПЛОТНОСТИ СУММЫ ДВУХ СЛУЧАЙНЫХ ВЕЛИЧИН
  6. ЛЕКЦИЯ 18. ЦЕНТРАЛЬНАЯ ПРЕДЕЛЬНАЯ ТЕОРЕМА
  7. ЛЕКЦИЯ 6. ИНТЕГРАЛЬНАЯ ТЕОРЕМА МУАВРА–ЛАПЛАСА, ТЕОРЕМА БЕРНУЛЛИ

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

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

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

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

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

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

Лемма

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

Доказательство. Так как все веса положительные, то множество максимального веса будет базой матроида. Пусть BG = {e1, e2, e3, …, er}, причем выписаны они в том порядке, в каком алгоритм выбирал их. Тогда w(e1) ≥ w(e2) ≥ … ≥ w(er). Рассмотрим базу B = {f1, f2, f3, …, fr}, причем элементы тоже упорядочены по убыванию. Пусть она будет базой максимального веса. Далее будет доказано, что всегда будет выполняться неравенство w(ek) ≥ w(fk).



Будем доказывать от противного. Пусть k + 1 будет наименьшим индексом, для которого это соотношение не будет выполняться — w(ek+1) < w(fk+1). Рассмотрим два множества — Y = {e1, e2, e3, …, ek}, X = {f1, f2, f3, …, fk+1}. По третьему свойству матроидов Y ∪ {fi} ∈ I для какого-то i ∈ {1, 2, …, k + 1}. Но w(fi) ≥ w(fk+1) ≥ w(ek+1). Но алгоритм должен был выбрать fi в предпочтение ek+1. Получили противоречие. Поэтому w(ei) ≥ w(fi). Так как было сделано предположение, что B — маскимального веса, то из этого следует что алгоритм действительно строит независимое множество максимального веса.


Дата добавления: 2015-07-07; просмотров: 175 | Нарушение авторских прав


Читайте в этой же книге: Исторический обзор | Формализация понятия алгоритма | Шаг алгоритма |
<== предыдущая страница | следующая страница ==>
Теорема| Теорема

mybiblioteka.su - 2015-2018 год. (0.013 сек.)