Абстрактное отношение зависимости (стр. 7 из 9)

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

Теорема 6.

Для любого транзитивного отношения зависимости

Z

отображение

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

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

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

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

.

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

, где - семейство замкнутых множеств, то пусть

- такое независимое подмножество множества B, что зависимо; поскольку для всех , имеем , откуда , то есть В замкнуто.

Пусть

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

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

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

II. Обратно, пусть

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

Будем считать

зависимым, если

для некоторого

, и независимым в противном случае.

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

Теперь для любых

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

Обратно, если

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

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

и , поэтому .

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

.

Пусть

и . Тогда , , но .

§5. Матроиды

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

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

Матроидом

называется конечное множество и семейство его подмножеств

, такое что выполняется три аксиомы:

М₁:

;

М₂:

;

М₃:

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

Элементы множества

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

- зависимыми множествами.

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

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

Пример 1.

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

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

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