Правила виконання мереж Петрі

ВСТУП

Структура мережі Петрі

Мережа Петрі складається із чотирьох елементів: множина позицій P, множина переходів T, вхідна функція I і вихідна функція O. Вхідна і вихідна функції пов'язані з переходами і позиціями. Вхідна функція I відображає перехід t_j у множину позицій I(t_j), що називаються вхідними позиціями переходу. Вихідна функція O відображає перехід t_j у множину позицій O(t_j), що називаються вихідними позиціями переходу.

Структура мережі Петрі визначається її позиціями, переходами, вхідною і вихідною функціями.

Визначення 1.Мережа Петрі C є четвіркою, C=(P, T, I, O). P={p₁, p₂, .., p_n} — кінцева множина позицій, n > 0. T={t₁, t₂, …, t_m} — кінцева множина переходів, m > 0. Множина позицій і множина переходів не перетинаються, P∩T = 0. I:T→P^∞ є вхідною функцією — відображенням з переходів у комплекти позицій. O:T→P^∞ є вихідна функція — відображення з переходів у комплекти позицій.

Потужність множини Р є число n, а потужність множини Т є число m. Довільний елемент Р позначається символом p_i, i=1, ..., n, а довільний елемент Т — символом t_j, j=1,..., т.

Приклади мереж Петрі дані на рис. 1-3.

Позиція p_i є вхідною позицією переходу t_j у тому випадку, якщо p_i I (tj); p_i є вихідною позицією, якщо p_t О(tj). Входи і виходи переходів являють собою комплекти позицій. Комплект є узагальненням множини, у яке включені багаторазово повторювані елементи — тиражовані елементи. Використання комплектів, а не множин для входів і виходів переходу дозволяє позиції бути кратним входом або кратним виходом переходу. Кратність вхідної позиції p_t для переходу t_j є число появ позиції у вхідному комплекті переходу, # ( p_i, I (tj)). Аналогічно кратність вихідної позиції p_t для переходу t_j є число появ позиції у вихідному комплекті переходу, #(р₄, О (tj)). Якщо вхідна і вихідна функції є множинами (а не комплектами), то кратність кожної позиції є або 0, або 1.

Вхідні і вихідні функції використовуються для відображення позицій у комплекти переходів, а також їх можна використати для відображення переходів у комплекти позицій. Визначимо, що перехід t_j є входом позиції р_i якщо р_i є вихід t_j. Перехід t_j є вихід позиції р_i якщо p_i є вхід t_j.

Визначення 2.Визначимо розширену вхідну функцію I і вихідну функцію

I : Р Т°°, О: Р Т°° таким чином, що

# (t_j, I(p_i)) = # (P_i, 0 (t_j)), # (tj, О (p_t)) = # (p_it I (tj)).

Для мережі Петрі на рис. 1 розширеними вхідною і вихідною функціями є:

I(p₁) = { }, O(p₁) = {t₁ },

I(p₂) = {t₁, t₄ }, O(p₂) = {t₂ },

I(p₃) = {t₁, t₄ }, O(p₃) = {t₂,t₃},

I(p₄) = {t₃ }, O(p₄)={t₄},

I(p₅) = {t₁, t₂ }, O(p₅) = {t₂).

C=(P, T, I, O),

P={p₁, p₂, p₃, p₄, p₅},

T={t₁, t₂, t₃, t₄},

I(t₁) = {p₁}, O(t₁) = {p₂, p₃, p₅},

I(t₂) = {p₂, p₃, p₅ }, O(t₂) = {p₅},

I(t₃) = {p₃}, O(t₃) = {p₄},

I(t₄) = {p₄}, O(t₄) = {p₂, p₃}.

Рис. 1. Структура мережі Петрі представлена у вигляді четвірки, що складається із множини позицій (Р), множини переходів (T), вхідної функції I : T P°° і вихідної функції (O : T P°°)

З=(Р, Т, I, О),

P = {p₁, p₂, p₃, p₄, p₅, p₆},

T={t₁, t₂, t₃, t₄, t₅},

I(t₁) = {p₁}, O(t₁) = {p₂, p₃},

I(t₂) = {p₃}, O(t₂) = {p₃, p₅, p₅},

I(t₃) = {p₂, p₃}, O(t₃) = {p₂, p₄},

I(t₄) = {p₄, p₅, p₅, p₅}, O(t₄) = {p₄},

I(t₅) = {p₂}, O(t₅) = {p₆}.

Рис. 2. Структура мережі Петрі

З=(Р, Т, I, О),

P = {p₁, p₂, p₃, p₄, p₅, p₆, p₇, p₈, p₉},

T={t₁, t₂, t₃, t₄, t₅, t₆},

I(t₁) = {p₁}, O(t₁) = {p₂, p₃},

I(t₂) = {p₈}, O(t₂) = {p₁, p₇},

I(t₃) = {p₂, p₅}, O(t₃) = {p₆},

I(t₄) = {p₃}, O(t₄) = {p₄},

I(t₅) = {p₆, p₇}, O(t₅) = {p₉},

I(t₆) = {p₄, p₉}, O(t₆) = {p₅, p₈}.

Рис. 3. Структура мережі Петрі

Вправи.

1.Знайдіть розширену вхідну і вихідну функції мереж Петрі (рис. 2 і 3).

2.Покажіть, що вхідна і вихідна функції одночасно не є необхідними і що мережа Петрі може бути визначена множинами позицій, переходів і розширеною вхідний (або вихідний) функцією. Для цього покажіть, як розширена вихідна функція може бути визначена з розширеної вхідної функції і навпаки.

Графи мереж Петрі

У значній мірі теоретична робота з мережами Петрі заснована на формальному визначенні мереж Петрі, викладеному вище. Проте, для ілюстрації понять теорії мереж Петрі набагато більш зручним є графічне подання мережі Петрі. Теоретико-графовим поданням мережі Петрі є двочастковий орієнтований мультиграф.

Структура мережі Петрі являє собою сукупність позицій і переходів. Відповідно до цього граф мережі Петрі володіє двома типами вузлів. Кружок О є позицією, а планка | — переходом.

Орієнтовані дуги (стрілки) з'єднують позиції і переходи, при цьому деякі дуги спрямовані від позицій до переходів, а інші — від переходів до позицій. Дуга, спрямована від позиції p_i до переходу t_j, визначає позицію, що є входом переходу. Кратні входи в перехід указуються кратними дугами із вхідних позицій у перехід. Вихідна позиція вказується дугою від переходу до позиції. Кратні виходи також представлені кратними дугами.

Мережа Петрі є мультиграф, тому що він припускає існування кратних дуг від однієї вершини графа до іншої. Варто додати, що тому що дуги є спрямованими, те це орієнтований мультиграф. Ми знаємо, що вершини графа можна розділити на дві множини (позиції і переходи) таким чином, що кожна дуга буде спрямована від елемента однієї множини (позицій або переходів) до елемента іншої множини (переходів або позицій); отже, такий граф є двочастковим орієнтованим мультиграфом. Надалі для простоти будемо називати його просто графом мережі Пртри.

Визначення 3. Граф G мережі Петрі є двочастковий орієнтований мультиграф, G = (V, А), де V= {й₁, u₂, …, u_s} — множина вершин, а А = {а₁, а₂, ..., а_r} — комплект спрямованих дуг, а_i = (v_j, v_k), де v_j, v_k V. Множина V може бути розбите на дві непересічні підмножини Р и Т, таких, що V = Р U Т, Р Т = , і для будь-якої спрямованої дуги a_t А, якщо a_t = (v_j, v_k), тоді або v_j Р и v_k T, або v_j Т, a v_k Р.

Графи мережі Петрі, зображені на рис. 4 - 6, еквівалентні структурам мережі Петрі на рис. 1 - 3.

Для демонстрації еквівалентності цих двох подань мережі Петрі — структури мережі Петрі і графа мережі Петрі — покажемо, яким чином можна перетворити один в іншій. Припустимо, нам дана структура мережі Петрі З = (Р, Т, I, О) з Р = = {p₁, p₂, …, p_n} і Т = {t₁, t₂, ..., t_m). Тоді граф мережі Петрі можна визначити в такий спосіб.

Визначення 4. Визначимо V = P T. Визначимо А як комплект спрямованих дуг, такий, що для всіх p_i P і t_j Т

# ((p_i, t_j), A) = # (р_i, I (t_j)),

#((t_j, p_i), A) = #(p_i, 0(t_j)).

G = (V, А) є граф мережі Петрі, еквівалентний структурі мережі Петрі З = (Р, Т, I, О).

Зворотне перетворення (від графа мережі Петрі до структури) здійснюється подібним чином. Однак при переході від графа мережі Петрі до структури мережі Петрі виникає одна цікава задача: якщо множину вершин можна розділити на дві підмножини S і R, то яка із цих підмножин повинна бути позиціями, а яка — переходами? Обоє можливих варіанта дозволяють визначити мережу Петрі, хоча в структурах, що виходять в результаті, позиції і переходи міняються місцями.

Рис. 4. Граф мережі Петрі, еквівалентний структурі, показаної на рис. 1

Рис 5. Граф мережі Петрі, еквівалентний структурі, зображеної на рис. 2

Рис. 6. Граф мережі Петрі, еквівалентний структурі, показаної на рис. 3

Рис. 7. Мережа, двоїста до мережі Петрі, показаної на рис. 4

Двоїстої до мережі Петрі З = (Р, Т, I, О) є мережа Петрі З = (Т, Р, I, О), що виходить у результаті перестановки позицій і переходів. Структура графа зберігається, просто міняються місцями кружки і планки (див. вправу 6). На рис. 7 показана мережа, двоїста до мережі Петрі на рис. 4. Подвійність — звичайно корисний прийом у теорії графів і здається цікавим поняттям для мереж Петрі. Однак ніякої користі витягти з поняття двоїстої мережі Петрі в дослідженні цих мереж не представляється можливим. Це порозумівається в основному труднощами визначення мережі, двоїстої до маркірованої мережі Петрі. Маркіровані мережі Петрі ми обговоримо пізніше.

Вправи

1. Побудуйте графи мереж Петрі, двоїсті до мереж Петрі, показаним на рис. 5 і 6.

2. Побудуйте граф мережі Петрі для наступної структури мережі Петрі:

P = {p₁, p₂, p₃, p₄},

T={t₁, t₂, t₃, t₄, t₅},

I(t₁) = { }, O(t₁) = {p₁},

I(t₂) = {p₁}, O(t₂) = {p₂},

I(t₃) = {p₂, p₄}, O(t₃) = {p₁, p₃},

I(t₄) = { }, O(t₄) = {p₃},

I(t₅) = {p₃}, O(t₅) = {p₄}.

3. Зобразите граф мережі Петрі наступної структури:

P = {p₁, p₂},

T={t₁, t₂, t₃},

I(t₁) = {p₁ }, O(t₁) = {p₁, p₂},

I(t₂) = {p₁}, O(t₂) = {p₂},

I(t₃) = {p₂}, O(t₃) = { }.

4. Покажіть, що двоїста до двоїстої мережі Петрі С є сама мережа С.

5. Визначите клас мереж Петрі, які збігаються із двоїстими до себе. Чи можете ви дати просту характеризацію цього класу мереж Петрі?

6. Якщо мережа, двоїста до мережі Петрі С = (Р, Т, I, О), визначена як = (Т, Р, I, О), вхідні і вихідні функції повинні бути розширені для відображення і P, і Т. Чому? Якщо С = (Р, Т, 1, О) має нерозширені вхідні і вихідні функції, дайте визначення = (T, Р, I', 0') з нерозширеними вхідними і вихідними функціями.

7. Знайдіть структуру мережі Петрі, що відповідає графу мережі Петрі на рис. 8. Визначите структуру мережі Петрі для графа на рис. 9.

8. Графи мережі Петрі є мультиграфами, тому що позиція може бути кратним входом або виходом переходу. У графі це показується декількома дугами між позицією і переходом. У той час як такий спосіб задовільний для дуг з малою кратністю (не більше трьох), він незручний для дуг дуже великої кратності. Таким чином, як альтернативне подання структур з великою кратністю використовується пучок дуг. Пучок — це спеціальна дуга, що рисується жирною лінією і позначається кратністю.

Рис. 10 ілюструє перехід із вхідною кратністю 7 і вихідною кратністю 11. Намалюйте граф мережі Петрі для наступної структури:

P = {p₁, p₂, p₃, p₄},

T={t₁, t₂, t₃, t₄},

I(t₁) = { }, O(t₁) = {p₁, p₁, p₁, p₁, p₂},

I(t₂) = {p₂}, O(t₂) = {p₁, p₁, p₁, p₁, p₁, p₁, p₃},

I(t₃) = {p₁, p₁, p₁, p₁, p₁, p₁}, O(t₃) = {p₂, p₂, p₂, p₂, p₄, p₄},

I(t₄) = { p₃, p₄, p₄, p₂}, O(t₄) = { }.

Рис. 8. Граф мережі Петрі Рис. 9. Граф мережі Петрі

Рис. 10. Пучок дуг. Для графів з великою кратністю використається пучок дуг, позначений числом кратності, а не зображення всіх кратних дуг

9. Інверсна мережа Петрі — С_інв для мережі Петрі С = (Р, T, I, 0) визначається перестановкою вхідної і вихідної функцій — С = (Р, Т, О, I). Як це вплине на граф мережі Петрі? У чому відмінність від двоїстої мережі Петрі? Чи зробить вплив розширення вхідної і вихідної функцій? Зобразіть інверсну мережу Петрі для мережі Петрі, наведеної на рис. 7.

Маркування мереж Петрі

Маркуванням є присвоєння фішок позиціям мережі Петрі. Фішка - це примітивне поняття мереж Петрі (подібно позиціям і переходам). Фішки привласнюються (можна вважати, що вони належать) позиціям. Кількість і положення фішок при виконанні мережі Петрі можуть змінюватися. Фішки використаються для визначення виконання мережі Петрі.

Визначення 5. Маркування мережі Петрі С = (Р, Т, I, О) є функція, що відображає множину позицій Р у множині ненегативних цілих чисел N.

: Р N.

Маркування може бути також визначена як n-вектор = = ( ₁, ₂, ...., _n). де п= і кожне N, i = 1, ..., п.

Рис. 11. Маркірована мережа Петрі. Структура мережі Петрі збігається зі структурами на рис. 1 і 4. Маркування - (1, 2, 0, 0, 1)

Рис. 12. Маркірована мережа Петрі. Структура аналогічна структурі, зображеної на рис. 11, але маркування відрізняється

Вектор визначає для кожної позиції p_i мережі Петрі кількість фішок у цій позиції. Кількість фішок у позиції р_i є _i, i = 1, ..., n. Зв'язок між визначеннями маркування як функції і як вектора очевидним образом установлюється співвідношенням (p_i)= _i. Позначення її у вигляді функції є трохи більше загальним і тому вживається набагато частіше.

Маркірована мережа Петрі М = (З, ) є сукупність структури мережі Петрі З = (Р, Т, I, О) і маркування і може бути записана у вигляді М = (Р, Т, I, О, ).

На графі мережі Петрі фішки зображуються маленькою крапкою в кружку, що представляє позицію мережі Петрі. На рис. 11 і 12 наведені приклади графічного подання маркірованої мережі Петрі.

Тому що кількість фішок, що може бути визначене для кожної позиції, необмежено, те в цілому для мережі Петрі існує нескінченно багато маркувань. Множина всіх маркувань мережі Петрі, що володіє n позиціями, є множина всіх n-векторів, Nⁿ. Це множина, хоча і нескінченно, є рахунковим.

Рис. 13. Граф мережі Петрі з дуже великим маркуванням (47, 13, 7, 42)

Вправи

1.Для маркірованої мережі Петрі (рис. 12) представте маркування як функцію і як вектор.

2.Для структури мережі Петрі (рис. 2) зобразите граф мережі Петрі і укажіть на графі маркування = (1, 0, 1, 1, 0, 0).

3.Кількість фішок у мережі Петрі рідко перевищує 5 або 6. У цьому випадку їх малюють. Однак, коли маркування має 10, 20 або сотні фішок, приписаних позиції, у кружках зручніше не малювати фішки, а вказувати їхня загальна кількість, як на рис. 2.13. Використовуючи цей спосіб, зобразіть маркування = (137, 22, 2, 0, 14) для мережі Петрі на рис. 12.

Правила виконання мереж Петрі

Виконанням мережі Петрі управляють кількість і розподіл фішок у мережі. Фішки перебувають у кружках і управляють виконанням переходів мережі. Мережа Петрі виконується за допомогою запусків переходів. Перехід запускається видаленням фішок з його вхідних позицій і утворенням нових фішок, що поміщають у його вихідні позиції.

Перехід може запускатися тільки в тому випадку, коли він дозволений. Перехід називається дозволеним, якщо кожна з його вхідних позицій має число фішок принаймні рівне числу дуг з позиції в перехід. Кратні фішки необхідні для кратних вхідних дуг. Фішки у вхідній позиції, які дозволяють перехід, називаються його розв'язними фішками. Наприклад, якщо позиції p₁ і р₂ служать входами для переходу t₄, тоді t₄ дозволений, якщо p₁ і р₂ мають хоча б по одній фішці. Для переходу t₇ із вхідним комплектом {р₆, р₆, р₆} позиція р₆ повинна володіти принаймні трьома фішками, для того щоб t₇ був дозволений.

Визначення 6. Перехід t_j Т у маркірованої мережі Петрі С = {Р, Т, I, О) з маркуванням , дозволений, якщо для всіх p_i P

(p_i) #(p_i, I(t_j)).

Перехід запускається видаленням всіх розв'язних фішок з його вхідних позицій і наступним приміщенням у кожну з його вихідних позицій по одній фішці для кожної дуги. Кратні фішки створюються для кратних вихідних дуг. Перехід t₃ з I(t₃) = {р₂} і O(t₃) = {р₇, р₁₃} дозволений щораз, коли в р₂ буде хоча б одна фішка. Перехід t₃ запускається видаленням однієї фішки з позиції р₂ і приміщенням однієї фішки в позицію р₇ і в p₁₃ (його виходи). Додаткові фішки в позиції р₂ не впливають на запуск t₃ (хоча вони можуть дозволяти додаткові запуски t₃). Перехід t₂, у якому I(t₂) = {p₂₁, р₂₃} і O(t₂) = {р₂₃, р₂₅, р₂₅}, запускається видаленням однієї фішки з p₂₁ і однієї фішки з р₂₃, при цьому одна фішка міститься в р₂₃ і дві в — р₂₅ (тому що р₂₅ має кратність, рівну двом).

Запуск переходу в цілому заміняє маркування мережі Петрі на нове маркування '. Помітимо також, що тому що можна запустити тільки дозволений перехід, то при запуску переходу кількість фішок у кожній позиції завжди залишається ненегативним. Запуск переходу ніколи не видалить фішку, відсутню у вхідній позиції. Якщо яка-небудь вхідна позиція переходу не має достатню кількість фішок, то перехід не дозволений і не може бути запущений.

Визначення 7. Перехід t_j у маркірованій мережі Петрі з маркуванням може бути запущений щораз, коли він дозволений. У результаті запуску дозволеного переходу t_j утвориться нове маркування ', обумовлена наступним співвідношенням: '(p_i) = (p_i) - #(p_i, I(t_j)) + #(p_i, O(t_j)).

Рис. 14. Ілюстрація того, як міняється маркування позицій, коли запущений перехід t_j. Кожна позиція може або не може бути входом або виходом переходу. Тут показаний випадок для кратності 0 або 1.

Запуски можуть здійснюватися доти, поки існує хоча б один дозволений перехід. Коли не залишиться жодного дозволеного переходу, виконання припиняється.

Вправи

1. Які переходи дозволені в маркірованій мережі Петрі на рис. 11, 12?

2. Яке маркування вийде при запуску переходу t₁ (рис. 11)? Яке маркування вийде при запуску переходу t₄ (рис. 12)? Яке маркування вийде в результаті виконання наступних операцій: спочатку — запуск t₄, потім — запуск t₂ (рис. 12)?

3. Які переходи дозволені в мережі Петрі на рис. 13? Які маркування утворяться при запуску кожного із цих переходів?