Первая страница / Теория / Разное /

Матроиды

Голосование: 23, 9

Введение

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

Договоренности

Для разговора следует сначала определиться по поводу терминов, используемых в этой статье. Циклом в графе будем называть замкнутый путь в графе, каждое из ребер графа встречается в нем не более одного раза. Простым циклом будем называть такой цикл, что при удалении из него ребра он перестает быть циклом. Все рассматриваемые графы неориентированные. Графовый матроид графа G будем обозначать M(G). Векторный матроид матрицы A будем обозначать M[A].

Что есть матроид?

Рассмотрим следующую матрицу.

1001000
0101110
0010110

Определим множество E, как множество состоящее из {1, 2, 3, 4, 5, 6, 7} — номеров столбцов матрицы, а множество I, как множество состоящее из подмножеств E, таких, что векторы, определяемые ими, являются линейно независимыми над полем вещественных чисел R. Зададимся вопросом — какими свойствами обладает построенное множество I?

  1. Множество I непусто. Даже если исходное множество E было пусто — E = Ø, то I будет состоять из одного элемента — множества, содержащего пустое. I = {{Ø}}.
  2. Любое подмножество любого элемента множества I также будет элементом этого множества. Это свойство понятно — если некоторый набор векторов линейно независим над полем, то линейно независимым будет также любой его поднабор.
  3. Также у множества I есть еще одно важное и весьма нетривиальное свойство. Если X, YI, причем |X| = |Y| + 1, тогда существует элемент xXY, такой что Y ∪ {x} ∈ I. На данный момент оно может показаться несколько странным и неочевидным. Немного позже картина прояснится.

Перейдем к определению самого понятия матроида. Матроидом называется пара множеств E, I, состоящая из конечного множества E, называемого базовым множеством матроида, и множества его подмножеств I, называемого множеством независимых множеств матроида, причем I удовлетворяет трем указанным выше свойствам. Стоит отметить, что свойство №2 еще называют свойством наследственности.

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

Доказательство. Пусть X, YI и |X| = |Y| + 1. Пусть W будет пространством векторов, охватываемым XY . Понятно, что его размерность будет не менее |X|. Предположим, что Y ∪ {x} будет линейно зависимо для всех xXY (то есть третье свойство не будет выполняться). Тогда Y образует базис в пространстве W. Из этого следует, что |X| ≤ dim W ≤ |Y|. Но так как по условию X и Y состоят из линейно независимых векторов и |X| > |Y|, получаем противоречие. Такое множество векторов будет являться матроидом. Его иногда называют векторным матроидом.

Графовый матроид

Рассмотрим граф на рисунке.

Граф

Граф неориентированный и состоит из четырех вершин и семи ребер, одно из которых является петлей. Пусть E будет множеством, состоящих из ребер этого графа, E= {1, 2, 3, 4, 5, 6, 7}, а I будет множеством подмножеств E, таких что каждый элемент I не содержит в себе циклов графа. Эта пара множеств E, I является матроидом, ее называют графовым матроидом и обозначают M(G).

Теорема

Пусть G — граф, а AG — его матрица инциденций. Если рассматривать AG как матрицу над полем {0, 1}, где все операции выполняются по модулю 2, то тогда векторный матроид, построенный на AG, в качестве независимых множеств будет содержать множества ребер, не содержащих в себе циклов, и M(G) = M[AG].

Доказательство. Необходимо доказать, что XAG линейно зависим тогда и только тогда, когда X содержит цикл. Предположим, что X содержит в себе цикл C. Если C — это петля, то тогда в X будет содержаться нулевой вектор и он будет линейно зависимым. Если же C не петля, то каждая вершина в этом цикле будет соответствовать двум ребрам C и сумма векторов по модулю 2 будет нулевым вектором. Из-за чего X будет линейно зависимым.

Теперь предположим, что X линейно зависимый. Возьмем минимальное линейно зависимое подмножество D из X (то есть такое подмножество, что удаление из него любого элемента приводит к тому, что оно будет линейно независимым). Если D будет состоять из нулевого вектора, то тогда X содержит петлю и, соответственно, цикл.

Если D не содержит нулевого вектора: так как в поле {0, 1} существует единственный ненулевой элемент — 1, то сумма векторов из D будет нулевым вектором, из-за того, что D — минимальное линейно зависимое подмножество. Из этого следует, что D содержит ребра из цикла, и если какой-то вершине инцидентно ребро из D, то существует как минимум еще одно ребро, инцидентное ей. Действительно, возьмем ребро d1 и пусть вершины v0 и v1 соответствуют этому ребру. Пусть вершине v1 инцидентно еще какое-то ребро d2. Пусть вершина v2 будет другим концом ребра d2. Продолжим этот процесс. В результате будут получены две последовательности — v0, v1, … и d1, d2, …. Так как количество вершин в D конечно, то какая-то из вершин v должна повториться. Когда это произойдет, то в D будет найден цикл. Соответственно цикл будет найден и в X.

Базы и простые циклы

Для того, чтобы перейти к решению различных задач непосредственно при помощи матроидов, следует рассмотреть еще два важных понятия из этой теории. База матроида — это максимальное независимое множество матроида (множество из I максимальной мощности).

Простой цикл матроида — это минимальное зависимое множество матроида.

Зададим два множества — множество, состоящее из всех возможных баз матроида M, обозначим его BM, и множество, состоящее из всех возможных простых циклов матроида M, обозначим его CM. Так как матроиды обладают свойством наследственности, любое из этих двух множеств может полностью определить матроид.

Теорема

Множество B является множеством баз матроида M тогда и только тогда, когда выполняются следующие два свойства:

  1. Множество B непусто.
  2. Если B1, B2В, xB1B2, тогда существует yB2B1, такой, что (B1x) ∪ {y} ∈ B.

Доказательство. Пусть выполняются два приведенных свойства. Необходимо доказать, что B содержит все базы. Опять проведем доказательство от противного. Пусть B1B. Но есть элемент l, такой что B1 ∪ {l} ∈ B, l = B1B. Но тогда такого элемента YB − (B ∪ {l}) не существует.

Пусть B — множество баз, докажем что имеют место оба свойства. Первое свойство — очевидно. Рассмотрим второе свойство. xB1B2. Но не существует такого yB2B1, что B1x ∪ {y} ∈ B. Но это противоречит третьему свойству матроидов, так как |B1 − {x}| + 1 = |B2|, и такой y должен существовать.

Cледствие

Мощность любой базы является одинаковой (по 2 свойству). Рангом матроида называется мощность его базы.

Теорема

Множество C является множеством простых циклов матроида тогда и только тогда, когда выполняются следующие три свойства:

  1. Ни один из элементов C не является пустым множеством.
  2. Ни один элемент C не является подмножеством другого элемента C.
  3. Если C1 и C2C и eC1C2, то (C1C2) − e содержат какой-то элемент C.

Доказательство. Аналогично уже приведенным двум доказательствам. Читателю предлагается проделать его самостоятельно.

Матроиды и комбинаторная оптимизация

Матроиды имеют широкое применение в задачах, связанных с комбинаторной оптимизацией, а также с задачами, решение которых основано на жадных алгоритмах.

Рассмотрим такую задачу: у менеджера есть m однодневных работ для одного человека J1, J2, J3, …, Jm. Также он располагает n рабочими, каждый из которых умеет выполнять какой-то поднабор работ. Менеджер хочет знать, какое максимальное количество работ способны выполнить его рабочие за один день. Как позже выяснится, это будет рангом некоего матроида.

Трансверсаль

Пусть A — множество подмножеств некоего множества E. К примеру, пусть A=({1,2,4}, {2,3,5,6}, {5,6}, {7}), при множестве E={1, 2, 3, 4, 5, 6, 7}. Подмножество E — {x1, x2, …, xk} называется частичным трансверсалем A, если есть взаимооднозначное соответствие Φ между {1, 2, …, k} и {1, 2, …, m}, причем xiAΦ(i) для любых i. Если m = k, то такой частичный трансверсаль называется трансверсалем. Если взять множество {2,3,6,7}, то оно будет трансверсалем для A, как это видно из рисунка слева.

Теорема

Пусть 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 — максимального веса, то из этого следует что алгоритм действительно строит независимое множество максимального веса.

Алгоритм Краскала

Для начала вкратце напомним алгоритм Краскала. Подробнее про него, к примеру, можно почитать в книге Кормена Введение в алгоритмы.

В начале работы алгоритма Краскала есть |V| независимых компонент, каждая из которых состоит из одной вершины. Далее на каждом шаге выбирается ребро наименьшего веса, соединяющее две компоненты, добавляется в уже построенное множество ребер минимального остовного дерева, эти две компоненты объединяются в одну. Когда осталась одна компонента — минимальное остовное дерево построено.

Раньше был рассмотрен графовый матроид и был доказан факт того, что он действительно является матроидом. Очевидно, что базам этого матроида будут соответствовать остовные деревья в G. Каким образом можно использовать только что изученный жадный алгоритм для построения минимального остовного дерева? Пусть G — граф. На его ребрах задана весовая функция w ≥ 0. Введем новую весовую функцию w* = M - w + 1, где M — наибольший вес ребра в графе G. Понятно, что задача минимизации веса остовного дерева сводится к находжению независимого множества максимального веса с весовой функцией w*. Это можно сделать при помощи жадного алгоритма, чем собственно алгоритм Краскала и занимается. В данной статье не рассматриваются аспекты реализации этого алгоритма.

Алгоритм удлиняющихся цепей

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

Теорема

Пусть I — множество подножеств множества E. Тогда E,I является матроидом тогда и только тогда, когда выполняются первые два свойства матроидов, и по любой неотрицательной весовой функции w на E, жадный алгоритм строит независимое множество максимального веса. Доказательство этого факта приводить не будем. Его можно найти в статье James Oxley, What is a matroid?. Отметим лишь, что этот факт показывает, что матроиды являются единственными иерархическими структурами, для которых применим жадный алгоритм.

Список литературы

  1. Oxley J. What is a matroid
  2. Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. — Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001.

Борис Ярцев


Игорь / 2013-09-07 20:06:23

хорошая сжатая статья

напишите также популярно о проблемах Гильберта

Взгляните на название сайта. Причем тут проблемы Гильберта?

Борис / 2016-04-18 15:03:39

Прошу прощения, что не по теме. Есть вопрос: существуют ли такие функции, приращение аргумента которых может быть только положительным?

Существует ли такая конструкция, чтобы, скажем, вектор удлинялся в одну сторону и одновременно отсекался в противоположную?

Возможен ли такой... непрерывный, что ли, алгоритм?

Да уж, не по теме. Отвечаем аналогично, но по существу. Пример с приращениями только в одну сторону и непрерывностью очевиден: вектор времени из настоящего в будущее, плюс сдвигающаяся только вправо точка отсчета (текущий момент).

Нечто подобное работает при упаковке текста в алгоритме со скользящим (ВПРАВО!) окном фиксированного размера. Устаревший левый символ исключается, очередной справа добавляется, текущий словарь-дерево модифицируется; окно сдвигается.

Ваше имя
Email
Текущий день недели (строчными буквами)
Комментарий