|
167 Т ( к ) T(q,) " I I ::: тш E 6s ▼ 'г ^r ▼ 1r si/ T (q n ) Т(Чп) j !: T(q21) T(q22) T(q23) Л А Рис. 5.3. Граф базовых проектов Известно, что ациклический граф допускает топологическую сортировку, т.е. такую нумерацию узлов, что у любой дуги графа номер начала меньше номера конца. На рис. 5.5 приведен пример топологической сортировки узлов графа А, представленного на рис. 5.4. Топологическая сортировка узлов графа А порождает следующую схему перераспределения: ■ топологическая сортировка определяет порядок обработки базовых проектов; |
Т(к) ▼ ▼ T(qi) Ш ) eg ▼ T(qn) ▼ Т Ы т T(q2i) т т ы т * т ы У4 'v' / \ Рис. 3.3. Граф базовых проектов Рассмотрим граф Д, который получается из графа Кв сменой ориентации ребер дерева Тв; ориентация прошивок сохраняется (см. рис. 3.4). Это означает, что любая дуга «модифицированного» дерева Тв идет от узлапроекта T(q) к ближайшему, минимальному узлу-проекту T(s), для которого T(q) является подпроектом. Будем считать, что граф А ацикличен, т.е. в нем нет (ориентированных) циклов наличие циклов в этом графе является пока4 зателем некорректности модели. Т(к) i1 T(qi) T(q2) T(q„) л T(q,2) Л " " т ы 1 л т ы т ы Рис. 3.4. Граф Д Известно, что ациклический граф допускает топологическую сортировку, т.е. такую нумерацию узлов, что у любой дуги графа номер начала меньше номера конца. На рис. 3.5 приведен пример топологической сортировки узлов графа Д, представленного на рис. 3.4. 7 1 |