86278 (612707), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

(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⁰;

Властивість 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.

Матроїдом називається кінцева множина й сімейство його підмножин , таке що виконується три аксіоми:

М₁: ;

М₂: ;

М₃:

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

Елементи множини називаються незалежними, а інші підмножини - залежними множинами.

Відповідно до уведеного раніше аксіомами простору залежності бачимо, що матроїди - це в точності кінцеві транзитивне простори залежності.

Розглянемо наступні приклади матроїдів:

Приклад 1.

Сімейство всіх лінійно незалежних підмножин будь-якої кінцевої множини векторів довільного непустого векторного простору є матроїдом.

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

Приклад 2.

Вільні матроїди. Якщо - довільна кінцева множина, то - матроїд. Такий матроїд називається вільним. У вільному матроїді кожна множина незалежно, А є базисом і .

Приклад 3.

Матроїд трансверсалей. Нехай - деяка кінцева множина, і - деяке сімейство підмножин цієї множини. Підмножина називається часткової трансверсалью сімейства , якщо містить не більш ніж по одному елементі кожної підмножини із сімейства . Часткові трансверсали над утворять матроїд на А.

Перейдемо до розгляду жадібного алгоритму. Для початку потрібно сформулювати задачу, що будемо вирішувати з його використанням.

Нехай є кінцева множина , , вагова функція й сімейство .

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

Не обмежуючи спільності, можна вважати, що

Розглянемо такий алгоритм, що вихідними даними має множину , сімейство його підмножин і вагарню функцію , причому множина впорядкована в порядку убування ваг елементів. Після виконання цього алгоритму ми одержимо підмножину .

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

Алгоритм такого типу називається «жадібним». Зовсім очевидно, що по побудові остаточна множина , тобто незалежно. Також очевидно, що жадібний алгоритм є надзвичайно ефективним: кількість кроків становить , тобто жадібний алгоритм є лінійним. (Не вважаючи витрат на сортування множини й перевірку незалежності .)

Приклад 4.

Нехай дана матриця . Розглянемо наступні задачі.

Задача 1. Вибрати по одному елементі з кожного стовпця, так щоб їхня сума була максимальна.

Тут вагова функція ставить у відповідність елементу матриці його значення. Наприклад, .

Множина в такий спосіб:

.

Сімейство незалежних підмножин будуть утворювати такі множини, у яких всі елементи з різних стовпців і порожня множина.

Наш алгоритм буде працювати в такий спосіб:

0 крок: ;

1 крок: перевіряємо для елемента , ;

Характеристики

Список файлов курсовой работы