Абстрактное отношение зависимости
Содержание
Введение 3
§1.Определения и примеры 5
§2. Пространства зависимости 12
§3. Транзитивность 16
§4. Связь транзитивных отношений зависимости с операторами замыкания 23
§5. Матроиды 27
Список библиографии 32
Введение
Целью квалификационной работы является изучение понятия отношения зависимости, рассмотрение отношения зависимости на различных множествах.
Поставленная цель предполагает решение следующих задач:
Изучить и дать определение понятию отношение зависимости.
Рассмотреть некоторые примеры отношения зависимости.
Сформулировать и доказать свойства и теоремы как для произвольных, так и для транзитивных пространств зависимости.
Рассмотреть теорему о связи транзитивного отношения зависимости и алгебраического оператора замыкания.
Изучить понятие матроида, привести примеры матроидов.
Рассмотреть жадный алгоритм и его связь с матроидами.
На основании поставленных целей и задач квалификационная работа разбивается на 5 параграфов.
В первом параграфе приведены основные определения и рассмотрены некоторые примеры отношения зависимости.
Во втором – рассматриваются произвольные пространства зависимости, их свойства и некоторые теоремы.
Третий – посвящен транзитивным и конечномерным пространствам зависимости. Здесь рассмотрены свойства транзитивных пространств зависимости и доказаны теоремы, которые подтверждают существования базиса и инвариантность размерности в любом конечномерном транзитивном пространстве зависимости.
В четвертом параграфе формулируются основные определения касающиеся оператора замыкания и рассмотрена теорема о представлении транзитивного отношения зависимости с помощью алгебраического оператора замыкания.
Пятый параграф посвящен матроидам, примерам матроидов и их применению при изучении теоретической основой анализа «жадных» алгоритмов.
Основной литературой при написании квалификационной работы стали монографии: Кона П. «Универсальная алгебра» [2] и Куроша А. Г. «Курс высшей алгебры» [3].
§1.Определения и примеры
Определение 1.
Множество Z подмножеств множества A назовем отношением зависимости на A, если выполняются следующие аксиомы:
Z>1>:
Z
;
Z>2>:
Z
Z
;
Z>3>:
Z
(
Z
-
конечно).
Подмножество множества A называется зависимым, если оно принадлежит Z, и независимым в противном случае.
Легко убедиться в независимости аксиом Z>1 >- Z>3>..
Модель 1:
.
Полагаем Z
= B (А)
для любого множества
.
Модель 2:
.
Пусть Z
=
при
.
Модель 3:
.
Пусть Z
=
для бесконечного множества
.
Определение 2.
Пространством
зависимости
назовем пару
Z
,
где Z
– отношение зависимости на A.
Определение 3.
Элемент
называется зависимым
от множества
,
если а
X
или
существует такое независимое подмножество
Y
множества
X,
что
зависимо,
т.е.
Z
Z ).
Из определения
1 вытекает, что если элемент
зависит от множества
,
то он зависит от некоторого конечного
подмножества
.
Определение 4.
Множество
всех элементов, зависящих от X,
называется
оболочкой
множества
X
и
обозначается через
.
Ясно, что
и включение
влечет включение их оболочек:
.
Определение 5.
Если
= A, то X
называется
порождающим
множеством
множества
A.
Определение 6.
Независимое порождающее подмножество множества A называется базисом множества A.
Определение 7.
Множество
зависит
от
,
если любой элемент из
зависит от
,
то есть
.
Определение 8.
Отношение
зависимости Z
на A
будем называть транзитивным
отношением
зависимости,
если
.
Определение 9.
Транзитивным пространством зависимости назовем пространство зависимости, в котором отношение зависимости обладает свойством транзитивности.
В качестве теоретико-множественного постулата будем использовать следующий принцип, эквивалентный известной аксиоме выбора.
Лемма Цорна.
Непустое упорядоченное множество, в котором каждое линейно упорядоченное подмножество обладает верхней гранью, имеет максимальный элемент.
Далее целесообразно рассмотреть некоторые примеры отношения зависимости:
Пример 1.
Понятие
линейной зависимости в векторном
пространстве V
над полем
.
Система
векторов векторного пространства V
называется линейно
зависимой,
если существует конечная линейно
зависимая ее подсистема, в противном
случае – линейно
независимой.
Понятие
линейной зависимости в конечномерных
векторных пространствах дается в курсе
алгебры. Конечная
система векторов
V
называется линейно
зависимой,
если существуют элементы поля
одновременно не равные нулю и такие,
что линейная комбинация
.
Множество
линейных комбинаций множества
векторов векторного
пространства V
с коэффициентами из поля P
называется линейной
оболочкой
этих векторов и обозначается
.
При этом
- является подпространством в пространстве
V,
порожденным
.
Получаем транзитивное отношение
зависимости.
Пример 2.
Пусть поле
является расширением основного поля
Р, а
минимальное подкольцо содержащее
элементы
и поле Р.
Подкольцо
состоит из всех элементов поля
,
которые выражаются через элементы
и
элементы поля Р
при помощи сложения, вычитания и
умножения: это будут всевозможные
многочлены от
с коэффициентами из поля Р.
Тогда, если для всякого элемента
существует единственная запись в виде
многочлена от
как неизвестных с коэффициентами из
поля Р, то
есть если различные многочлены от
будут различными элементами подкольца
,
то система
элементов
,
будет называться алгебраически
независимой
над полем Р, в противном
случае алгебраически
зависимой. Произвольное
множество элементов поля Р
называется зависимым,
если оно содержит конечное зависимое
подмножество. В
первом случае кольцо
изоморфно кольцу многочленов
.
Отношение алгебраической зависимости
над полем Р
является транзитивным отношением
зависимости.
Пример 3.
Пусть на
множестве A
задано рефлексивное и симметричное
бинарное отношение
(называемое отношением сходства).
Подмножество
X
множества A
будем
считать зависимым,
если оно содержит два различных элемента,
находящихся в отношении
.
Оболочкой
множества
служит множество
В этом случае
можно усилить аксиому
отношения зависимости следующим образом:
Z
Z.
Тогда
оболочкой множества
будет множество всех элементов,
находящихся в отношении сходства хотя
бы с одним элементом из множества
.
Введенное
отношение зависимости будет транзитивным
тогда и только тогда, когда соответствующее
бинарное отношение
будет транзитивно, то есть является
отношением эквивалентности на
.
В случае,
когда
- отношение эквивалентности
будет независимым
тогда и только тогда, когда
множество
содержит не более одного элемента. Любое
максимальное независимое подмножество
будет содержать ровно по одному элементу
из каждого класса эквивалентности
.
Пример 4.
Рассмотрим четырехэлементное
множество
.
Назовем подмножество
множества
зависимым
тогда и только тогда, когда
или
.
Z
.
Рассмотрим подмножество
множества
,
по введенному определению оно будет
независимо. Рассмотрим оболочку множества
и найдем оболочку оболочки нашего
множества
.
Таким образом, мы получили
,
то есть рассмотренное нами отношение
зависимости не является транзитивным.
Пример 5.
Рассмотрим
произвольное множество
и
.
Множество
будем считать зависимым,
если
B (А)\ B (В), то есть
,
но
.
Таким
образом, получили следующее транзитивное
пространство зависимости:
B (А)\ B (В
.
Оболочкой
будет множество
.
В частности можно рассмотреть 2 случая:
,
то есть все множества независимы, тогда
.
B (А)
,
то есть
все множества, кроме пустого, будут
зависимыми, в этом случае
.
Пример 6.
Рассмотрим
произвольное множество
и его непустое конечное подмножество
.
Введем на множестве А
следующее отношение зависимости
Z
B (А)
.
Таким образом,
зависимыми будут все надмножества
множества
.
Если
,
то
.
Если
,
то
.
Если
,
то
.
Получаем транзитивное пространство зависимости.
Пример 7.
Подпространство
пространства зависимости
Z.
Рассмотрим
,
где действует то же отношение зависимости
Z.
Тогда
получим индуцированное пространство
зависимости
Z
B
.
В этом случае зависимыми будут только
те подмножества множества
,
которые были зависимы в пространстве
Z.
И если
пространство
Z
транзитивно,
то транзитивным будет и подпространство
.
Пример 8.
Пусть
и Z
=
.
Такое пространство зависимости
Z
не
транзитивно, так как
и
.
Пространство А имеет два базиса
и
,
которые являются и единственными
минимальными порождающими множествами
в
.
Этот пример показывает, что существуют не транзитивные пространства зависимости, в которых минимальные порождающие множества независимы, то есть являются базисами.
Пример 9.
Зададим на множестве N натуральных чисел следующее отношение зависимости:
Z
.
Получаем
бесконечную строго возрастающую цепочку
оболочек в
Z.
При
получаем
.
Таким образом,
имеем
.
Замечание.
Понятие
пространства зависимости можно и удобно
определять через базу зависимости.
Именно, множество
B
всех минимальных зависимых множеств
пространства зависимости
Z
назовем его базой.
Ясно, что множества из B
непусты, конечны и не содержатся друг
в друге. Кроме того, любое независимое
множество содержит некоторое множество
базы B.
Пространство
Z
имеет единственную базу и однозначно
определяется ей. Поэтому пространства
зависимости можно задавать базами.
Легко видеть, что верно следующее утверждение:
Непустое
множество B
подмножеств множества
задает на
отношение зависимости тогда и только
тогда, когда множества из B
непусты, конечны и не включены друг в
друга.
В терминах базы B можно сформулировать условие транзитивности соответствующего пространства зависимости.
§2. Пространства зависимости
Теорема 1.
Пусть
Z
- произвольное пространство зависимости.
Рассмотрим следующие три утверждения:
X — базис в A;
X — максимальное независимое подмножество в A;
X — минимальное порождающее множество в A.
Тогда
и
.
Доказательство:
(i)
(ii) Если
X
– базис, то по определению 6 X
– независимое порождающее подмножество.
Докажем от противного, что оно максимальное.
Пусть существует независимые множества
.
Возьмем
,
тогда
независимо, так как любое подмножество
независимого множества независимо.
Поэтому по определениям 3 и 5
,
откуда
,
получили противоречие с условием.
Поэтому X
является максимальным независимым
подмножеством в A.
(ii)
(i) Докажем
от противного, пусть
не базис в
,
то есть
.
Тогда
такое, что
независимо
и лежит в
,
получили противоречие с максимальностью
.
(ii)
(iii) Если X
— максимальное
независимое множество в A,
то всякий элемент у
A
либо принадлежит X,
либо таков,
что
зависимо,
а поэтому
в том и
другом случае, то есть
Поскольку
,
то X
- порождающее
множество.
Значит,
- базис пространства
.
Докажем
теперь, что оно минимально. Пусть
множество
.
Докажем, что оно не является порождающим
для A.
Возьмем
,
но
.
Тогда
независимо, как подмножество множества
X.
Поэтому по определениям 3 и 5
и
,
а это значит, что Y
не является порождающим множеством.
Вывод: X
– минимальное
порождающее множество в A.
(i)
(iii) Справедливо,
по доказанным выше утверждениям (i)
(ii)
и (ii)
(iii).
■
Определение - обозначение 10.
Для произвольного
множества
пространства зависимости
Z
обозначим
множество всех максимальных независимых
подмножеств, а через
- множество всех минимальных порождающих
подмножеств этого множества.
Из теоремы 1
вытекает, что
совпадает с множеством всевозможных
базисов пространства
и
для любого
.
Следующий
пример показывает, что обратное включение
верно не всегда.
Пример 10.
Рассмотрим
девятиэлементное множество
,
которое записано в виде матрицы
.
Зависимыми
будем считать подмножества множества
,
содержащие «прямые линии»: столбцы,
строки или диагонали матрицы
.
Рассмотрим
множества
и
,
они будет максимальными независимыми,
так как не содержат прямых и при добавлении
любого элемента из
,
не лежащего в них, становятся зависимыми.
Здесь максимальные независимые множества
содержат разное количество элементов.
Рассмотрим
еще одно множество
,
оно является минимальным порождающим,
так как если исключить из него хотя бы
один элемент, то оно уже не будет
порождающим множеством. Легко заметить,
что
зависимо, поэтому не является базисом.
Данный пример иллюстрирует, что (iii)
(i)
не верно в общем случае, то есть для
произвольных пространств зависимости.
Для любого
пространства зависимости
Z
выполняются следующие свойства:
Замещение.
Если
Доказательство:
Пусть
,
.
Так как
зависит от
,
то
зависит от независимого подмножества
множества
,
то есть
зависимо. Теперь, если бы
,
то
было бы подмножеством множества
и поэтому
,
что противоречило бы нашему предположению.
Поэтому
.
Возьмем
.
Тогда
независимо, так как
.
Но
зависимо. Откуда
.
Вложенность.
Объединение
любой системы вложенных друг в друга
независимых множеств является независимым
множеством, то есть
- независимо, где
также независимы и
Доказательство:
Докажем от
противного. Предположим, что
зависимо, тогда в нем найдется конечное
зависимое подмножество
:
.
Имеем
,
получили противоречие с независимостью
.
Максимальность. Любое независимое множество содержится в максимальном независимом множестве.
Доказательство:
Пусть
- произвольное независимое множество
в
.
Образуем множество
Z
:
всех
независимых множеств, содержащих
.
Относительно
множество
является упорядоченным множеством,
удовлетворяющим по свойству вложенности,
условию леммы Цорна. Тогда по лемме
Цорна в
существует максимальный элемен
.
Теорема 2.
Любое пространство зависимости обладает базисом.
Доказательство:
Возьмем пустое множество, оно независимо. По свойству максимальности оно должно содержаться в некотором максимальном независимом множестве, которое по теореме 1 является базисом.
§3. Транзитивность
Особый интерес представляют транзитивные пространства зависимости. Важным результатом является доказательство инвариантности размерности любого транзитивного пространства зависимости.
Докажем
некоторые свойства,
справедливые для транзитивных пространств
зависимости
Z.
Свойство 1:
зависит от
.
Доказательство:
зависит от
,
то есть
,
и
.
Рассмотрим
,
тогда
- независимо и
- зависимо, а
,
получаем, что
,
поэтому
.
Имеем
.
По
определению 8 любое подмножество
зависит от
Свойство 2: Если
зависит от
,
а
зависит от
,
то
зависит от
.
Доказательство:
Запишем
условие, используя свойство 1
,
а
,
тогда очевидно, что
.■
Свойство 3: Если X — минимальное порождающее множество в A, то X — базис в A.
Доказательство:
Пусть X — минимальное порождающее множество в A. Покажем, что оно не может быть зависимым, так как в этом случае его можно было бы заменить собственным подмножеством, все еще порождающим A. Действительно, в силу транзитивности отношения зависимости, любое множество, порождающее множество X, будет так же порождать и множество A. Следовательно, X - независимое порождающее множество, которое по определению 6 является базисом.
Свойство 4:
для любого
.
Доказательство: Следует из свойства 3.
Свойство 5 (о замене.) :
Если X
— независимое
множество и Y
— порождающее
множество в A,
то существует такое подмножество
множества Y,
что
и
— базис
для A.
Доказательство:
Рассмотрим
систему J
таких независимых подмножеств Z
множества A,
что
.
Так как X
независимо,
то такие множества существуют; кроме
того, если
—
некоторое линейно упорядоченное
множество множеств из J,
то его
объединение
снова принадлежит J,
поскольку
Z
удовлетворяет условию
,
и если Z
зависимо, то некоторое конечное
подмножество множества Z
должно было бы быть зависимым; это
подмножество содержалось бы в некотором
множестве
в противоречии с тем
фактом, что все
независимы.
По лемме Цорна
J
имеет
максимальный элемент М;
в силу
максимальности каждый элемент множества
Y
либо
принадлежит М,
либо зависит
от М, откуда
.
Этим доказано, что М — базис в
A.
Так как
,
то М имеет вид
,
где
удовлетворяет условиям
.■
Определение 11.
Пространство
зависимости
Z
называется конечномерным, если любое
его независимое множество конечно.
Теорема 3.
Пусть
Z
- транзитивное пространство зависимости.
Тогда любые два базиса в этом пространстве
равномощны.
Доказательство:
Рассмотрим
сначала случай конечномерного пространства
.
Пусть В,
С — любые
два базиса в А,
их существование обеспечивается теоремой
2, и
,
,
,
где различные элементы обозначены
различными буквами или снабжены
различными индексами. Применим
индукцию по max
(r,
s).
Если r
= 0 или s
= 0, то
или
,
и
.
Поэтому можно предполагать, что r
≥ 1, s ≥ 1,
без ограничения общности будем считать,
что r > s,
так что на самом деле r
> 1.
Предположим, что базисы будут равномощными для любого t < r
По лемме о
замене множество
можно дополнить до базиса D
элементами базиса С,
скажем
,
t ≤ s < r.
Теперь
пересечение D
c В
состоит из n
+ 1 элемента,
и D содержит,
кроме того, еще t (< r) элементов, тогда
как В
содержит, кроме этого пересечения, еще
r - 1 элементов, так что по предположению
индукции
,
то есть
.
Поскольку r
> 1, отсюда
вытекает, что t
≥ 1, и
поэтому пересечение D
с С содержит не меньше чем n+1
элементов. Используя еще раз предположение
индукции, находим, что
и, следовательно, r
= s и базисы
В и
С равномощны.
Далее, пусть
В
- конечный базис в
.
Тогда и любой другой базис С
пространства
будет конечным. Действительно, В
выражается через конечное множество
элементов
в силу транзитивности
будет порождающим и независимым
множеством в
,
то есть
.
Наконец, если базисы В и С бесконечны. Каждый элемент из В зависит от некоторого конечного подмножества базиса С, и наоборот. Мощность множества всех конечных подмножеств всякого бесконечного множества равна мощности самого множества. Поэтому мощности В и С совпадают.■
Теорема 4.
Пусть
Z
- произвольное пространство зависимости,
тогда следующие условия эквивалентны
Z транзитивно;
для любого конечного
;
конечных и
Z
Z;
для любого конечного
.
Доказательство:
(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о:
.
Доказательство: вытекает из свойства 40;
Свойство 7о:
.
Доказательство:
.
§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
| Y
X}.
Обратно, каждый оператор замыкания J на
определяет
систему замыканий E
J
.
Следующая теорема показывает связь транзитивного отношения зависимости и алгебраического оператора замыкания.
Теорема 6.
Для любого транзитивного
отношения зависимости
Z
отображение
является алгебраическим оператором
замыкания на
А
со свойством замещения.
Обратно, любой алгебраический оператор замыкания на А со свойством замещения получается таким способом из некоторого транзитивного отношения зависимости Z на А.
Доказательство:
Будем называть
подмножество Т множества A
замкнутым,
если
.
Покажем сначала, что
замкнутые подмножества образуют систему
замыканий. Если
,
где
- семейство замкнутых множеств, то пусть
- такое независимое подмножество
множества B,
что
зависимо; поскольку
для всех
,
имеем
,
откуда
,
то есть В замкнуто.
Пусть
,
то по определению 3
Z
конечное, такое что
зависимо. В первом случае
,
а во втором
.
И поскольку
замкнуто в силу транзитивности, получаем
алгебраический оператор замыкания.
Этим доказано, что замкнутые подмножества образуют алгебраическую систему замыканий.
Выполнение свойства замещения следует из соответствующего свойства пространств зависимости.
Обратно, пусть
- алгебраический оператор замыкания
со свойством замещения.
Будем считать
зависимым, если
для некоторого
,
и независимым
в противном случае.
Так как оператор алгебраический, то отсюда вытекает, что всякое зависимое множество обладает конечным зависимым подмножеством, и поскольку очевидно, что всякое множество, содержащее зависимое подмножество, само зависимо, таким образом получаем отношение зависимости. Условие транзитивности выполняется по определению, и это показывает, что мы имеем транзитивное отношение зависимости.
Теперь для любых
,
имеем
тогда и только тогда, когда
для некоторого конечного подмножества
множества
.
Выбирая
минимальным, можем предполагать, что
независимо. Отсюда вытекает, что
и, следовательно,
.
Обратно, если
,
то снова
для некоторого конечного независимого
подмножества
множества
.
Это означает, что
зависимо, т.е.
для некоторого
.
В силу свойства замещения
получаем, что
и
,
поэтому
.
Замечание.
Существуют алгебраические
операторы замыкания, не обладающие
свойством замещения. Для примера возьмем
бесконечную циклическую полугруппу
.
Пусть
и
.
Тогда
,
,
но
.
§5. Матроиды
Понятие матроида тесно связано с понятием отношения зависимости, поэтому эта тема рассматривается в данной квалификационной работе. Однако с другой стороны оно является теоретической основой для изучения и анализа «жадных» алгоритмов.
Определение 17.
Матроидом
называется конечное множество и
семейство его подмножеств
,
такое что выполняется три аксиомы:
М>1>:
;
М>2>:
;
М>3>:
Определение 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 таковым не является,
так как не выполняется аксиома М>3>.
Если рассмотреть
,
тогда
получили противоречие с независимостью
хотя бы одного из множеств.
Список библиографии
Ван дер Варден Б.Л. Алгебра. – М.: Наука, 1976. – 648 с.
Кон П. Универсальная алгебра. – М.: Мир, 1968. – 352 с.
Курош А. Г. Курс высшей алгебры. – СПб: Лань, 2006. – 432 с.
Новиков Ф. А. Дискретная математика для программистов. – Спб: Питер, 2001. – 304 с.
Фрид Э. Элементарное введение в абстрактную алгебру. – М.: Мир, 1974. – 260 с.