Вивчення поняття відносин залежності (стр. 7 из 8)
Цим доведено, що замкнуті підмножини утворять алгебраїчну систему замикань.
Виконання властивості заміщення потрібне з відповідної властивості просторів залежності.
Обернено, нехай
- алгебраїчний оператор замикання із властивістю заміщення.Будемо вважати 
залежним, якщо 
для деякого 
, і незалежним у противному випадку.
Тому що оператор алгебраїчний, то звідси випливає, що всяка залежна множина має кінцеву залежну підмножину, і оскільки очевидно, що всяка множина, що містить залежну підмножину, саме залежно, у такий спосіб одержуємо відношення залежності. Умова транзитивності виконується по визначенню, і це показує, що ми маємо транзитивне відношення залежності.
Тепер для будь-яких
, 
маємо 
тоді й тільки тоді, коли 
для деякої кінцевої підмножини 
множини . Вибираючи 
мінімальним, можемо припускати, що 
незалежно. Звідси випливає, що 
й, отже, 
.Обернено, якщо
, те знову 
для деякої кінцевої незалежної підмножини множини . Це означає, що 
залежно, тобто 
для якогось 
.У силу властивості заміщення одержуємо, що
й 
, тому 
.Зауваження. Існують алгебраїчні оператори замикання, що не володіють властивістю заміщення. Для приклада візьмемо нескінченну циклічну напівгрупу
.Нехай
і 
. Тоді 
, 
, але 
.5. Матроїди
Поняття матроїда тісно пов'язане з поняттям відносини залежності, тому ця тема розглядається в даній кваліфікаційній роботі. Однак з іншої сторони воно є теоретичною основою для вивчення й аналізу «жадібних» алгоритмів.
Визначення 17.
Матроїдом 
називається кінцева множина й сімейство його підмножин 
, таке що виконується три аксіоми:
М1: 
;
М2: 
;
М3: 
Визначення 18.
Елементи множини 
називаються незалежними, а інші підмножини 
- залежними множинами.
Відповідно до уведеного раніше аксіомами простору залежності бачимо, що матроїди - це в точності кінцеві транзитивне простори залежності.
Розглянемо наступні приклади матроїдів:
Приклад 1.
Сімейство всіх лінійно незалежних підмножин будь-якої кінцевої множини векторів довільного непустого векторного простору є матроїдом.
Дійсно, по визначенню можна вважати, що порожня множина лінійно незалежно. Усяка підмножина лінійно незалежної підмножини векторів лінійно незалежно. Нехай
і 
- лінійно незалежні множини. Якби всі вектори із множини 
виражалися у вигляді лінійної комбінації векторів із множини 
, то множина була б лінійно залежним. Тому, серед векторів множини 
є принаймні один вектор 
, що не входить у множину й не виражається у вигляді лінійної комбінації векторів із множини . Додавання вектора 
до множини 
утворить лінійно незалежна множина.Приклад 2.
Вільні матроїди. Якщо
- довільна кінцева множина, то 
- матроїд. Такий матроїд називається вільним. У вільному матроїді кожна множина незалежно, А є базисом і 
.Приклад 3.
Матроїд трансверсалей. Нехай
- деяка кінцева множина, і 
- деяке сімейство підмножин цієї множини. Підмножина 
називається часткової трансверсалью сімейства 
, якщо містить не більш ніж по одному елементі кожної підмножини із сімейства . Часткові трансверсали над утворять матроїд на А.Перейдемо до розгляду жадібного алгоритму. Для початку потрібно сформулювати задачу, що будемо вирішувати з його використанням.
Нехай є кінцева множина
, 
, вагова функція 
й сімейство 
.Розглянемо наступну задачу: знайти
, де 
. Інакше кажучи, необхідно вибрати в зазначеному сімействі підмножина найбільшої ваги.Не обмежуючи спільності, можна вважати, що
Розглянемо такий алгоритм, що вихідними даними має множину
, сімейство його підмножин 
і вагарню функцію 
, причому множина впорядкована в порядку убування ваг елементів. Після виконання цього алгоритму ми одержимо підмножину 
.