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

ВСТУП

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

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

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

Визначення 1.Мережа Петрі C є четвіркою, C=(P, T, I, O). P={p1, p2, .., pn} — кінцева множина позицій, n > 0. T={t1, t2, …, tm} — кінцева множина переходів, m > 0. Множина позицій і множина переходів не перетинаються, P∩T = 0. I:T→P є вхідною функцією — відображенням з переходів у комплекти позицій. O:T→P є вихідна функція — відображення з переходів у комплекти позицій.

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

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

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

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

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

I : Р Правила виконання мереж Петрі - student2.ru Т°°, О: Р Правила виконання мереж Петрі - student2.ru Т°° таким чином, що

# (tj, I(pi)) = # (Pi, 0 (tj)), # (tj, О (pt)) = # (pit I (tj)).

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

I(p1) = { }, O(p1) = {t1 },

I(p2) = {t1, t4 }, O(p2) = {t2 },

I(p3) = {t1, t4 }, O(p3) = {t2,t3},

I(p4) = {t3 }, O(p4)={t4},

I(p5) = {t1, t2 }, O(p5) = {t2).

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

P={p1, p2, p3, p4, p5},

T={t1, t2, t3, t4},

I(t1) = {p1}, O(t1) = {p2, p3, p5},

I(t2) = {p2, p3, p5 }, O(t2) = {p5},

I(t3) = {p3}, O(t3) = {p4},

I(t4) = {p4}, O(t4) = {p2, p3}.

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

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

P = {p1, p2, p3, p4, p5, p6},

T={t1, t2, t3, t4, t5},

I(t1) = {p1}, O(t1) = {p2, p3},

I(t2) = {p3}, O(t2) = {p3, p5, p5},

I(t3) = {p2, p3}, O(t3) = {p2, p4},

I(t4) = {p4, p5, p5, p5}, O(t4) = {p4},

I(t5) = {p2}, O(t5) = {p6}.

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

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

P = {p1, p2, p3, p4, p5, p6, p7, p8, p9},

T={t1, t2, t3, t4, t5, t6},

I(t1) = {p1}, O(t1) = {p2, p3},

I(t2) = {p8}, O(t2) = {p1, p7},

I(t3) = {p2, p5}, O(t3) = {p6},

I(t4) = {p3}, O(t4) = {p4},

I(t5) = {p6, p7}, O(t5) = {p9},

I(t6) = {p4, p9}, O(t6) = {p5, p8}.

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

Вправи.

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

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

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

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

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

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

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

Визначення 3. Граф G мережі Петрі є двочастковий орієнтований мультиграф, G = (V, А), де V= {й1, u2, …, us} — множина вершин, а А = {а1, а2, ..., аr} — комплект спрямованих дуг, аi = (vj, vk), де vj, vk Правила виконання мереж Петрі - student2.ru V. Множина V може бути розбите на дві непересічні підмножини Р и Т, таких, що V = Р U Т, Р Правила виконання мереж Петрі - student2.ru Т = Правила виконання мереж Петрі - student2.ru , і для будь-якої спрямованої дуги at Правила виконання мереж Петрі - student2.ru А, якщо at = (vj, vk), тоді або vj Правила виконання мереж Петрі - student2.ru Р и vk Правила виконання мереж Петрі - student2.ru T, або vj Правила виконання мереж Петрі - student2.ru Т, a vk Правила виконання мереж Петрі - student2.ru Р.

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

Для демонстрації еквівалентності цих двох подань мережі Петрі — структури мережі Петрі і графа мережі Петрі — покажемо, яким чином можна перетворити один в іншій. Припустимо, нам дана структура мережі Петрі З = (Р, Т, I, О) з Р = = {p1, p2, …, pn} і Т = {t1, t2, ..., tm). Тоді граф мережі Петрі можна визначити в такий спосіб.

Визначення 4. Визначимо V = P Правила виконання мереж Петрі - student2.ru T. Визначимо А як комплект спрямованих дуг, такий, що для всіх pi Правила виконання мереж Петрі - student2.ru P і tj Правила виконання мереж Петрі - student2.ru Т

# ((pi, tj), A) = # (рi, I (tj)),

#((tj, pi), A) = #(pi, 0(tj)).

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

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

Правила виконання мереж Петрі - student2.ru

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

Правила виконання мереж Петрі - student2.ru

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

Правила виконання мереж Петрі - student2.ru

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

Правила виконання мереж Петрі - student2.ru

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

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

Вправи

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

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

P = {p1, p2, p3, p4},

T={t1, t2, t3, t4, t5},

I(t1) = { }, O(t1) = {p1},

I(t2) = {p1}, O(t2) = {p2},

I(t3) = {p2, p4}, O(t3) = {p1, p3},

I(t4) = { }, O(t4) = {p3},

I(t5) = {p3}, O(t5) = {p4}.

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

P = {p1, p2},

T={t1, t2, t3},

I(t1) = {p1 }, O(t1) = {p1, p2},

I(t2) = {p1}, O(t2) = {p2},

I(t3) = {p2}, O(t3) = { }.

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

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

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

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

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

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

P = {p1, p2, p3, p4},

T={t1, t2, t3, t4},

I(t1) = { }, O(t1) = {p1, p1, p1, p1, p2},

I(t2) = {p2}, O(t2) = {p1, p1, p1, p1, p1, p1, p3},

I(t3) = {p1, p1, p1, p1, p1, p1}, O(t3) = {p2, p2, p2, p2, p4, p4},

I(t4) = { p3, p4, p4, p2}, O(t4) = { }.

Правила виконання мереж Петрі - student2.ru

Правила виконання мереж Петрі - student2.ru

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

Правила виконання мереж Петрі - student2.ru

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

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

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

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

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

Правила виконання мереж Петрі - student2.ru : Р Правила виконання мереж Петрі - student2.ru N.

Маркування Правила виконання мереж Петрі - student2.ru може бути також визначена як n-вектор Правила виконання мереж Петрі - student2.ru = = ( Правила виконання мереж Петрі - student2.ru 1, Правила виконання мереж Петрі - student2.ru 2, ...., Правила виконання мереж Петрі - student2.ru n). де п= Правила виконання мереж Петрі - student2.ru і кожне Правила виконання мереж Петрі - student2.ru Правила виконання мереж Петрі - student2.ru N, i = 1, ..., п.

Правила виконання мереж Петрі - student2.ru

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

Правила виконання мереж Петрі - student2.ru

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

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

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

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

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

Правила виконання мереж Петрі - student2.ru

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

Вправи

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

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

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

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

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

Перехід може запускатися тільки в тому випадку, коли він дозволений. Перехід називається дозволеним, якщо кожна з його вхідних позицій має число фішок принаймні рівне числу дуг з позиції в перехід. Кратні фішки необхідні для кратних вхідних дуг. Фішки у вхідній позиції, які дозволяють перехід, називаються його розв'язними фішками. Наприклад, якщо позиції p1 і р2 служать входами для переходу t4, тоді t4 дозволений, якщо p1 і р2 мають хоча б по одній фішці. Для переходу t7 із вхідним комплектом {р6, р6, р6} позиція р6 повинна володіти принаймні трьома фішками, для того щоб t7 був дозволений.

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

Правила виконання мереж Петрі - student2.ru (pi) Правила виконання мереж Петрі - student2.ru #(pi, I(tj)).

Перехід запускається видаленням всіх розв'язних фішок з його вхідних позицій і наступним приміщенням у кожну з його вихідних позицій по одній фішці для кожної дуги. Кратні фішки створюються для кратних вихідних дуг. Перехід t3 з I(t3) = {р2} і O(t3) = {р7, р13} дозволений щораз, коли в р2 буде хоча б одна фішка. Перехід t3 запускається видаленням однієї фішки з позиції р2 і приміщенням однієї фішки в позицію р7 і в p13 (його виходи). Додаткові фішки в позиції р2 не впливають на запуск t3 (хоча вони можуть дозволяти додаткові запуски t3). Перехід t2, у якому I(t2) = {p21, р23} і O(t2) = {р23, р25, р25}, запускається видаленням однієї фішки з p21 і однієї фішки з р23, при цьому одна фішка міститься в р23 і дві в — р25 (тому що р25 має кратність, рівну двом).

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

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

Правила виконання мереж Петрі - student2.ru

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

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

Вправи

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

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

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

Наши рекомендации