Page 84 - 4496

5 8 7
6 9 11
7 10 10
8 11 11
9 12 13
11
12

Знаходження максимального шляху

Шлях максимальної довжини має зміст шукати тільки в
графах, де немає контурів. Дійсно, у графі з контурами
розв'язок однозначний і дорівнює нескінченності, тому що
існує шлях, нескінченне число раз минаючий по цьому
контуру. Одним із завдань, де використовується пошук
максимального шляху, є завдання аналізу мережевого графіка.
Дамо необхідні визначення.
Семантика завдання. Зіставимо кожній дузі роботу.
Вага дуги - час виконання роботи. Вершині зіставимо подію,
що полягає у тому, що всі роботи, приписані дугам, що
заходять у неї, виконані, і можна починати всі роботи,
приписані вихідним дугам. Граф з таким трактуванням
називається діаграмою ПЕРТ ( від Prograam Evaaluaation aand
Review Technique) або мережевим графіком
У мережевому графіку максимальному шляху,
названому критичним, буде відповідати мінімальний час,
необхідний для виконання всіх робіт. Для скорочення
загального часу можна розглядати, наприклад, питання про
автоматизацію робіт на критичному шляху з метою
скорочення часу їх виконання.
Для розв'язку завдання пошуку максимального шляху
можна скористатися алгоритмом Дейкстри, змінивши його
відповідним чином. Однак задана додаткова умова на граф
завдання: у ньому немає контурів. Додаткові умови можуть
зажадати перевірки їх виконання й ускладнити алгоритм, але
можна використовувати ці умови й для скорочення алгоритму,
що ми й зробимо.
Теорема: якщо в графі немає контурів, то його
вершини можна перенумерувати таким чином, що всяка дуга

81