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