7. Побудова сіткового графа.

Під час будівництва різноманітних споруд, виготов­лення технічних виробів, підготовки і проведення науко­вих і практичних експериментів доводиться виконувати велику кількість робіт. Виконання їх пов'язане в часі: розпочати одні роботи (за винятком початкової) можна лише тоді, коли виконано одну або кілька інших, підготовчих до них робіт. Інформацію про взаємозв'язок і порядок виконання всіх робіт якогось проекту найчастіше подають за допомогою орієнтованого графа, який доповнюють певними числовими даними, такими, наприклад, як кількість часу, потрібного для завершення конкретних робіт, час початку певної роботи, номери вершин графа тощо. Такий орграф називають сітковим графом (скорочено СГ) даного проекту. На СГ дугами зображають процеси виконання робіт, або просто роботи, а вершинами – відповідні події, які настають в результаті виконання однієї або кількох робіт.

Під роботою розуміють будь-який процес, дію, за допомогою якої досягають певних результатів. Наприклад, при спорудженні будинку можна назвати такі види робіт: 1) виготовлення проекту, 2) одержання дозволу на будівництво, 3) доставка потрібних будівельних матеріалів тощо.

Подіями називають результати виконання однієї або кількох робіт. Перелічені вище роботи приводять до таких подій: 1) проект виготовлено, 2) дозвіл на будівницт­во будинку одержано, 3) потрібні будівельні матеріали доставлено, тощо.

В СГ виділяють дві вершини: V₁, яка є початком, і V_n, що є завершенням усього проекту, всі інші вершини називають проміжними.

Не існує єдиного загального методу, користуючись яким можна побудувати сітковий графік для реаліза­ції будь-якого проекту. Сітковий графік подає розгорнуту картину всього процесу реалізації конкретного проекту з його індивідуальними деталями і особливостями, які потрібно вміти виявляти і враховувати. Тому до складання СГ залучають досвідчених інженерів, економістів та інших спеціалістів. Щоб можна було однозначно розуміти усі СГ і застосовувати до них математичні методи дослідження, СГ повинні мати загальну струк­туру незалежно від конкретного змісту, будуватися за загальними правилами.

Найважливіші правила побудови СГ:

1. Скласти список робіт, які потрібно виконати для реалізації проекту (такі списки можуть бути або деталізованими або укрупненими).

2. Відповідно до списку робіт скласти список подій.

3. Якщо подія, яка є завершенням операцій D₁, D₂, ...,D_n, дає можливість розпочати операції Q₁, Q₂, ..., Q_m, то на СГ це зображається так, як показано на рис. 2.1.

4. Якщо операція D₃ йде за операціями D₁ і D₂, а D₄ йде лише за D₂, причому завершення операцій D₁ і D_z дає подію Р, то вводять додаткову подію Р і фіктивну операцію D (рис. 2.2). Роботу називають фіктивною .якщо її виконання не вимагає затрати часу. У нашому випадку робота D полягає в тому, що за допомогою додаткової події Р' відображають той факт, що D₄ не залежить від D₁ a D₃ залежить від D₁ і D₂.

Рис. 2.1. Рис. 2.2. Рис. 2.3.

5. Якщо між подіями Р₁ і Р₂ виконуються дві паралельні операції D₁ і D₂, то використовують одну допоміж­ну подію і фіктивну операцію (рис. 2.3). Якщо виконуються кілька паралельних операцій, то вводять відповідну кількість допоміжних подій і фіктивних операцій.

6. В СГ не повинно бути так званих тупикових подій, тобто таких проміжних подій, які не дають початку ніякій роботі. Наприклад, на рис. 2.4 такою подією P₅.

Рис. 2.4.

7. В СГ не повинно бути так званих хвостових подій, тобто таких проміжних подій, яким не передує ніяка робота. Такою на рис. 2.4 є подія Р₃.

8. В СГ не повинно бути циклів, бо в такому разі створилася б практично неможлива ситуація, коли кож­на операція з циклу фактично ніколи не могла б початися: її початок залежав би від виконання інших операцій цього циклу.

У процесі аналізу і розрахунків на СГ нумерувати вершини зручно так, щоб для кожної дуги (r,s), виконувалось співвідношення r<s.

Розглянемо один із способів нумерації вершин, який називають способом викреслювання дуг. Для цього вер­шини спочатку розбивають на ранги, а потім нумерують. Розбиття на ранги проводять так. Вершини, в які не за­ходять ніякі дуги, називають вершинами рангу 0. В СГ це – єдина початкова вершина. Після цього викреслю­ють всі дуги, які виходять з вершин рангу 0. Ті вер­шини, в які не заходить, крім цих, жодна дуга, назива­ють вершинами першого рангу. Така вершина знайдеть­ся хоч одна, бо в СГ немає циклів. Далі з усіх вершин першого рангу викреслюють усі дуги, які виходять з них. Вершинам, які мають вхідні дуги лише розглянутих двох видів, присвоюють ранг 2. Через відповідну кількість кроків усі вершини будуть розбиті на ранги. Нумерацію вершин тепер проводять так. Вершині рангу 0 присвоюють номер 0. Потім у довільному по­рядку нумерують усі вершини рангу 1, і т.д.