Головна

Алгоритмічні завдання пошуку в графах: завдання Прима-Краскала, Дейкстри, Форда-Фалкерсона.

  1. Cегментація ринку. Основні завдання. Критерії сегментації на В2С ринку.
  2. I. ЗАВДАННЯ МЕДИЧНИХ ПРАЦІВНИКІВ В ЗАБЕЗПЕЧЕННІ МАРША
  3. I.1.2. Цілі, завдання та види інженерних вишукувань.
  4. III. Цілі, завдання та результати розвитку фінансового ринку на період до 2020 року
  5. III.3.7. ПРЕДМЕТ І ЗАВДАННЯ Логопсихологія
  6. А) Основні алгоритмічні конструкції. Базові алгоритми.
  7. Автоматизація офісу. Основні завдання та використовуються інформаційні системи управління.

Класифікація алгоритмічних задач на графах

Завдання мережевого планування:

Нехай задана транспортна мережа з орієнтованими дугами. У дуг задані їх довжини. Потрібно вирішити одну з наступних завдань:

А) Знайти довжелезний шлях (без повторення) від входу до виходу вздовж напрямку стрілок. Шлях вважається більше, якщо сума довжин його дуг більше;

В) Визначення длиннейшего або найкоротшого шляху від входу до вершин у напрямку;

С) Визначення тупиків і контурів в мережі.

Тупик - висяча вершина, у якій є вхідний потік і немає виходить.

Контур - простий цикл, побудований у напрямку.

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

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

Завдання про максимальний потік

Мережа - Зв'язний граф, частина вершин якого виділена і наз-ся полюсами. Розрізняють однополюсні і двополюсні мережі.

транспортною мережею наз-ют двухполюсную мережу, в одному - витік, в іншому - стік, вони мають напрямок і довжину (пропускна здатність мережі).

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

Для потоків повинні виконуватися закони Кірхгофа:

- В будь-якій вершині сума вхідних потоків = сумі виходять

- Вхідний потік всієї мережі = вихідного потоку даної мережі

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

У завданнях max и min пропускної здатності мережі потрібно визначити відповідно до теореми Форда-Фолкерсона, min пропускну здатність простого перетину.

просте перетин - переріз. У якого немає ребер, які можна виключити.

Дерев'яний алгоритм. | Теорема Форда-Фолкерсона


Конструктор і деструктор класу. | Поняття графа, методи опису графа, види графів. Ейлерови і Гамільтона графи. | Способи завдання графів | Комбінаторні об'єкти дискретної математики. Алгоритмічні завдання комбінаторики. Завдання комівояжера. | розбиття | розбиття чисел | біномінальні коефіцієнти | Рекурентні співвідношення. | Завдання комівояжера. Загальний опис | жадібний алгоритм |

© 2016-2022  um.co.ua - учбові матеріали та реферати