§4. Связь транзитивных отношений зависимости с операторами замыкания

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

Определение 13.

Множество E подмножеств множества A называется системой замыканий, если E и система E замкнута относительно пересечений, т. е. ?D E для любой непустого подмножества D E

Определение 14.

Оператором замыкания на множестве A называется отображение J множества B (A) в себя, обладающее следующими свойствами:

J. 1. Если , то J(X)J(Y);

J. 2. XJ(X);

J. 3. JJ(X) = J(X), для всех X, Y B (A).

Определение 15.

Оператор замыкания J на множестве A называется алгебраическим, если для любых и влечет для некоторого конечного подмножества множества .

Определение 16.

Система замыканий называется алгебраической, если только соответствующий оператор замыкания является алгебраическим

Следует отметить теорему о взаимосвязи между системами замыканий и операторами замыканий.

Теорема 5.

Каждая система замыканий E на множестве определяет оператор замыкания J на по правилу J(X) = ?{Y E | YX}. Обратно, каждый оператор замыкания J на определяет систему замыканий E J.

Следующая теорема показывает связь транзитивного отношения зависимости и алгебраического оператора замыкания.

Теорема 6.

Для любого транзитивного отношения зависимости Z отображение является алгебраическим оператором замыкания на А со свойством замещения.

Обратно, любой алгебраический оператор замыкания на А со свойством замещения получается таким способом из некоторого транзитивного отношения зависимости Z на А.

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

I. Будем называть подмножество Т множества A замкнутым, если .

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

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

Этим доказано, что замкнутые подмножества образуют алгебраическую систему замыканий.

Выполнение свойства замещения следует из соответствующего свойства пространств зависимости.

II. Обратно, пусть - алгебраический оператор замыкания со свойством замещения.

Будем считать зависимым, если для некоторого , и независимым в противном случае.

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

Теперь для любых , имеем тогда и только тогда, когда для некоторого конечного подмножества множества . Выбирая минимальным, можем предполагать, что независимо. Отсюда вытекает, что и, следовательно, .

Обратно, если , то снова для некоторого конечного независимого подмножества множества . Это означает, что зависимо, т.е. для некоторого .

В силу свойства замещения получаем, что и , поэтому .

Замечание. Существуют алгебраические операторы замыкания, не обладающие свойством замещения. Для примера возьмем бесконечную циклическую полугруппу .

Пусть и . Тогда , , но .

§5. Матроиды

Понятие матроида тесно связано с понятием отношения зависимости, поэтому эта тема рассматривается в данной квалификационной работе. Однако с другой стороны оно является теоретической основой для изучения и анализа «жадных» алгоритмов.

Определение 17.

Матроидом называется конечное множество и семейство его подмножеств , такое что выполняется три аксиомы:

М₁: ;

М₂: ;

М₃:

Определение 18.

Элементы множества называются независимыми, а остальные подмножества - зависимыми множествами.

В соответствии с введенными ранее аксиомами пространства зависимости видим, что матроиды - это в точности конечные транзитивное пространства зависимости.

Рассмотрим следующие примеры матроидов:

Пример 1.

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

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

Пример 2.

Свободные матроиды. Если - произвольное конечное множество, то - матроид. Такой матроид называется свободным. В свободном матроиде каждое множество независимо, А является базисом и .

Пример 3.

Матроид трансверсалей. Пусть - некоторое конечное множество, и - некоторое семейство подмножеств этого множества. Подмножество называется частичной трансверсалью семейства , если содержит не более чем по одному элементу каждого подмножества из семейства . Частичные трансверсали над образуют матроид на А.

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

Пусть имеются конечное множество , , весовая функция и семейство .

Рассмотрим следующую задачу: найти , где . Другими словами, необходимо выбрать в указанном семействе подмножество наибольшего веса.

Не ограничивая общности, можно считать, что

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

Изначально искомое множество пусто, далее просматриваем по очереди все элементы из множества и проверяем зависимость множества, если - независимо, то элемент добавляем в множество , если же - зависимо, то переходим к элементу , пока все элементы из множества не будут проверены.

Алгоритм такого типа называется «жадным». Совершенно очевидно, что по построению окончательное множество , то есть независимо. Также очевидно, что жадный алгоритм является чрезвычайно эффективным: количество шагов составляет , то есть жадный алгоритм является линейным. (Не считая затрат на сортировку множества и проверку независимости .)

Пример 4.

Пусть дана матрица . Рассмотрим следующие задачи.

Задача 1. Выбрать по одному элементу из каждого столбца, так чтобы их сумма была максимальна.

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

Множество упорядоченно следующим образом:

.

Семейство независимых подмножеств будут образовывать такие множества, в которых все элементы из разных столбцов и пустое множество.

Наш алгоритм будет работать следующим образом:

0 шаг (нач. усл.): ;

1 шаг: поверяем для элемента , ;

2 шаг: для ,;

3 шаг: для ,;

4 шаг: для ,;

5 шаг: для ,;

6 шаг: для ,;

7 шаг: для ,;

8 шаг: для ,;

9 шаг: для ,;

В результате получили множество , ., полученный результат действительно является решением задачи.

Задача 2. Выбрать по одному элементу из каждой строки, так чтобы их сумма была максимальна.

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

Используя наш алгоритм получим следующее решение: множество и , которое так же является верным.

Задача 3. Выбрать по одному элементу из каждого столбца и из каждой строки, так чтобы их сумма была максимальной.

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

Нетрудно видеть, что жадный алгоритм выберет следующие элементы:

и , которые не являются решением задачи, поскольку существует лучшее решение - и .

Возникает вопрос, в каких же случаях жадный алгоритм действительно решает поставленную задачу? На поставленный вопрос поможет ответить теорема, сформулированная и доказанная в [4, с.75-76].

Теорема 7.

Для любой функции жадный алгоритм находит независимое множество с наибольшим весом, тогда и только тогда, когда является матроидом.

Действительно, в нашем примере в задачах 1 и 2 - матроид, а в задаче 3 таковым не является, так как не выполняется аксиома М₃. Если рассмотреть , тогда получили противоречие с независимостью хотя бы одного из множеств.

Список библиографии

1. Ван дер Варден Б.Л. Алгебра. - М.: Наука, 1976. - 648 с.

2. Кон П. Универсальная алгебра. - М.: Мир, 1968. - 352 с.

3. Курош А. Г. Курс высшей алгебры. - СПб: Лань, 2006. - 432 с.

4. Новиков Ф. А. Дискретная математика для программистов. - Спб: Питер, 2001. - 304 с.

5. Фрид Э. Элементарное введение в абстрактную алгебру. - М.: Мир, 1974. - 260 с.