266 Т(к) !т т T(qi) T(q2) т ▼ Т У Т Т(чи) Т (ч,,) T(q2.) T(q22) T fe) Рис. 5.2. Дерево базовых проектов Определим но множестве В отношение <=>, отражающее связь проектов по потреблению: для X=(q,R), Y=(s,L) отношение X ^Y означает, что существует такая услуга pcR, что q out(p) и либо р—>s, либо p-»h, где h некоторая услуга, удовлетворяющий условию pred(h) = s. Иначе говоря, отношение X ^Y означает, что некоторая услуга проекта X, для которого платформа q является выпускающей, потребляется либо платформой s проекта Y, либо некоторой услугой h, производимой непосредственно на платформе s. Отношение X ^Y отражается дугой-прошивкой, идущей от узла X к узлу Y. Полученный граф назовем графом базовых проектов Кв. Граф Кв есть дополненное прошивками дерево Тв, к которому подвязаны услуги проектов с пустыми платформами. Ясно, что этот граф однозначно определяется распределительным графом К и назначенными (возможно) платформами некоторых узлов (рис. 5.3). Рассмотрим граф Д, который получается из графа Кв сменой ориентации ребер дерева Тв; ориентация прошивок сохраняется (рис. 5.4). Это означает, что любая дуга «модифицированного» дерева Тв идет от узла-проекта T(q) к ближайшему, минимальному узлу-проекту T(s), для которого T(q) является подпроектом. Будем считать, что граф Д ацикличен, т.е. в нем нет (ориентированных) циклов наличие циклов в этом графе является показателем некорректности модели. |
Т(к) Рис. 3.2. Дерево базовых проектов Расширим понятие базового проекта, отнеся к таковым все простые проекты с пустой выпускающей платформой, т.е проекты вида (Л,р). Включим эти проекты во множество В, не распространяя на них отношение частичного упорядочения; следовательно, расширение множества В не изменяет дерева Тв. Определим во множестве В отношение *=>, отражающее связь проектов по потреблению: для X=(q,R), Y=(s,L) отношение X ^Y означает, что сущеФ ствует такой продукт peR, что q = out(p) и либо p->s, либо р—>h, где h некоторый продукт, удовлетворяющий условию pred(h) = s. Иначе говоря, отношение X ^Y означает, что некоторый продукт проекта X, для которого платформа q является выпускающей, потребляется либо платформой s проекта Y, либо некоторым продуктом h, производимым непосредственно на платформе s. Отношение X=>Y отражается дугой-прошивкой, идущей от узла X к узлу Y. Полученный граф назовем графом базовых проектов Кв. Граф Кв есть дополненное прошивками дерево Тв, к которому подвязаны продукты проектов с пустыми платформами. Ясно, что этот граф однозначно опре# деляется калькуляционным графом К и назначенными (возможно) платформами некоторых узлов (см. рис. 3.3). 7 0 Т(к) ▼ ▼ 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 |