52. Сети Петри: определение, структура, способы задания.

Определение 1:

Обычной сетью Петри называется конечный двудольный ориентированный граф <V, E>, где V = P  T, P  T =  — разбиение множества вершин, E  (PT)  (TP) – отношение инцидентности вершин.

Определение 2:

Сеть Петри N является четверкой N = (P, Т, I, O), где

• P={p₁, p₂, ..., p_n} — конечное множество позиций, n0;

• T={t₁, t₂,...,t_m} — конечное множество переходов, m0;

• I: T  P^ — входная функция, сопоставляющая переходу мультимножество его входных позиций;

• О: T  P^ — выходная функция, сопоставляющая переходу мультимножество его выходных позиций.

Позиция pP называется входом для перехода tT, если pI(t). Позиция pP называется выходом для перехода tT, если pO(t). Структура сети Петри определяется ее позициями, переходами, входной и выходной функциями.

Способы представления сети Петри:

1) Перечисление элементов множеств позиций, переходов, перечисление элементов комплектов входной и выходной функций. Пример:

N =(P, T, I, O),

P={p₁, p₂, p₃},

T={t₁, t₂},

I(t₁)={ p₁, p₁, p₂}, O(t₁)={p₃},

I(t₂)={ p₁, p₂, p₂}, O(t₁₂)={p₃}.

2) Наиболее наглядным представлением сети Петри является её графическое представление, которое представляет собой двудольный, ориентированный мультиграф.

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

Пример: