85488 (589835), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

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

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

Теорема 4.

Пусть Z - произвольное пространство зависимости, тогда следующие условия эквивалентны

1. Z транзитивно;

2. для любого конечного ;

3. конечных и Z

Z;

1. для любого конечного .

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

(i) (ii) Справедливо по теореме 3 и примеру 7.

(ii) (iii) Возьмем , так что - независимы и . Допустим, что утверждение Z неверно. Тогда Z. Рассмотрим . Имеем . Но Z, поэтому Z . По (ii) имеем . Но - противоречие.

(iii) (ii) Докажем от противного. Пусть . Можно считать, что . Тогда по (iii) независимо. Получили противоречие с максимальностью

(iii) (i) Нужно доказать равенство для произвольного .

Возьмем и покажем, что Так как , то Пусть существует , тогда независимо и существует Z и Z . Расширяя в можно предположить, что По (ii) , то есть . Поэтому по (iii) Z . видим, что . Значит, . Получаем противоречие с тем, что Следовательно, , то сеть .

Теперь достаточно показать, что . Пусть , тогда зависимо, расширяя в можно предположить, что , кроме того , тогда по (ii) . независимо, поэтому . По (iii) Z . видим, что . Значит, , получили противоречие с максимальностью . Следовательно, , обратное включение очевидно, поэтому .

(iv) (ii) В силу теорем 1 и 3 и доказанной эквивалентности

(i) (ii).■

Далее будем рассматривать произвольное конечномерное транзитивное пространство зависимости Z .

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

Мощность максимального независимого подмножества данного множества называется рангом этого множества: .

Будем рассматривать конечные подмножества .

Имеют место следующие свойства.

Свойство 1^о: Z .

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

Свойство 2^о: Z .

Доказательство: Z, возьмем , тогда по свойству 1^о и . Обратное утверждение следует из определения 13.

Свойства 3^о – 7^о сформулированы для .

Свойство 3^о: .

Доказательство: Ясно, что , и так как число элементов любого подмножества не больше числа элементов самого множества, то данное свойство выполняется.

Свойство 4^о: .

Доказательство: следует из того, что любое независимое подмножество в можно продолжить до максимального независимого подмножества в ;

Свойство 5^о: .

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

Пусть Тогда И затем . Имеем .

Свойство 6^о: .

Доказательство: вытекает из свойства 4⁰;

Свойство 7^о: .

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

.

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

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

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

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

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

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

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

J. 2. X J(X);

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

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

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

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

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

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

Теорема 5.

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

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

Теорема 6.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

§5. Матроиды

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

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

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

М₁: ;

М₂: ;

М₃:

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

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

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

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

Пример 1.

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

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

Пример 2.

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

Характеристики

Список файлов ВКР