2.2.5 S-СП и их свойства

Начнем с рассмотрения фундаментального свойства S-СП, которое состоит в том, что все ее достижимые маркировки содержат одно и то же количество фишек.

Утверждение 15  Пусть  N=(S,T,F,M0)S-СП. Далее, пусть M — достижимая в N маркировка. Тогда  M0(S)=M(S).

Доказательство. Так как NS-СП, то срабатывание любого ее перехода удаляет ровно одну фишку из его входного места и добавляет ровно одну фишку в его выходное место. Таким образом, общее число фишек остается постоянным. □

Следующее утверждение будет полезно нам в дальнейшем.

Утверждение 16   Пусть  (N=(S,T.F),M0)сильно связная S-СП. Далее, пусть M и  M'маркировки сети N такие, что  M(S)=M'(S)Тогда  M'  достижима из M.

Доказательство. Будем доказывать индукцией по M(S)

M(S)=M'(S)=0. Очевидно.

M(S)=M'(S)>0. Определим маркировки K, K', L, L' следующим образом: L(S)=1, L'(S)=1 и M=K+L, M'=K'+L'. Тогда K(S)<M(S) и K(S)=K'(S). Применяя индукционную гипотезу, получим, что K' достижима из K. Без потери общности предположим, что K[σ>K'.
Покажем, что L[τ>L' для некоторой последовательности срабатываний τ. Пусть s и s' — места, которые маркируются L и L' соответственно. Так как (S,T.F,M0) — сильно связная S-СП, то существуют путь st1...tns' и последовательность τ=t1...tn такие, что τ удаляет фишку из s и добавляет ее в s'.

Тогда, по лемме 4, имеем следующее:

M=(K+L)[σ>(K'+L)[τ>(K'+L')=M'.

Значит, M' достижима из M.       □

Рассмотрим характеризацию свойства живости S-СП.

Теорема 19  S-СП  (N,M0)  жива, если и только если N — сильно связная сеть и  M0  маркирует по крайней мере одно место.

Доказательство.

(): Предположим, что (N,M0) — живая S-СП. По утверждению 15, имеем, что (N,M0) ограничена. Согласно теореме 13N — сильно связная сеть. Поскольку (N,M0) жива, то по крайней мере один переход может сработать при маркировке M0. Таким образом, M0 маркирует по крайней мере входное место данного перехода.

(): Пусть M — произвольная достижимая маркировка и t — произвольный переход. Покажем, что существует некоторая маркировка, достижимая из M, при которой t может сработать. Поскольку M0 маркирует по крайней мере одно место, по утверждению 15M маркирует по крайней мере некоторое место s. Согласно сильной связности данной сети, существует минимальный путь, ведущий из s в t. Так как NS-сеть, то каждый переход на этом пути имеет одно входное место и одно выходное место, которые являются предшественником и преемником перехода на данном пути. Пусть σ — последовательность переходов (кроме t), содержащихся в этом пути. Тогда имеем, что M[σ>M' для некоторой маркировки M', которая маркирует по крайней мере одной фишкой входное место перехода t. Вновь так как NS-сеть, то t имеет ровно одно входное место. Следовательно, t может сработать при M'. □

Теперь рассмотрим характеризацию свойства достижимости живых S-СП.

Теорема 20   Пусть  N=(N,M0)живая S-СП и M — ее маркировка. Тогда M — достижимая в N маркировка, если и только если  M0(S)=M(S).

Доказательство.

(): Следует из утверждения 15.

(): Согласно теореме 19N — сильно связная сеть. Результат следует из утверждения 16. □

Теперь рассмотрим харарктеризацию свойства k-ограниченности живых S СП.

Теорема 21  Живая S-СП  (N=(S,T.F),M0)  k-ограничена, если и только если  M0(S)k.

Доказательство.

(): Пусть s — место и M — маркировка в N такие, что M(s)=M(S)=M0(S). Согласно теореме 19N — сильно связная сеть. По утверждению 16, M достижима из M0. Так как (N,M0)k-ограничена, то M(s)k. Следовательно, верно, что M0(S)k.

(): Согласно утверждению 15, имеем, что M(S)=M0(S) для любой достижимой в (N,M0) маркировки M. Так как M(s)M0(S) для каждого места s и M0(S)k, по предположению, то (N,M0)k-ограничена. □