Курсова робота
Вивчення поняття відносин залежності
Зміст
Введення
1. Визначення й приклади
2. Простір залежності
3. Транзитивність
4. Зв'язок транзитивнихвідносин залежності з операторами замикання
5. Матроїди
Висновок
Список літератури
Введення
Метою курсової роботи є вивчення поняття відносинизалежності, розгляд відносини залежності на різних множинах.
Поставлена мета припускає рішення наступних задач:
Вивчити й дати визначення поняттю відношеннязалежності.
Розглянути деякі приклади відносини залежності.
Сформулювати й довести властивості й теореми як длядовільних, так і для транзитивних просторів залежності.
Розглянути теорему про зв'язок транзитивноговідношення залежності й алгебраїчного оператора замикання.
Вивчити поняття матроїда, привести приклади матроїдів.
Розглянути жадібний алгоритм і його зв'язок зматроїдами.
На підставі поставлених цілей і задач кваліфікаційнаробота розбивається на 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 випадки:
/>, тобто всі множини незалежні,тоді /> />.
/> 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
По лемі про заміну множина /> можна доповнити до базису Dелементами базису З, скажемо
/>, t ≤ s
Тепер перетинання D c У складається з n+ 1 елемента, і D містить, крім того, ще t (У містить, крім цього перетинання, ще 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. 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 на А.
Доказ:
Будемо називати підмножину Т множини 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. Якщорозглянути /> />, тоді /> одержалипротиріччя з незалежністю хоча б одного із множин.
Висновок
У роботі були розглянуті такі питання, як:
Вивчення й визначення поняття відношення залежності.
Розглянуті деякі приклади відносин залежності.
Сформулювали й довели властивості теореми як длядовільних, так і для транзитивних просторів залежності. Робота дала відповідіна всі питання, які були поставлені за мету.
Список літератури
1. Ван дер Варден Б.Л.Алгебра. – К., 2004
2. Кон П. Універсальнаалгебра. – К., 2004.
3. Курош О. Г. Курс вищоїалгебри. – К., 2003.
4. Новиков Ф. А. Дискретнаматематика для програмістів. – К., 2005
5. Фрид Е. Елементарневведення в абстрактну алгебру. – К., 2000