Алгоритми за дискретна математика
Формулиране на задача
Съществува набор от процеси W , а за всеки процес w от W има набор от неговите предшественици Pw .
Задачата е да се представи този проект под формата на граф, в който дъга се използва за обозначаване на процес, а връх се нарича събитие и установява релация на приоритет.
Освен това графиката трябва да има следните свойства:
- всеки процес е представен от точно една дъга;
- всеки процес се идентифицира с два върха.
Алгоритъм за решаване на задачата
- Съставяме таблица, отразяваща връзката на предходство, във всеки ред от която са записани предшествениците на съответния процес.
- Извършваме транзитивно затваряне на набор от задачи.
- Разделяме множеството от задачи W на групи πα, α∈ A , според следната характеристика: групираме процеси с еднакъв набор от предшественици.
- Нека сега разделим процесите на групи, които еднакво са включени или не са включени в множествата πα. Това ще бъдат групи ρβ, β∈ B , състоящи се от процеси, които заедно влизат или не влизат в съответните набори, или, за нашата таблица, групи от процеси, които се срещат само заедно в редове.
Нека започнем да изграждаме графика.
Свържете с всяко множество πα дял Πα: W = πα∪(W\πα). Разгледайте произведението на съответните дялове Πα и го означете като Π=β>β∈ B . Тогава всяко множество е обединение на някакво множество от множества ρβ, т.е. πα=∪β∈ B (α)ρβ. Така ние номерирахме процесите с индекси β.
- Тогава ако дъгата съответства на процес, то началото на дъгата съответства на индекс от множеството A , а краят – от множеството B .
- Добавяме фиктивни работни места, тоест дъги, съответстващи на двойки (β,α), където началото на дъгата е β∈ B (α), а краят е α∈ A . Тези дъги свързват елемента πα с онези елементи ρβ, на които той е обединение, но водещи от елементите ρβ към елемента πα.
След това се опитваме да опростим получената графика.
- Гледаме през фиктивни дъги. Ако началото и краят на фиктивна дъга са свързани с път, който не съдържа тази дъга, тогава тя може да бъде премахната от графиката.
- Ако някоя фиктивна дъга е единствената дъга, влизаща (или напускаща) връх, тогава тя може да бъде премахната от графиката чрез залепване на нейното начало и край в една точка, тъй като предполагаме, че фиктивната работа има нулева продължителност.
- Построена е желаната графика.