Абстрактне відношення залежності

Зміст

Введення

§ 1.Визначення та приклади

§ 2. Простору залежності

§ 3. Транзитивність

§ 4. Зв'язок транзитивних відносин залежності з операторами замикання

§ 5. Матроіди

Список бібліографії

Введення

Метою кваліфікаційної роботи є вивчення поняття відношення залежності, розгляд відносини залежності на різних множинах.

Поставлена мета передбачає вирішення наступних завдань:

Вивчити і дати визначення поняттю відношення залежності.
Розглянути деякі приклади відносини залежності.
Сформулювати і довести властивості і теореми як для довільних, так і для транзитивних просторів залежності.
Розглянути теорему про зв'язок транзитивного відносини залежності і алгебраїчного оператора замикання.
Вивчити поняття матроіда, привести приклади матроідов.
Розглянути жадібний алгоритм і його зв'язок з матроідамі.

На підставі поставлених цілей і завдань кваліфікаційна робота розбивається на 5 параграфів.

У першому параграфі наведено основні визначення і розглянуті деякі приклади відносини залежності.

У другому - розглядаються довільні простору залежності, їх властивості та деякі теореми.

Третій - присвячений транзитивним та скінченновимірних просторів залежності. Тут розглянуті властивості транзитивних просторів залежності і доведені теореми, які підтверджують існування базису і інваріантність розмірності в будь-якому конечномерное транзитивної просторі залежності.

У четвертому параграфі формулюються основні визначення стосуються оператора замикання і розглянута теорема про подання транзитивного відносини залежності за допомогою алгебраїчного оператора замикання.

П'ятий параграф присвячений матроідам, прикладів матроідов та їх застосування при вивченні теоретичної основою аналізу «жадібних» алгоритмів.

Основний літературою при написанні кваліфікаційної роботи стали монографії: Кона П. «Універсальна алгебра» [2] і Куроша А. Г. «Курс вищої алгебри» [3].

§ 1.Визначення та приклади

Визначення 1.

Безліч Z підмножин множини A назвемо ставленням залежності на A, якщо виконуються наступні аксіоми:

Z _1: Z;

Z _2: Z Z;

Z _3: Z ( Z - Звичайно).

Підмножина множини A називається залежним, якщо воно належить Z, і незалежним у противному випадку.

Легко переконатися в незалежності аксіом Z ₁ - Z ₃ ..

Модель 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

для будь-якого кінцевого .

Доказ:

(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 ^про: .

Доказ: випливає з властивості 4 ^0;

Властивість 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. Якщо розглянути , Тоді отримали протиріччя з незалежністю хоча б одного з множин.

Список бібліографії

Ван дер Варден Б.Л. Алгебра. - М.: Наука, 1976. - 648 с.
Кон П. Універсальна алгебра. - М.: Мир, 1968. - 352 с.
Курош А. Г. Курс вищої алгебри. - СПб: Лань, 2006. - 432 с.
Новиков Ф. А. Дискретна математика для програмістів. - Спб: Питер, 2001. - 304 с.
Фрід Е. Елементарне введення в абстрактну алгебру. - М.: Мир, 1974. - 260 с.