Дискретна математика алгоритми
Формулювання завдання
Є безліч процесів W , і кожного процесу w з W — безліч його попередників Pw .
Завдання полягає у поданні даного проекту у вигляді графа, в якому для позначення процесу використовується дуга, а вершина називається подією та встановлює відношення передування.
Крім цього, граф повинен мати такі властивості:
- кожен процес представимо рівно однією дугою;
- кожен процес ідентифікується двома вершинами.
Алгоритм вирішення поставленого завдання
- Складаємо таблицю, що відбиває відношення попередження, у кожному рядку якої виписані попередники відповідного процесу.
- Виконуємо транзитивне замикання багатьох робіт.
- Безліч робіт W розбиваємо на групи πα, α∈ A за наступною ознакою: групуємо процеси з однаковим набором попередників.
- Тепер роз'єм процеси на групи, що однаково входять або не входять до множини πα. Це будуть групи ρβ, β∈ B , що складаються з процесів, які разом або входять, або не входять у відповідні множини, або, для нашої таблиці, групи процесів, що зустрічаються в рядках тільки разом.
Приступаємо до побудови графа.
Порівняємо кожній множині πα розбиття Πα: W = πα∪(W\πα). Розглянемо твір відповідних розбиття Πα та позначимо його як Π=β>β∈ B . Тоді кожна множина є поєднанням деякого набору множин ρβ, тобто πα=∪β∈ B (α)ρβ. Таким чином ми занумерували процеси індексами β.
- Тоді якщо дуга відповідає процесу, то початку дуги відповідає індекс з множини A, а кінцю - з множини B .
- Додаємо фіктивні роботи, тобто дуги, що відповідають парам (β,α), де початок дуги β∈ B (α), а кінець α∈ A . Ці дуги з'єднують елемент πα з тими елементами ρβ, об'єднання яких він є, але які ведуть від елементів ρβ до елемента πα.
Далі намагаємося спростити отриманий граф.
- Переглядаємо фіктивні дуги. Якщо початок і кінець фіктивної дуги з'єднані шляхом, що не містить цієї дуги, вона може бути видалена з графа.
- Якщо будь-яка фіктивна дуга - єдина дуга, що входить у вершину (виходить з вершини), то вона може бути видалена з графа склеюванням її початку і кінця в одну точку, тому що ми вважаємо, що фіктивна робота має нульову тривалість.
- Шуканий граф побудований.