Пространство структур сетей Петри
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.
Отличительной особенностью данного формализма является эффективное сочетание свойств аппарата СП с возможностями теории структур.
