Начнем с того, что покажем, что понятие цикла (см. Определение 2) в сети играет важную роль в теории T-СП.

Пусть γ — цикл и M — маркировка в сети. Далее, пусть R — множество мест в цикле γ. Количество фишек M(γ) в цикле γ при маркировке M определяется как M(R). Будем говорить, что цикл γ маркируется маркировкой M, если M(γ)>0; γ изначально маркирован, если γ маркируется начальной маркировкой M0.

Рассмотрим фундаментальное свойство T-СП — количество фишек в любом цикле остается постоянным при любом функционировании T-СП.

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

Доказательство. Пусть t — переход.

Если t не принадлежит циклу γ, то срабатывание t не изменяет количество фишек в любом месте цикла γ, поскольку (N,M0) является T-СП.

Если t принадлежит циклу γ, то ровно одно входное место и одно выходное место перхода t принадлежит γ. Тогда срабатывание t удаляет одну фишку из одного места в γ и добавляет одну фишку в одно место в γ (эти два места могут быть одним и тем же).

Таким образом, в обоих случаях количество фишек в местах цикла γ не меняется. □

Свойство живости T -СП характеризуется следующей теоремой.

Теорема 22  T-СП  (N,M0)  жива, если и только если каждый ее цикл изначально маркирован.

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

(): Предположим, что некоторый цикл не является изначально маркированным. Согласно утверждению 17, этот цикл немаркируется ни одной достижимой в (N,M0) маркировкой. По определению цикла и отношения F, цикл содержит по крайней мере один переход t. Тогда t не может сработать ни при одной достижимой маркировке. Таким образом, (N,M0) не жива.

(): Пусть t — переход и M — достижимая маркировка в (N,M0). Покажем, что t может сработать при некоторой маркировке, достижимой из M.

Определим множество SM мест следующим образом: sSM, если существует путь из s в t, который не содержит мест, которые маркируются M. Будем доказывать индукцией по |SM|.

|SM|=0. Тогда каждое входное место перехода t маркируется M, и следовательно, t может сработать при M.

|SM|>0. Тогда t не может сработать при M. По предположению, каждый цикл (N,M0) изначально маркирован. Согласно утверждению 17, каждый цикл маркируется M. Поэтому существует путь π максимальной длины, который не содержит мест, которые маркируются M, и который ведет к переходу t. Пусть u — первый элемент в π. Согласно максимальности, πu — переход и все входные места u маркируются M. Тогда u может сработать при M. Заметим, что ut, поскольку t не может сработать при M. Пусть M[u>M'. Для того, чтобы применить индукционную гипотезу, покажем, что SM' — собственное подмножество множества SM.

SM'SM. Пусть sSM'. Тогда существует путь π'=s...t, который не содержит мест, которые маркируются M', Покажем, что π' не содержит мест, которыеи маркируются M, что означает sSM. Предположим обратное, т.е. некоторое место r пути π' маркируется M. Так как r не маркируется M' и M[u>M', то u — выходной переход места r. Поскольку NT-сеть, то u — единственный выходной переход места r и, следовательно, его преемник на пути π'. Далее, так как ut, некоторое выходное место перехода u содержится в π'. Тогда это место маркируется M', что противоречит определению π'.

SM'SM. Пусть s — преемник перехода u на пути π. Так как все места в π принадлежат множеству SM, имеем, что sSM. Поскольку срабатывание перехода u добавляет фишку в место s, то верно, что M'(s)>0. Значит, имеем, что sSM'.

По индукционной гипотезе, существует последовательность срабатываний σ такая, что M'[σ>M'' и t может сработать при M''. Так как M[u>M', маркировка M'' достижима из маркировки M. Результат доказан. □

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

Свойство k-ограниченности живых T-СП характеризуется следующей теоремой.

Теорема 23   Живая T-СП  N=(N=(S,T.F),M0))  k-ограничена, если и только если для каждого места  sS существует цикл  γкоторый содержит  s  и верно, что  M0(s)k.

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

(): Пусть sS. Так как Nk-ограничена, то граница места s, т.е. максимальное количество фишек в s, меньше или равна k. Пусть M — достижимая в N маркировка такая, что M(s) равна границе места s. Определим маркировку L в N следующим образом:

L(r)=M(r),rs0,r=s

Покажем, что (N,L) не является живой. Предположим обратное. Так как живость влечет S-живость, согласно утвеждению 4, то существует последовательность срабатываний σ такая, что L[σ>L' и L'(s)>0. Поскольку ML, то M[σ>, согласно лемме 4. Пусть M[σ>M'. Так как L(s)=0, имеем, что M'(s)=L'(s)+M(s)>M(s), что противоречит предположению о том, что M(s) равно границе места s. Значит, (N,L) не является живой. Тогда, согласно теореме 22, существует цикл γ, который не маркируется L. Поскольку (N,M) живая, то γ маркируется M. Далее, так как L и M отличаются только маркировкой места s, то цикл γ содержит s. Более того, s — единственное место в γ, которое маркируется M. Значит, M(γ)=M(s). Следовательно, M(γ)b, поскольку M(s)b.

(): Пусть M — произвольная достижимая маркировка и s — произвольное место в (N,M0). По предположению, s принадлежит циклу γ такому, что M0(γ)b. Согласно утверждению 17, имеем, что M(γ)b. Значит, M(s)b. □

Следствие 2  Пусть  (N=(S,T,F),M0)живая T-СП.

а)  Место  sS  является ограниченным, если и только если s содержится в некотором цикле сети N.

б)  Если место  sS  ограничено, то его граница равна  min{M0(γ)|γцикл сети N, содержащий s}.

в)T-СП  (N,M0)  ограничена, если и только если сеть N сильно связна.

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

а)  (): Пусть sS ограничено. Тогда доказательство теоремы 23 показывает, что s содержится в некотором цикле γ таком, что M0(γ) — граница места s.

(): Предположим, что s содержится в некотором цикле сети N. Согласно утверждению 17s не может содержать больше, чем M0(γ) фишек.

б)  Согласно пункту а), s содержится в некотором цикле сети N. Так как M0(γ) — граница места s, то достаточно показать, что для каждого цикла δ, содержащего s, верно, что M0(δ)M0(γ).

Пусть M — достижимая маркировка такая, что M(s) равно границе места s. Тогда M0(γ)=M(s). Поскольку δ содержит s, то верно M(s)M(δ). Значит, M0(γ)M(δ). Согласно утверждению 17, имеем, что M0(γ)M0(δ).

в)  (): Следует из теоремы 13. Также следует из теоремы 23: поскольку (N,M0) ограничена, то каждое ее место содержится в некотором цикле сети N; так как каждое место имеет ровно один входной переход и ровно один выходной переход, то для каждой дуги (x,y) в N данный цикл имеет префикс xy. Вместе со связностью сети N это означает, что сеть N сильно связна.

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

T-СП, изображенная на рис. 2.28, является живой. Место s5 не содержится ни в каком цикле. Заметим также, что базовая сеть этой T-СП не является сильно связной. Следовательно, эта T-СП не ограничена. Действительно, в месте s5 может накапливаться бесконечное количество фишек. Тогда как в живой T-СП на рис. 2.29 каждое место принадлежит некоторому циклу. Кроме того, базовая сеть этой T-СП является сильно связной. Следовательно, эта T-СП ограничена. Причем, граница каждого места равна 1.