Проверяемый текст
Джиоева, Наталья Николаевна. Многокомпонентная сетевая модель формирования алгоритмов распределенной обработки и управления в АСУ (Диссертация 2004)
[стр. 105]

При использовании системы ГЕРТ необходимо учитывать основные положения и аппарат теории потоковых графов.
Для нас существенно, что процесс может быть определен как совокупность активных взаимодействующих между собой элементов, которые выполняют некоторые функции.
Для графического описания таких систем наиболее широко используются потоковые графы.
В потоковом графе элементы системы представляются узлами, а взаимосвязь между элементами, или функции перехода, — дугами.
Основным элементом потокового графа является ориентированная ветвь, направленная из узла /
в узел у, с параметром ty.
Направление ветви
указывает связь по входу и выходу между двумя переменными, представленными узлами этой ветви.
Узел /
соответствует независимой переменной л,, а узел у — независимой переменной ху Параметр /у обычно называют коэффициентом пропускания дуги.
Он равен множителю, используемому для того, чтобы преобразовать величину х,до рассмотрения ее как части величины Xj.
Основное свойство потоковых графов заключается в том, что величина узла равна сумме преобразованных величин узлов, соединенных с рассматриваемым узлом входящими в него дугами.
Основные свойства потоковых
1рафов могут быть использованы для разработки методов, позволяющих обращаться непосредственно с элементами графа, в результате чего он будет преобразован в эквивалентный граф с более простой структурой и, следовательно, упростится решение задачи.
Наиболее известным результатом в данной области является топологическое уравнение Мейсона, которое может быть использовано для потоковых графов с произвольной структурой.
Для рассмотрения уравнения Мейсона введем следующие определения.
Петля связная последовательность ориентированных ветвей, каждый узел которых является общим ровно для двух ветвей.
Петлю обычно называют петлей первого порядка, чтобы указать на то, что она не содержит
106
[стр. 114]

эквивалентной дуге, а затем эти дуги преобразовать в сеть, состоящую из одной ветви, эквивалентную исходной системе.
Пусть (/, у) — ветвь, эквивалентная сети.
Из (3.2.2) и (3.2.3) следует; что вес ветви (z,y) равен Wy = Wb + WaWb + Wa 2Wb + ...
= 1ГЬ[1+ ].
/77 — 1 Данное выражение, в котором мы временно опустили аргументы FT-функций, можно упростить, зная, что биномиальный ряд (1—WJ'1 раскладывается следующим образом: (1 1¥аУ{ = 1 + Wa + W% + +...
= 1 + Таким образом, окончательно имеем ^.(5) = Wb (s)[l Wa (Л)Г' = Wb (s)/[l FF„(s)] .
(3.2.4) Следовательно, сеть сводится к одной единственной эквивалентной ей ветви, для которой W-функция равна й^(^) = fPb(s)/[ 1—f^a(s)].
Отметим, что описанная процедура может быть использована и для контуров, поскольку с помощью формулы (3.2.2) контур сводится к петле.
Таким образом, если GERT-сеть состоит из параллельных и последовательных цепей и (или) петель, то она может быть преобразована в эквивалентную сеть, состоящую из одной единственной ветви.
На самом деле, данный результат обобщается на любую GERT-сеть, поскольку можно комбинировать базисные преобразования.
При использовании системы GERT необходимо учитывать основные положения и аппарат теории потоковых графов.
Для нас существенно, что процесс может быть определен как совокупность активных взаимодействующих между собой элементов, которые выполняют некоторые функции.
Для графического описания таких систем наиболее широко используются потоковые графы.
В потоковом графе элементы системы представляются узлами, а взаимосвязь между элементами, или функции перехода, — дугами.
Основным элементом потокового графа является ориентированная ветвь, направленная из узла
i в узел у, с параметром ty.
Направление ветви
114

[стр.,115]

указывает связь по входу и выходу между двумя переменными, представленными узлами этой ветви.
Узел
i соответствует независимой переменной xit а узел j — независимой переменной хр Параметр ty обычно называют коэффициентом пропускания дуги.
Он равен множителю, используемому для того, чтобы преобразовать величину х,до рассмотрения ее как части величины xj.
Основное свойство потоковых графов заключается в том, что величина узла равна сумме преобразованных величин узлов, соединенных с рассматриваемым узлом входящими в него дугами.
Основные свойства потоковых
графов могут быть использованы для разработки методов, позволяющих обращаться непосредственно с элементами графа, в результате чего он будет преобразован в эквивалентный граф с более простой структурой и, следовательно, упростится, решение задачи.
Наиболее известным результатом в данной области является топологическое уравнение Мейсона, которое может быть использовано для потоковых графов с произвольной структурой.
Для рассмотрения уравнения Мейсона введем следующие определения.
Петля связная последовательность ориентированных ветвей, каждый узел которых является общим ровно для двух ветвей.
Петлю обычно называют петлей первого порядка, чтобы указать на то, что она не содержит
других петель, и что каждый узел можно достичь из любого другого узла.
Собственную петлю можно рассматривать как вырожденную петлю первого порядка.
Петля порядка п множество п не связанных между собой петель первого порядка.
Замкнутый потоковый граф граф, в котором каждая ветвь принадлежит, по крайней мере, одной петле.
Отметим, что потоковый граф является замкнутым, поскольку он целиком состоит из петель.
Петлю первого порядка можно рассматривать как цепь, состоящую из последовательно соединенных ориентированных ветвей, концевые узлы которой совпадают.
Поэтому коэффициент пропускания эквивалентного ей потокового графа равен произведению коэффициентов пропускания каждой ветви.
115

[Back]