Ноу Інти, лекція, жадібні алгоритми і матроід

Анотація: матроід. Теорема Радо-Едмондс. Зважені паросполучення.

Жадібні алгоритми і матроід

Жадібними (градієнтними) називають алгоритми, що діють за принципом "максимальний виграш на кожному кроці". Така стратегія не завжди веде до кінцевого успіху - іноді вигідніше зробити не кращий, здавалося б, вибір на черговому кроці з тим, щоб в результаті отримати оптимальне рішення. Але для деяких завдань застосування жодних алгоритмів виявляється виправданим. Однією з найвідоміших завдань такого роду є завдання про оптимальному каркасі. Існує загальна теорія, що обґрунтовує застосовність жодних алгоритмів до задач певного типу, до якого належить і розглянутий в "попередній лекції" алгоритм Круськала. У цій лекції буде дано начерк цієї теорії. Потім буде розглянуто застосування жодного алгоритму в поєднанні з методом збільшують шляхів для вирішення завдання про паросочетание найбільшої ваги в дводольному графі зі зваженими вершинами.

Коли виникло питання про те, які обставини, при яких жадібний алгоритм результативним, або інакше - що особливого в тих завданнях, для яких він дає точне рішення, виявилося, що математична теорія, за допомогою якої щось в цьому можна прояснити, вже існує . Це теорія матроідов. основи якої були закладені Уїтні в роботі 1935 р Метою створення теорії матроідов було вивчення комбінаторного аспекту лінійної незалежності, а в подальшому виявилися різноманітні застосування поняття матроід. спочатку зовсім були на увазі.

Визначення. Матроід називається пара, де - кінцеве непорожня множина, - сімейство підмножин безлічі, що задовольняє умовам:

• (1) якщо і, то;
• (2) якщо, і, то існує такий елемент, що.

Елементи множини називаються елементами матроід. а безлічі з сімейства - незалежними множинами матроід. Максимальна по включенню незалежне безліч називають базою матроід. З аксіоми (2) випливає, що всі бази матроід складаються з однакової кількості елементів.

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

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

Теорема 1. Якщо - звичайний граф. - сімейство всіх ациклічних підмножин множини, то пара є матроід.

Доведення. Аксіома (1) виконується, так як будь-яке підмножина ациклического безлічі, очевидно, є ациклічним. Доведемо, що виконується і (2). Нехай і - два ациклических безлічі і. Припустимо, що не існує такого ребра, що безліч є ациклічним. Тоді при додаванні будь-якого ребра з безлічі до безлічі утворюється цикл. Це означає, що кінці кожного такого ребра належать одній компоненті зв'язності остовного подграфа, утвореного ребрами безлічі. Тоді кожна область зв'язності подграфа міститься в якій-небудь області зв'язності подграфа. Але компоненти зв'язності кожного з цих подграфов - дерева, а дерево з вершинами містить рівно ребер. Отже, в цьому випадку число ребер в не перевищувало б числа ребер в, що суперечить умові.

Базами графового матроід є все каркаси графа. Для зв'язкового графа це будуть всі його остовне дерева.