Курсова робота
Вивчення поняття відносин залежності
Зміст
Введення
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 < 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. 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
|