Пространство структур сетей Петри

3.4. Пространство структур сетей Петри

Ранее мы выделили множество СП Lm и отношение частичного порядка ІіІ . Дополнительно введем множество Q других отношений эквивалентности. Тогда пространством структур СП назовем тройку:

L = < Lm , P , Q > ,

где P - отношение частичного порядка ІіІ .

Любое из отношений эквивалентности q О Q может служить для разбиения множества Lm на смежные классы и построения некоторой шкалы путем сопоставления данных классов. Дробность шкалы можно определить числом k , таким, что q = q1 & q2 & ... & qk , где q - отношение эквивалентности, по которому осуществлено разбиение Lm на смежные классы.

Соответствие Q, однозначное в одну сторону и удовлетворяющее условию: если x і y , то Q(x) і Q(y) , называется изотонным или сохраняющим порядок [7]. Две шкалы Z и Z' будем называть эквивалентными, если существует такое взаимно однозначное отображение f: Z ® Z' , при котором из zi < zj , где (zi , zj) О Z , следует zi’ < zj’ , где

(zi’ , zj’) О Z’, (причем zi’ = f(zi) , zj’ = f(zj)) и обратно. Другими словами, эквивалентность шкал означает существование взаимно однозначного и изотонного отображения одной шкалы на другую.

На семействе смежных классов Lm ={Li} могут быть заданы различные функции оценки n[Li ], определенные на Lm .

Оценка является изотонной тогда и только тогда, когда из условия L' Ј L'' следует, что n[L'] Ј n [L''] ; положительной - тогда и только тогда, когда из L' < L'' следует, что n[L'] < n [L''].

Рекомендуемые материалы

Оценка является ограниченной сверху тогда и только тогда, когда существует конечное положительное число q и для всех цепей L' < L''<...<  имеет место неравенство:

n [] - n[ L' ] Ј q .

Структура с изотонной оценкой n[Li] называется квазиметрической, а с положительной n[Li] - метрической [7].

Расстоянием Гливенко от LОLm до L'ОLm произвольной квазиметрической (или метрической) структуры является функция

d(L,L') = n[L] - n[L'] .

Квазиметрическое пространство (или пространство Гливенко) есть пространство, в котором может быть определена функция d(L,L') со следующими свойствами:

            (1) d(L,L') = 0;

            (2) d(L,L') > 0 при L' № L ;

            (3) d(L,L') = d(L’,L) ;

            (4) d(L,L') + d(L’,L’’) і d(L,L’’) .

Очевидно, что оценка n[L] является одинаковой для всех элементов Ni О L , т.к. данная оценка является критерием для построения семейства смежных классов. Если функции оценки n[L] поставить в соответствие число вершин в СП-структуре и рассмотреть семейство Lm ={Li} , то нетрудно заметить, что свойства (1)-(4) выполняются. Таким образом, пространство структур СП, разбитое на семейство смежных классов Lm ={Li} , является пространством Гливенко.

Вернемся к диаграмме структур СП, представленной рис.3.2. Здесь оценка

n[N]=ЅNЅ для всех NОLm (при m=2) разбивает множество Lm на 5 классов эквивалентности. Каждый класс объединяет множество СП-структур с одинаковым числом вершин. Класс эквивалентности на рис.3.2 отображается величиной уровня грани. Внутри каждого класса построена еще одна шкала n1[Li] , которая оценивает сумму весов головных и хвостовых позиций каждой СП-структуры NОLi, например, в соответствии со следующим выражением:

 ,                         (3.4)

где  - число головных позиций,  - число хвостовых позиций; S1 , S2 - веса головных и хвостовых позиций соответственно.

Видно, что оценка n1[Li] также разбивает каждый класс эквивалентности на подклассы. Например, класс L3 = {N15 , N16 , N17 , N18 , N19 } разбит на подклассы: L31 = {N15, N16 }, L32 = {N17}, L33 = {N18}, L3 = {N19}.

Рассмотрим свойства шкал, представленных на рис.3.2. Обозначим через n' число позиций, m' - число переходов, w - число операций объединения, с помощью которых построена СП-структура. Тогда можно заметить следующее соотношение:

             n' + m' + w = 3r = const                             (3.5)

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

Рассмотрим шкалу n1[Lm] . Можно ли считать пространство L=<Lm, P, Q>квазиметрическим пространством, если на нем введена функция d(L,L') = n1[L] -

- n1[L'] ?

Если L, L' и L''' - классы эквивалентности, которые строятся при отношении

q = n1[Lm] , то легко увидеть выполнимость свойств (1) - (4). Следовательно, пространство Lm , на котором введена функция n1[Lm], также является квазиметрическим.

Рассмотрим следующий вопрос: существуют ли инварианты при перемещении по шкале n1[Lm]? На рис.3.2 шкала n1[Lm] построена из предположения, что S1=1, S2=2. Для поиска инвариантов введем следующие веса для позиций и операций объединения вершин СП-структур:

- если p головная позиция, то S(p) = S1 = 1 ;

- если p хвостовая позиция, то S(p) = S2 = 2 ;

- если p внутренняя позиция, то S(p) = S3 = 0 ;

- вес операции объединения l позиций pi и pj определяется как:

S(l) = S(pi) (или S(pj)) - если объединяются только головные или только хвостовые позиции; S(l) = S(pi ) + S(pj) - если объединяются разные позиции.

Рассмотрим выражение

Люди также интересуются этой лекцией: Политический менеджмент как теория и как практика.

 ,          (3.6)

где  - число головных позиций,  - число хвостовых позиций в СП-структуре, w - число операций объединения, с помощью которых построена анализируемая СП-структура,  S(N) - вес СП-структуры N .

Для всех СП-структур Ni О Lm , изображенных на рис.3.2, вес СП-структур, найденный в соответствии с выражением (3.6), является величиной постоянной и равен утроенному рангу структуры СП 3r . Следовательно, величина S(N) также является инвариантом.

Легко убедиться, что инварианты, описываемые выражениями (3.5) и (3.6), выполняются и на структурах СП с более высоким рангом. На основе этого можно сформулировать следующую теорему.

Теорема 3.6. В любой полной структуре СП с рангом r можно построить систему оценочных шкал, при которых существуют инварианты с численным значением равным 3r.

Отличительной особенностью данного формализма является эффективное сочетание свойств аппарата СП с возможностями теории структур.