21. Дайте определение сетевой модели (n-схемы), укажите основные соотношения сети Петри

В практике моделирования объектов часто приходится решать задачи, связанные с формализованным описанием и анализом причинно следственных связей в сложных системах, где одновременно параллельно протекает несколько процессов.

Теория сетей Петри развивается в нескольких направлениях: разработка математических основ, структурная теория сетей, различные приложения (параллельное программирование, дискретные динамические системы и т. д.).

Сеть Петри состоит из 4 компонентов, которые и определяют ее структуру:

- множество позиций Р,

- множество переходов Т,

- входная функция I,

- выходная функция О.

Входная и выходная функции связаны с переходами и позициями. Входная функция I отображает переход t_j в множество позиций I(t_j), называемых входными позициями перехода. Выходная функция О отображает переход t_j в множество позиций О(t_j), называемых выходными позициями перехода. Т.е.

( I : T -> P^) (O : T -> P^).

Определение 1. Сеть Петри С является четверкой С = (P,T,I,O) где

Р={p1,p2,...,p_n} конечное множество позиций, n>=0.

T={t1,t2,...,t_m} конечное множество переходов, m>=0.

Множества позиций и переходов не пересекаются.

I : T -> P^ является входной функцией - отображением из переходов в комплекты позиций.

O : T -> P^ выходная функция - отображение из переходов в комплекты позиций.

Мощность множества Р есть число n, а мощность множества Т есть число m. Произвольный элемент Р обозначается символом p_i, i=1...n; а произвольный элемент Т - символом t_j, j=1...m.

рис. 1

Позиция p_i является входной позицией перехода t_j, в том случае, если p_i  I(t_j);

p_i является выходной позицией перехода, если pi  O(t_j).

рис. 2

Входы и выходы переходов представляют комплекты позиций. Кратность входной позиции для перехода t_j есть число появлений позиции во входном комплекте перехода #(p_i,I(t_j)). Аналогично, кратность выходной позиции p_i для перехода t_j есть число появлений позиции в выходном комплекте перехода #(p_i,O(t_j)).

Определим, что переход t_j является входом позиции p_i, если p_i есть выход t_j (рис. 2). Переход t_j есть выход позиции p_i, если p_i есть вход t_j (рис. 1).

Графически N-схема изображается в виде двудольного ориентированного

мультиграфа, представляющего собой совокупность позиций и переходов

(рис. 2.8). Как видно из этого рисунка, граф N-схемы имеет два типа узлов:

позиции и переходы, изображаемые 0 и 1 соответственно.

Ориентировочные дуги соединяют позиции и переходы, причем каждая дуга направлена от элемента одного множества (позиции или перехода) к элементу другого множества (переходу или позиции). Граф N-схемы является мультиграфом, так как он допускает существование кратных дуг от одной вершины к другой.

Рис. 28. Графическое изображение