Вивчення поняття відносин залежності
Властивість
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. Вибрати по одному елементі з кожного стовпця, так щоб їхня сума була максимальна.
Тут вагова
функція
ставить у
відповідність
елементу матриці
його значення.
Наприклад,
.
Множина
в такий спосіб:
![]()
.
Сімейство
незалежних
підмножин
будуть утворювати
такі множини,
у яких всі елементи
з різних