47. Сети Петри. Функционирование сети Петри. Конечные разметки сети.

Графы специального вида, получившие в дальнейшем название «Сети Петри» были впервые введены Карлом Петри в 60-х годах.

Основой сети Петри является понятие условно-событийной системы. Компоненты системы и их действия представляются абстрактными событиями. Совокупность действий, возникающих как реализация событий при функционировании системы, образует процесс, порождаемый этой системой. Для того, чтобы событие произошло, необходимо появление ситуации, в которой это событие может быть реализовано. При этом ситуация определяется как совокупность некоторых условий возникновения события.

Сеть Петри — набор N = (P, T, F, W, M0 ), где (P, T, F) — конечная сеть (множество Х = P È T конечно), а W: F ® N и M0: P ® N0 — две функции, называемые кратностью дуг и начальной пометкой. Первая ставит в соответствие каждой дуге число N > 0 (кратность дуги). Если N > 0, то при графическом представлении сети число N выписывается рядом с короткой чертой, пересекающей дугу. Дуги с кратностью 1 не помечаются. Каждой позиции p Î P ставится в соответствие некоторое число M0 (p) Î N0 (пометка позиции).

Функционирование сети Петри описывается формально с помощью множества последовательностей срабатываний и множества достижимых в сети разметок. Эти понятия определяются через правила срабатывания переходов сети.

Сеть Петри определяется как двудольный граф. Т.е. все вершины графа относятся к одному из двух классов — позициям (местам, places) и переходам (bridge). Позиции изображаются окружностями, переходы — отрезками прямой. Дуги в сетях Петри — направленные. Причем каждая дуга связывает вершины только разных классов. Либо начало дуги совпадает с позицией и тогда конец этой дуги совпадает с переходом, либо наоборот.

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

Примеры:

Недопустимые примеры

Разметка сети

Оригинальным понятием теории сетей Петри является понятие «фишка» (маркер, token). Фишки изображаются точками, расположенными внутри позиций. Таким образом, каждой позиции сети ставится в соответствие натуральное число, указывающее количество фишек в данной позиции. Это число называют разметкой позиции, а совокупность таких чисел для всех позиций сети называют разметкой сети. Позиция может и не содержать фишек, т.е. иметь нулевую разметку

Срабатывание перехода

Назовем входными позициями некоторого конкретного перехода те позиции, из которых исходят дуги, входящие в данный переход. Соответственно, выходными позициями назовем позиции, в которые входят дуги, исходящие из данного перехода.

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

Условие срабатывания перехода

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

Как только введено понятие «срабатывание» перехода — появляется возможность говорить о функционировании сети и моделировании процессов, этапы которых связаны между собой причинно-следственной связью.