Задача означення критичного шляху

Будь-яка складна комплексна робота або розробка може бути зображена у виді мережного графіка. Початкова точка S цієї мережі відповідає початку робіт за комплексом, кінцева точка t - закінченню (див. Рисунок9).

Кожна окрема робота комплексу зображується у вигляді дуги, початкова вершина якої відповідає початку роботи, а кінцева - кінцю роботи; кожній дузі (x_ix_j) ставиться у відповідність число t_ij - час виконання роботи, кожній вершині x_i - час t_i настання даної події (початку роботи).

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

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

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

1. Ланка - таке pебро, що не має орієнтації.

2. Дуга - ребро, на якому зазначений напрямок (орієнтир).

3. Петля – ребро, з'єднуюче деяку вершину графа з цією же самою вершиною.

Відповідно розрізняють три типи графів.

1. Неорієнтовані графи, що містять ребро тільки типу ланка.

2. Орієнтовані графи, що містять тільки дуги.

3. Змішані графи, що можуть містити як ланки, так і дуги.

Кажуть, що вершини x_i і x_j суміжні, якщо існує, принаймні, одне ребро, що з'єднує ці 2 вершини. Аналогічно ребра v_i і v_j називаються суміжними, якщо вони мають, принаймні, одну загальну граничну точку. У цьому випадку вершина називається інцидентною ребрам v_i і v_j.

Число ребер, інцидентних даній вершині, називається ступенем вершини.

Маршрутом у графі називається послідовність вершин, що чергується, і ребер

х₁v₁, x₂v₂…,x_nv_n,...

Маршрут є замкнений, якщо х₁ = х_n і відкритий - у противному випадку.

Маршрут називається ланцюгом, якщо всі його ребра різні, і простим ланцюгом, якщо всі вершини (а, отже, і ребра) різні. Замкнений ланцюг називається циклом.

Граф називається зв'язним, якщо будь-яка пара його вершин сполучена ланцюгом.

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

Існує три еквівалентних способи завдання графів: аналітичний, геометричний і матричний.