Page 87 - 4496

виконання всієї роботи (R o–загальний резерв) або на умови
виконання наступних робіт (R св–вільний резерв). Для робіт на
критичному шляху резерви часу дорівнюють нулю.
Для розглянутого прикладу можна визначити, що
виконання роботи, зіставленій дузі (5,8), можна затримати на
8 одиниць або збільшити на цю величину, і загальний час
виконання роботи залишиться колишнім. Тут максимальний
шлях від вершини 8 до кінцевої рівний 18, від початкової
вершини до вершини 5 рівний 8, час виконання роботи (5,8)
рівний 3. Виходить, максимальний шлях через цю дугу рівний
18+8+3=29, що на 8 менше критичного.
Більш складним завданням є завдання скорочення
загального часу виконання роботи, якщо можливе частину
роботи передати із критичного шляху на некритичний. Якщо
вага дуги на критичному шляху може бути зменшена за
рахунок збільшення ваги дуги, що не належить критичному
шляху (робота «передана» іншим виконавцям), то як за
рахунок цього зменшити загальний строк виконання роботи?
Цю й ряд інших спеціальних завдань розглядати не будемо.

13.15 Дерева
Визначення.
Неорієнтованим деревом називають граф, що
задовольняє одній з умов:
 зв'язний граф без циклів;
 зв'язний граф з n вершин і (n-1) ребра;
 граф, у якому будь-які дві вершини пов'язані рівно
одним ланцюгом.
Завдання. Доведіть, що всі три умови описують той
самий об'єкт і що з того, що граф має одну із цих
властивостей, випливають два інших.
Орієнтованим деревом називають зв'язний граф, у
якому в кожну вершину, крім однієї, названу коренем дерева,
заходить рівно одна дуга. У корінь дерева жодна дуга не
заходить.
Вершини, з яких не виходить жодна дуга, називаються
листами.
Завдання. Покажіть, що якщо орієнтованому дереву
зіставити неорграф, одержимо неорієнтоване дерево.
84