РефератыМатематикаВиВивчення поняття відносин залежності

Вивчення поняття відносин залежності

Курсова робота


Вивчення поняття відносин залежності


Зміст


Введення


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


5. Фрид Е. Елементарне введення в абстрактну алгебру. – К., 2000

Сохранить в соц. сетях:
Обсуждение:
comments powered by Disqus

Название реферата: Вивчення поняття відносин залежності

Слов:4791
Символов:35325
Размер:68.99 Кб.