Абстрактное отношение зависимости — страница 9

  • Просмотров 5704
  • Скачиваний 76
  • Размер файла 765
    Кб

транзитивного отношения зависимости и алгебраического оператора замыкания. Теорема 6. Для любого транзитивного отношения зависимости Z отображение является алгебраическим оператором замыкания на А со свойством замещения. Обратно, любой алгебраический оператор замыкания на А со свойством замещения получается таким способом из некоторого транзитивного отношения зависимости Z на А. Доказательство: Будем называть

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

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

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

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

циклическую полугруппу . Пусть и . Тогда , , но . §5. Матроиды Понятие матроида тесно связано с понятием отношения зависимости, поэтому эта тема рассматривается в данной квалификационной работе. Однако с другой стороны оно является теоретической основой для изучения и анализа «жадных» алгоритмов. Определение 17. Матроидом называется конечное множество и семейство его подмножеств , такое что выполняется три аксиомы: М1: ; М2: ; М3: