|
других петель, и что каждый узел можно достичь из любого другого узла. Собственную петлю можно рассматривать как вырожденную петлю первого порядка. Петля порядка п множество п не связанных между собой петель первого порядка. Замкнутый потоковый граф граф, в котором каждая ве гвь принадлежит, по крайней мере, одной петле. Отметим, что потоковый граф является замкнутым, поскольку он целиком состоит из петель. Петлю первого порядка можно рассматривать как цепь, состоящую из последовательно соединенных ориентированных ветвей, концевые узлы которой совпадают. Поэтому коэффициент пропускания эквивалентного ей потокового графа равен произведению коэффициентов пропускания каждой ветви. Пусть Lп, 12ь —, 1п\ — п не связанных между собой петель первого порядка заданной петли порядка п. Для каждой петли Lк\ первого порядка эквивалентный коэффициент пропускания 7* равен произведению коэффициентов пропускания ветвей, принадлежащих этой петле, т. е. UJW'II Следовательно, для петли порядка п эквивалентный коэффициент пропускания T(LД равен Основной результат (3.5) используется для определения стохастического поведения распределенных алгоритмов, которые могут быть описаны ГЕРТ-сетями. Цель использования системы ГЕРТ в стохастическом сетевом анализе алгоритмов и программ состоит в вычислении математического ожидания и дисперсии времени выполнения сети (которые рассматриваются здесь как общий параметр сети) и вероятности выполнения стока (или стоков). Очевидно, что коэффициент пропускания дуги ГЕРТ-сети есть соответствующая ^-функция. Напомним, что IP-функция дуги определяется (3.4) п п ш „ ) = т = п г к • (3.5) 107 |
указывает связь по входу и выходу между двумя переменными, представленными узлами этой ветви. Узел i соответствует независимой переменной xit а узел j — независимой переменной хр Параметр ty обычно называют коэффициентом пропускания дуги. Он равен множителю, используемому для того, чтобы преобразовать величину х,до рассмотрения ее как части величины xj. Основное свойство потоковых графов заключается в том, что величина узла равна сумме преобразованных величин узлов, соединенных с рассматриваемым узлом входящими в него дугами. Основные свойства потоковых графов могут быть использованы для разработки методов, позволяющих обращаться непосредственно с элементами графа, в результате чего он будет преобразован в эквивалентный граф с более простой структурой и, следовательно, упростится, решение задачи. Наиболее известным результатом в данной области является топологическое уравнение Мейсона, которое может быть использовано для потоковых графов с произвольной структурой. Для рассмотрения уравнения Мейсона введем следующие определения. Петля связная последовательность ориентированных ветвей, каждый узел которых является общим ровно для двух ветвей. Петлю обычно называют петлей первого порядка, чтобы указать на то, что она не содержит других петель, и что каждый узел можно достичь из любого другого узла. Собственную петлю можно рассматривать как вырожденную петлю первого порядка. Петля порядка п множество п не связанных между собой петель первого порядка. Замкнутый потоковый граф граф, в котором каждая ветвь принадлежит, по крайней мере, одной петле. Отметим, что потоковый граф является замкнутым, поскольку он целиком состоит из петель. Петлю первого порядка можно рассматривать как цепь, состоящую из последовательно соединенных ориентированных ветвей, концевые узлы которой совпадают. Поэтому коэффициент пропускания эквивалентного ей потокового графа равен произведению коэффициентов пропускания каждой ветви. 115 Пусть Zn, Z21, L„x — n не связанных между собой петель первого порядка заданной петли порядка п. Для каждой петли Lki первого порядка эквивалентный коэффициент пропускания 7* равен произведению коэффициентов пропускания ветвей, принадлежащих этой петле, т. е. ГК(3.2.5) Следовательно, для петли порядка п эквивалентный коэффициент пропускания T(L„) равен щ-„)=гк=п к=1 £=1 11*У (3.2.6) Основной результат (3.2.6) используется для определения стохастического поведения распределенных алгоритмов, которые могут быть описаны GERT-сетями. Цель использования системы GERT в стохастическом сетевом анализе алгоритмов и программ состоит в вычислении математического ожидания и дисперсии времени выполнения сети (которые рассматриваются здесь как общий параметр сети) и вероятности выполнения стока (или стоков). Очевидно, что коэффициент пропускания дуги GERT-сети есть соответствующая Ж-функция. Напомним, что Ж-функция дуги определяется как произведение вероятности выполнения этой дуги и производящей функции моментов для времени выполнения операции, представленной этой дугой. В предыдущем, разделе мы показали, как определить все петли замкнутого потокового графа. Для того чтобы применить эти результаты к открытой сети, необходимо ввести дополнительную дугу с Ж-функцией ^(s), соединяющую сток t с источником 5. Затем для модифицированной сети нужно найти все петли (вплоть до максимально возможного порядка). Функция Wa(s) необходима для того, чтобы найти эквивалентную PF-функцию для исходной сети. На рис. 3.2.2 исходная сеть изображена в виде «черного ящика» с Ж-функцией WE(s). 116 |