Більшість завдань розглянутих із застосуванням графів вимагають моделей, в яких у кожного ребра необхідно враховувати одну або кілька властивостей. Приписування кожному ребру графа якогось властивості, що має однаковий для всіх ребер семантичний сенс, називається зважуванням графа. Значення цієї властивості для кожного з ребер (постійне або одержуваного виконанням якогось певного функціоналу) називається вагою ребра.
Як приклад розглянемо транспортну задачу (Малюнок 2.1 -4), в якій об'єкту знаходиться в вершині v1 потрібно за мінімальний час досягти вершини v6.
Малюнок 2.1-4. Приклад навантаженого графа
Завдання неможливо вирішити не знаючи час, за яке об'єкт в стані долати кожне з ребер графа. Довизначити вихідні дані і поставимо в якості ваги час подолання ребра. На графі призначені ваги приведені поруч з кожним з ребер через символ "/", так e3 / 5 означає що ребро e3 долається за 5, припустимо, хвилин. Тепер, після деякого роздуми, перебравши всі чотири можливі шляхи з v1 у v6, можна сказати що найкоротшим (за часом) способом пересування з v1 у v6 є шлях Pmin (v1, v6) = e1, e3, e4, e5>.
Якщо трохи ускладнити тільки що розглянуту задачу і вимагати визначення оптимального за часом маршруту для довільного об'єкта з відомою швидкістю, то очевидно що в графовой моделі доведеться замінити вага - час подолання ребра на вагу - довжина ребра (наприклад, в кілометрах), тому що кожен з об'єктів буде проходити ребра за різний час. На тій же топології (відносинах між вершинами) графа, використовуючи інше властивості ребра (іншу вагу) ми отримаємо вже відмінну від першої модель.
Часто використовують призначення декількох ваг. Так, якщо в попередній задачі враховувати наявність світлофорів і вважати що кожен світлофор на маршруті подовжує його, скажімо на 1 хвилину, то доведеться використовувати модель з двома вагами, першим з яких буде довжина ребра, а другим - кількість світлофорів.
Ліпимо пельмені - будуємо граф
Спробуємо зрозуміти чому апарат графів виявився зручний при описі моделі проекту. Для цього розглянемо іграшковий за масштабами, але цілком реальний проект.
Сформулюємо мета проекту: "Приготувати домашні пельмені" і спробуємо відповісти на одне з перших питань стадії планування проекту - яка ж тривалість проекту. В якості вступної додамо, що:
з метою спрощення будемо вважати наші ресурси (руки, фінанси і обладнання) необмеженими,
обсяг проекту (кількість результуючих пельменів) фіксований.
Відповісти на питання про тривалість проекту можна тільки лише представивши технологію його реалізації, для чого потрібно відповісти на наступні питання:
з яких частин (підпроектів, фаз, робіт) складається проект,
яка тривалість кожної з частин,
які технологічні обмеження накладені на послідовність виконання робіт.
Звідки можна почерпнути відповіді на ці питання? Тільки з опита.Своего (майбутня сотня пельменів не перша зліплена в нашому житті) або чужого (кулінарна книга). Спробуємо відповісти послідовно на ці три питання в умовах обраного проекту.
Виділимо окремі роботи, які необхідно виконати в рамках проекту (цей процес називається декомпозицією цілей). Отже, для того щоб "приготувати домашні пельмені" необхідно:
Купити яловичину, свинину, борошно, сіль, перець, олія, молоко, цибулю, часник.
Замісити тісто і дати йому відстоятися.
Почистити цибулю і часник.
Пропустити через м'ясорубку м'ясо з часником, цибулею.
Додати до фаршу перець, сіль і молоко.
Нарізати тісто на шматки.
Відкладемо до розділу. питання чому саме ці роботи виділені (тобто чому саме так проведена декомпозиція цілей) і займемося оцінкою тривалості робіт. Будемо тепер використовувати для позначення робіт вже сформований в попередньому списку індекс роботи у вигляді заголовного латинського символу. Отже: A - 45 (хвилин), B - 5, C - 45, D - 4, E - 5, F - 10, G - 2, H - 4, I - 10, J - 15, K - 40, L - 12.І тут залишимо на подальший розгляд питання типу "Чому ліплення пельменів займає 40 хвилин, хоча кількість робочих рук необмежено?".
Приступимо тепер до відповіді на третє питання "Які технологічні обмеження накладені на послідовність виконання робіт?". І що таке взагалі технологічні обмеження? Перш за все це обмеження на послідовність будь-якої пари робіт. Наприклад, не можна почати зводити стіни будівлі не побудувавши фундамент. Можна і складніше - не можна почати зводити стіни будівлі перш ніж не пройде три дні з моменту заливки бетону в фундамент (три дні бетон повинен "схоплюватися"). У нашому проекті ці обмеження послідовностей виглядають наступним чином:
не виконавши роботу A (закупівля продуктів) не можна почати жодну з інших робіт,
роботу C (місити тісто) можна почати тільки після закінчення роботи B (просіювання борошна),
робота F (м'ясорубка) може бути почата тільки після робіт D (миття м'ясо) і E (чистка овочів).
роботу G (додавання спецій до фаршу) можна почати тільки після закінчення роботи F (м'ясорубка) і лише закінчивши роботу G можна почати Н (місити фарш),
роботи I (розрізання тесту) і J (розкочування тіста) будемо виконувати послідовно і I можна виконувати лише після того як тісто буде готове (робота С),
ліпити пельмені (робота K) почнемо лише після того як готовий фарш (робота Н) і коржі розгорнуті (J), а варити (робота L) - після того як пельмені зліплені (K).
Настільки значний перелік обмежень, який можна порівняти за довжиною з переліком самих робіт, характерний для проектів будь-якого рівня.
Зауважимо тут, що ще не всі умови наведені вище. Наприклад, не перераховано цілком логічне умова: "Робота I (розрізання тесту) не може бути розпочато до закінчення роботи B (просіювання борошна)". Пояснюється ця обставина тим, що воно є зайвим при наявності двох вище сформульованих умов: "C після B" і "I після С". Беручи це зауваження до уваги, формулюємо тепер перше з вище перерахованих умов передування "не виконавши роботу A (закупівля продуктів) не можна почати жодну з інших робіт" як ряд умов: "B після A", "C після A", "D після A ", і т.д. і з цього ряду викинемо зайві, залишивши тільки три: "B після A", "D після A", "E після A".
Обмеження передування сформульовані. Як же представити їх в моделі проекту? Тут то і приходить на допомогу апарат графів. Як вже зазначалося у вступі до розділу 2.1, граф являє універсальне і має графічну інтерпретацію засобів представлення відносин між об'єктами. Конкурентні форми подань - матричні або спискові простого наочного графічного уявлення не мають.
Отже, уявімо модель проекту з приготування пельменів у вигляді графа. Граф є пара множин: вершини і ребра. Що ж для моделі проекту є вершиною і що ребром? Історично, з методів перерахованих на початку цього розділу, було прийнято в якості ребер графа брати роботи, а в якості вершин - події, які полягають в початку або закінчення однієї або декількох робіт (альтернативний підхід розглянутий у наступному підрозділі). Спробуємо побудувати такий граф, почавши з однієї роботи A.
Малюнок 2.1-5. Подання одиничної роботи на графі проекту.
Ребро графа (Малюнок 2.1 -5) позначає роботу A. Вершина графа ідентифікована цифрою 1 означає подія знаменує собою початок роботи A. а вершина 2 - закінчення роботи A. Граф орієнтований, бо роботи (ребра) виконуються в часі і, отже, початок і кінець ребра визначені. Граф є зваженим і в якості ваги виступає тривалість роботи. Вага проставлений на зображенні графа поруч з ідентифікатором роботи.
Додамо до вищенаведеного графу роботи B. З і D. які по сформульованим нами обмеженням передування можуть початися після закінчення роботи A. Це дасть нам можливість подивитися як обмеження передування знаходять відображення на графі.
Малюнок 2.1-6. Відображення залежностей передування на графі проекту.
Переформулюємо відношення "робота T2 може початися тільки після закінчення роботи T1" в термінах графів. Отримаємо: ребра T2 і T1 суміжні, при цьому для їх загальної вершини ребро T1 є вхідним, а ребро T2 - виходить. Звідси і отримане зображення графа (Малюнок 2.1 -6).
Побудуємо тепер весь граф, що відображає модель проекту виготовлення пельменів.
Малюнок 2.1-7. Повний граф проекту виготовлення пельменів.
Залишимо на час відкритим питання про те скільки часу займе виготовлення пельменів і перейдемо до моделей використовується в управлінні проектом.