|
131 те элементы, которые не достижимы в развернутой сети при движении от места р'л вдоль дуг сети. При этом необходима корректировка вторых верхних индексов оставшихся элементов. Для элемента х',у берется новый второй индекс (j -к), где к — максимальный индекс удаленного элемента Х'< Рис. 2.14. Развертка примитивной сети с произвольной начальной разметкой Развертка примитивной сети с произвольной начальной разметкой может привести к сети, не являющейся 5 -сетью, т.е. теорема 7.8 не верна для этого случая. Например, сеть на рис. 2.14. является А -сетью. Для получаемых сетей-процессов выполняется ограничение, т.е. каждый переход имеет ровно одну входную и ровно одну выходную дуги, но нарушается требование к 5 -сети иметь ровно одно головное место. Рассмотрим развертку подкласса регулярных сетей, которые мы назовем параллельными сетями. Параллельная сеть N представляет собой наложение последовательных сетей Nn, каждая из которых является простым путем или простым (регулярным) циклом. Примеры параллельных сетей показаны на рис. 2.15. Процедура развертки параллельных сетей включает три этапа. На первом этапе в исходной сети N = (N,,N2,..., N„) выделяются все ее последовательные составляющие, и каждая из них разворачивается по правилам развертки примитивных сетей с произвольной разметкой (последовательная сеть является честным случаем примитивной сети). На втором этапе осуществляется специальная |
62 преобразована в совокупность трех примитивных сетей, две из которых имеют по фишке в головном месте, а третья содержит фишку во “ внутреннем” месте р . . Каждая из копий разворачивается по правилам развертки примитивной сети со стандартной разметкой, причем переходы и места получают второй верхний индекс. В случае, если в некоторой копии фишка содержится не в головном месте сети, как, например, в третьей копии сети на рис. 2.9.6, развертка осуществляется, как будто фишка находится в головном месте. Затем фишка помещается в первое вхождение р ',] (в развертку копии) того места р ' , которое содержало фишку в соответствующей /-й копии исходной сети. Наконец, в развертке /-й копии удаляются все те элементы х (и связывающие их дуги), для которых не выполняется отношение р ' лР +%, т.е. те элементы, которые не достижимы в развернутой сети при движении от места р ' л вдоль дуг сети. При этом необходима корректировка вторых верхних индексов оставшихся элементов. Для элемента %''' берется новый второй индекс ( у к ) , где к — максимальный индекс удаленного элемента х "к. На рис. 2.9. показана сеть, полученная в результате развертки сети. Развертка примитивной сети с произвольной начальной разметкой может привести к сети, не являющейся Б -сетью, т.е. теорема 7.8 не верна щ для этого случая. Например, сеть на рис. 2.9.в является А -сетью. Для получаемых сетей-процессов выполняется ограничение А10 (см. § 7.3), т.е. каждый переход имеет ровно одну входную и ровно одну выходную дуги, но нарушается требование А9 к £ -сети иметь ровно одно головное место. В то же время теорема 7.9 остается верной и для случая примитивной сети с произвольной разметкой. Рассмотрим развертку подкласса регулярных сетей, которые мы назовем параллельными сетями. Параллельная сеть N представляет собой наложение последовательных сетей NХ,Ы Nп, каждая из которых является простым путем или простым (регулярным) циклом. Примеры 63 параллельных сетей показаны на рис. 2.10.а. Процедура развертки параллельных сетей включает три этапа. На первом этапе в исходной сети N = (N^ ,Ыг,..., Ыи) выделяются все ее последовательные составляющие, и каждая из них разворачивается по правилам развертки примитивных сетей с произвольной разметкой (последовательная сеть является честным случаем примитивной сети). На втором этапе осуществляется специальная переиндексация развернутой сети ТУ, для обеспечения последующего наложения развернутых сетей. На третьем этапе развернутые сети накладываются друг на друга с учетом индексации и образуют развернутую сеть (N ^ N 2 7У„) , которая затем приводится к “ каноническому” виду сетипроцесса путем удаления мертвых переходов и связанных с ними дуг и мест. Ь Рис. 2.9. Развертка примитивной сети с произвольной начальной разметкой Пусть /У, — последовательная составляющая параллельной сети и начальная разметка сети Nl помещает в ее места т фишек. После расщепления Ы, на т экземпляров последовательных сетей N1к,1 < к < т со стандартной разметкой (единственная фишка в каждой из копий) и их развертки в 5 -сети производится переиндексация переходов данных сетей следующим образом. На первом шаге новый индекс получают первые переходы в каждой из сетей. Первый переход в первой сети (Ы1Л) получает индекс 1. Если первый переход в к п сети ( М, л ) не имеет одноименных среди первых переходов предыдущих к 1 сетей (Ы1, , то он также получает индекс 1, в противном случае данный переход получает индекс, на |