Головна |
Класифікація алгоритмічних задач на графах
Завдання мережевого планування:
Нехай задана транспортна мережа з орієнтованими дугами. У дуг задані їх довжини. Потрібно вирішити одну з наступних завдань:
А) Знайти довжелезний шлях (без повторення) від входу до виходу вздовж напрямку стрілок. Шлях вважається більше, якщо сума довжин його дуг більше;
В) Визначення длиннейшего або найкоротшого шляху від входу до вершин у напрямку;
С) Визначення тупиків і контурів в мережі.
Тупик - висяча вершина, у якій є вхідний потік і немає виходить.
Контур - простий цикл, побудований у напрямку.
Завдання пошуку:алгоритми пошуку тупиків є алгоритмами пошуку всіх вершин з визначенням ступеня входу і виходу для всіх вершин Ці значення не можуть бути = 0найдя нульову ступінь ми знайдемо вершину, що є тупиком.
Пошук контурів більш складне завдання. Зазвичай вирішується видаленням крайніх вершин. Цей алгоритм прибирає вершини і дуги, кіт. не входять до цикл, а залишаючи ті, кіт. входять. Як тільки ми не можемо видалити жодної дуги, то все решта є циклічними. Тупики та контури це помилки при побудові мережевого графіка.
Завдання про максимальний потік
Мережа - Зв'язний граф, частина вершин якого виділена і наз-ся полюсами. Розрізняють однополюсні і двополюсні мережі.
транспортною мережею наз-ют двухполюсную мережу, в одному - витік, в іншому - стік, вони мають напрямок і довжину (пропускна здатність мережі).
потік - Це функція, яка визначена на ребрах або дугах таким чином. Що вона завжди позитивна для будь-якого ребра і його пропускної здатності.
Для потоків повинні виконуватися закони Кірхгофа:
- В будь-якій вершині сума вхідних потоків = сумі виходять
- Вхідний потік всієї мережі = вихідного потоку даної мережі
перетином мережі - Наз-ся таке безліч ребер, які ділять мережу на дві частини, і її вхід в одній стороні, з виходом - в інший. У кожного перетину можна підсумувати пропускну здатність ребер. Ця величина наз-ся пропускною спроможністю перетину.
У завданнях max и min пропускної здатності мережі потрібно визначити відповідно до теореми Форда-Фолкерсона, min пропускну здатність простого перетину.
просте перетин - переріз. У якого немає ребер, які можна виключити.
Дерев'яний алгоритм. | Теорема Форда-Фолкерсона
Конструктор і деструктор класу. | Поняття графа, методи опису графа, види графів. Ейлерови і Гамільтона графи. | Способи завдання графів | Комбінаторні об'єкти дискретної математики. Алгоритмічні завдання комбінаторики. Завдання комівояжера. | розбиття | розбиття чисел | біномінальні коефіцієнти | Рекурентні співвідношення. | Завдання комівояжера. Загальний опис | жадібний алгоритм |