Методы системного анализа и синтеза: графы и сети Петри

1. Методы системного анализа и синтеза:

Графы и сети Петри

2. ГРАФ. ОПРЕДЕЛЕНИЕ

Граф есть пара
G = V, А ,
где V – множество вершин v, а А V V – множество
пар элементов ai, aj (дуг / ребер) из V.
• Дуги – упорядоченные пары вершин (случай
ориентированного графа);
• Ребра – неупорядоченные пары вершин (случай
неориентированного графа).
Геометрически вершины графа изображаются
точками, а ребра – соединяющими их отрезками (cо
стрелками в случае дуг).
2

3. ОТНОШЕНИЯ И ГРАФЫ

Ребрам графа можно приписывать:
• знаки (знаковые графы);
• числа (взвешенные графы).
Ориентированный
взвешенный граф
Ориентированный граф с
изолированной вершиной
Полный неориентированный граф
Между любыми двумя
вершинами есть связь
3

4. ОТНОШЕНИЯ И ГРАФЫ

Наглядно представлять в виде графов можно различные
отношения.
Представление отношений с помощью графов выражает
следующие их свойства:
• направленные отношения –
Антисимметричность
ориентированные графы
• ненаправленные отношения –
Симметричность
неориентированные графы
Рефлексивность
Число отношений
между вершинами
• есть петля? – граф с циклами
• нет петли? – ациклический граф
(дерево)
• = 1 – граф
• > 1 – мультиграф
4

5. ПРИМЕРЫ ГРАФОВ

Неориентированный граф
с петлей
Взвешенный мультиграф
Между v1 и v5 две дуги с разным
весом
5

6. ГРАФЫ ОТНОШЕНИЙ

Z = {+, , 0}
ТИПЫ ОТНОШЕНИЙ
Ориентированные знаковые графы
ВЗАИМНЫЕ
+
+
v1
v2
v1
v2
0
0
v1
v2
КОНТРАСТНЫЕ
v1
+
v2
v1
+
v2
СЛАБОКОНТРАСТНЫЕ
+
v1
v1
0
0
v2
v1
0
+
v2
0
v2
v1
v2
6

7. ПУТЬ В ГРАФЕ

• Путь – термин для ориентированного графа;
• Цепь – для неориентированного.
Путем в графе называется последовательность из
вершин и дуг:
v1, a1, v2, a2, … , vm, am, vm+1,
где m 0,
ai A и ai всегда является дугой (vi , vi+1).
7

8. ПУТЬ В ГРАФЕ

Путь называется:
простым, если все вершины vi различны;
замкнутым, если vi+1 = v1;
полным, если в него входят все вершины графа G.
Замкнутый путь, в котором v1, … ,vm и a1,…,am
различны, называется контуром (аналогично
определяется цикл для цепи).
Длиной пути называется число входящих в него дуг
(длина цепи – число входящих в нее ребер).
Вершина v достижима из вершины u, если
существует путь с началом в u и концом в v.
8

9. ПРИМЕРЫ ПУТЕЙ В ГРАФЕ

Для графа постройте простой путь, замкнутый путь, полный путь, контур,
полный контур.
Какие вершины достижимы из v1, какие нет?
9

10. ТУРНИРЫ

Ориентированный граф DG = V, А называется турниром, если между
любыми двумя вершинами u, v A существует единственная дуга: либо
(u,v) А, либо (v, u) А.
Примеры турниров с двумя и тремя вершинами приведены ниже.
w
u
v
u
v
Интерпретация турниров для представления конкуренции предприятий
Наличие дуги (u, v) означает, что предприятие u в конкурентной борьбе
одержало победу над предприятием v.
Как быть, если нужно установить победителя в турнире? Обозначим
через s(u) число выходных дуг для вершины u, т.е. число побед
предприятия u над другими предприятиями.
Тогда естественно считать победителем то предприятие, которое
одержало максимальное число побед.
Обоснованность такого подхода к определению победителя
подтверждает следующее утверждение:
В турнире V, А вершина u имеет наибольшее количество побед, то для
любой другой вершины v либо (u,v) А, либо существует вершина w
10
такая, что (u,w) А и (w, v) А.

11. ХАРАКТЕРИСТИКИ ГРАФА: СВЯЗНОСТЬ

Важным понятием в теории графов является понятие
связности.
Если для любых двух вершин графа существует хотя бы
один соединяющий их путь, то граф называется связным.
Связность может быть не только качественной
характеристикой графа (связный/несвязный), но и
количественной.
Граф называется k-связным, если каждая его вершина
связана с числом k других вершин.
Иногда связность определяют как характеристику не
каждой, а одной (произвольной) вершины.
Тогда появляются определения типа: граф называется kсвязным, если хотя бы одна его вершина связана с k
других вершин.
Является ли граф связным, рассчитайте количественную характеристику
связности
11

12. ПОКАЗАТЕЛЬ СВЯЗНОСТИ

Пусть |Rmin | минимальное число связей,
необходимых для связности графа структуры. Если
граф содержит n вершин, то, очевидно,
|Rmin | = n 1.
Для оценки связности структуры можно использовать
показатель , называемый мерой избыточности
структуры по связям, который определяется в виде
относительной разности числа связей | R |,
имеющихся в данной структуре, и |Rmin | :
= (| R | |Rmin | ) / |Rmin | = [| R | / (n 1)] 1.
Каково минимальное количество вершин для графа?
Рассчитайте меру избыточности структуры по связям
12

13. ХАРАКТЕРИСТИКИ ГРАФА: МОЩНОСТЬ

Мощностью графа называется количество дуг,
связывающих две вершины.
При этом дуги, имеющие встречное
направление, обычно рассматриваются
раздельно.
Мощность, как и связность, может
определяться как для каждой пары вершин
графа, так и для некоторой (произвольной)
пары.
Как рассчитывается мощность графа? Какова мощность для невзвешенных
13
графов, для мультиграфов?

14. ХАРАКТЕРИСТИКИ ГРАФА: РАЗМЕРНОСТЬ

Размерность графа определяется общим
количеством вершин и дуг, существующих
в графе.
В одних случаях эта величина определяется
как сумма количеств элементов обоих видов,
в других – как их произведение, а иногда –
как количество элементов только одного
(того или иного) вида.
Рассчитайте размерность для графа несколькими методами
14

15. ПОНЯТИЯ СМЕЖНОСТИ И ИНЦИДЕНТНОСТИ

Если две различные дуги графа инцидентны одной и
той же вершине, то они являются смежными
Каждая дуга (ребро) графа связывает между собой две
вершины, называемые в этом случае смежными.
Матрица инцидентности, Матрица смежности
Граф также можно задать матрицей смежности вершин
V = [vij], в которой vij = вес дуги, если граф содержит
дугу (i,j) и vij = 0 в противном случае
Запишите матрицу смежности для взвешенного ориентированного графа
15

16. ПОДГРАФ, НАДГРАФ, ПОЛНЫЙ ГРАФ

Подграфом ориентированного графа G называется граф,
у которого все вершины и дуги принадлежат G.
Если G1 – подграф графа G, то G называется надграфом
графа G1.
Остовный (частичный) подграф графа G содержит все его
вершины. Например, удаление дуги aj из G приведет к
остовному подграфу, содержащему все дуги графа G, за
исключением aj.
Полным называется граф, любые две вершины которого
соединены ребром. Полный граф с числом вершин p
имеет ½ p (p – 1) ребер.
Цикломатическое число графа = q – p +1
(увеличенная на единицу разность между числом ребер и числом вершин)
16

17. ДВУДОЛЬНЫЙ ГРАФ

Двудольный граф – это граф G, множество вершин V
которого можно разбить на два подмножества V1 и V2
таким образом, что каждое ребро графа G соединяет
вершины из разных множеств (также говорят, что ребра
графа G соединяют множества V1 и V2 ).
Если граф G содержит все ребра, соединяющие
множества V1 и V2 , то этот граф называется полным
двудольным графом.
17

18. ПРИМЕР ДВУДОЛЬНОГО ГРАФА. СЕТИ ПЕТРИ

t1
P1
P4
P2
2
P3
18

19. СЕТИ ПЕТРИ. ВВЕДЕНИЕ

Одним из инструментов моделирования дискретных
процессов, протекающих в производственных системах (ПС),
являются сети Петри и их модификации, включая временные
сети Петри.
Аппарат сетей Петри позволяет описывать параллельные,
асинхронные, иерархические процессы достаточно
простыми средствами. Математическая модель
описываемого сетью Петри процесса достаточно наглядна,
легко алгоритмизируема для моделирования на
компьютерах.
Сети Петри имеют алгебраическую и графическую формы.
Графическое представление сетей нашло большое
применение в силу его наглядности и простоты.
19

20. СЕТИ ПЕТРИ. ВВЕДЕНИЕ

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

21. ИСПОЛЬЗОВАНИЕ СЕТЕЙ ПЕТРИ

Моделирование временными сетями Петри
применяют для различных целей:
• изучение процессов, протекающих в ПС, на предмет
их реализуемости;
• изучение проблем, связанных с использованием
ограниченного количества ресурсов ПС для
выполнения параллельных действий;
• определение пропускной способности ПС;
• определение "узких мест" в ПС;
• получение статистик по загрузке оборудования и
т.д.
21

22. СЕТИ ПЕТРИ. ОСНОВНЫЕ ПОНЯТИЯ

В любой сложной системе можно выделить две составляющих:
1. Условия возникновения событий
2. События
Pn
В сетях Петри условия образуют
множество мест и обозначаются кругами:
tn
События образуют множество переходов
и обозначаются «барьерами»:
Причинно-следственные отношения между условиями-местами и
событиями-переходами изображаются направленными дугами:
P1
t1
P2
t2
…

23. СЕТИ ПЕТРИ. РАЗМЕТКА СЕТИ

Все условия в сети имеют кратность выполнения, т.е. условие может
быть выполнено несколько раз:
Условие выполнено один раз:
Pn
Условие выполнено два раза:
Pn
Условие выполнено m раз:
Pn m
Если для срабатывания перехода требуется
выполнения какого-либо условия несколько раз, то
применяют вес дуги, который ставится над ней:
n
Сети Петри, у которых все дуги имеют вес равный 1, ординарными

24. СЕТИ ПЕТРИ. ДИНАМИКА СЕТИ

Динамика сети Петри представляет собой совокупность действий,
которые называются срабатыванием переходов
Срабатывание перехода – это неделимое действие, которое изменяет
разметку входных и выходных мест сети следующим образом: из
каждого входного места изымается количество маркеров равное весу
дуги, входящей в переход, а в каждое выходное место добавляется
число маркеров равное весу дуги, исходящей из перехода
Переход может сработать в том случае, если ВСЕ предусловия
выполнены

25. СЕТИ ПЕТРИ. ДИНАМИКА СЕТИ

Станок свободен:
P1
Робот свободен:
P2
В накопителе 3 детали:
P3
Станок загружен:
P1
Робот загружен:
P2
В накопителе 1 деталь:
P3
t1
P4
- станок свободен
2
Загрузка
станка
t1
P4
- станок загружен
2
Загрузка
станка

26. СЕТИ ПЕТРИ. ИНГИБИТОРНЫЕ ДУГИ

Ингибиторные дуги применяются для ограничения максимального
числа маркеров, которые могут одновременно находиться в позиции
3
P1
t1
P2
Переход может сработать, только если в P2 не более трех маркеров
3
P1
7
t1
3
P2
P1
4
t1
P2
3

27. СЕТИ ПЕТРИ. АНАЛИТИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ

Сеть Петри:
N = (P, T, F, W, M0)
P – множество мест (позиций)
P = (P1, P2, … , Pn)
P=0
T – множество переходов
T = (T1, T2, … , Tn)
T=0
F – отношения инцидентности F = (P X T) (T X P)
(P, T, F) - конечная сеть. Для неё выполняются следующие условия:
1. Множества мест и переходов не пересекаются (P T= 0)
2. Любой элемент сети инцидентен минимум одному элементу другого типа
3. Сеть не содержит пары мест, которые инцидентны одному и тому же
множеству переходов

28. СЕТИ ПЕТРИ. АНАЛИТИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ

Сеть Петри:
N = (P, T, F, W, M0)
W – кратности дуг
Если кратность равна 1 для всех дуг сети, то такая сеть называется
ординарной
M0 : P N
M0 – начальная разметка сети
t1
t1
P2
2
P1
2
t2
t4
t3
P3
M0(P1) = 1
M0(P2) = 2
M0(P3) = 0
M0 (1, 2, 0)

29. СЕТИ ПЕТРИ. АНАЛИТИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ

P2
t1
t3
2
t2
2
P1
P3
На основании отношений
инцидентности построим матрицы
дуг для данной сети:
n, если W (k, m) F ( k, m )
W (k, m) =
t4
0, если нет дуги
Дуги от tj к Pi :
Дуги от Pj к ti :
P1 P2 P3
t1
t2
t3
t4
t1
1
1
0
P1
1
0
0
0
t2
0
0
1
P2
0
2
0
0
t3
0
2
0
P3
0
0
1
1
t4
1
0
0
29

30. СЕТИ ПЕТРИ. АНАЛИТИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ

P2
t1
t1
2
P1
2
t2
t3
Множество всех маркировок,
достижимых изначальной, называется
множеством достижимости сети Петри
и обозначается R(N)
P3
t4
(1, 2, 0)
t1
(1, 3, 0)
t1
(1, 4, 0)
t1
(1, 5, 0)
t2
t1
(1, 1, 1)
t2
(1, 2, 1)
t1
t2
t3
(1, 2, 0)
t4
(1, 3, 0)
(1, 0, 1)
t4
(1, 1, 1)
t3
(2, 0, 0)
(1, 2, 0)
t1
(2, 1, 0)
(2, 1, 0)30

31. СЕТИ ПЕТРИ. СЕТИ С ПРИОРИТЕТОМ

Для разрешения конфликтных ситуаций при срабатывании переходов в
сетях Петри используют приоритеты.
В конфликтной ситуации в первую очередь срабатывает переход с более
высоким приоритетом.
t3
t1
Переход t1 обладает более
высоким приоритетом, чем t2
П=2
2
Представленная сеть будет
работать бесконечно
t2
П =1
2

32. ВРЕМЕННЫЕ СЕТИ ПЕТРИ. АНАЛИТИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ

Временная сеть Петри:
N = (P, T, F, W, M0, Z)
Z – определяет время задержки маркера
Маркеры в позициях могут находиться в двух состояниях: доступном и
недоступном
t
t
Dt
1
t
2
…
1. Если текущее время t находится в интервале (t < t < t + Dt) – маркер
находится в состоянии «недоступен». Станет доступным при t > t + Dt
2. Переход ti T считается инициированным, если для него выполнено
условие возбуждения (ингибиторные дуги) и в каждой позиции имеется
соответствующее этому условию число доступных маркеров
3. Переход срабатывает мгновенно в момент инициирования
4. Каждый маркер, совершивший переход из Pk в Pn, будет недоступен
позиции Pn в течение времени Zn начиная с момента его появления в Pn, где
Zn – время блокировки позиции

33. ВРЕМЕННЫЕ СЕТИ ПЕТРИ. АНАЛИТИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ

Временная сеть Петри называется детерминированной, если
для нее выполняется условие:
|I(Pi)| = |O(Pi)| = 1, а также если |I(Pi)| > 1 и |O(Pi)| > 1, но конфликты в Pi
однозначно решены текущей маркировкой сети
P2
P1
t1
t2
P4
P3
|I(Pi)| - число входов
в позицию
t3
|O(Pi)| - число
выходов из позиции
Сеть является недетерминированной, если конфликты в Pi не решены

34. СЕТИ ПЕТРИ. СВОЙСТВА СЕТИ

1. Место P сети называется ограниченным, если существует число n,
такое, что для любой достижимой разметки M справедливо неравенство:
M(P) <= n
Сеть называется ограниченной, если все её позиции ограничены
2. Место P сети называется безопасным, если для любой достижимой
разметки M справедливо неравенство:
M(P) <= 1
Сеть называется безопасной, если все её позиции безопасны
3. Сеть, в которой сумма маркеров за всё время работы остается
постоянной, называется консервативной
4. Переход t сети называется потенциально живым, если существует
достижимая из M разметка M’, при которой t может сработать.
Если M = M0, то t называется потенциально живым в сети

35. СЕТИ ПЕТРИ. СВОЙСТВА СЕТИ

5. Переход t называется мертвым при разметке M, если он не является
потенциально живым при M
6. Переход t называется мертвым, если он мертв при любой достижимой
в сети разметке
t
1
t2
t2 – мертвый в сети
7. Переход в сети t называется устойчивым, если он может сработать и
срабатывание любого другого перехода не может лишить его этой
возможности
Сеть N устойчива, если все её переходы устойчивы
t1
t1 и t2 - устойчивы
t2

36.

Е-сети
r1
P1
P2
P3
36

37. E-сети. Основные понятия

Е-сети представляют собой более «жесткий» с точки зрения ограничений
вариант сетей Петри. Дополнительные ограничения позволяют избежать
конфликтов в сети.
Каждой решающей позиции ставится в соответствие некоторый предикат.
rm R (решающая позиция rm принадлежит множеству реш.позиций R)
qm Q(R) (условие срабатывания qm принадлежит множеству условий Q)
t1
t1
В Е-сетях запрещено вхождение в / выход из позиции более одной дуги.
При этом в позиции не бывает более одного маркера

38. E-сети. Основные понятия

Позиция Pi P в сети имеет список переменных (vi1, vi2, …, vis) с помощью
которых характеризуются связанные с позицией условия
Прибытие в позицию маркера означает, что соответствующее условие
выполнено.
Маркер является носителем некоторого конечного числа атрибутов,
которые обозначаются M[L], где L – длина вектора
При попадании маркера в позицию Pi его атрибуты занимают места
переменных (vi1, vi2, …, vis), причем атрибут M[I], где I [1, 2, ... , L]
записывается на место переменной ViI
Если Si < L, то часть атрибутов маркера теряется.
Если Si > L, то часть переменных Vi не будет содержать атрибутов.

39. E-сети. Динамика сети

Каждый переход в E-сетях осуществляется в три фазы:
1. Проверяется условие возбуждения перехода
2. Реализуется задержка времени, и в каждой выходной позиции меняется
маркировка в соответствии с процедурой перехода атрибутов маркера
3. Завершение перехода: маркировка меняется в полном соответствии со
схемой перехода, маркеры удаляются из входных позиций и заносятся в
выходные
Переход в Е-сети записывается тройкой an = (pn, zn, jn)
pn П – тип перехода
zn Z – время выполнения перехода
jn – процедура перехода
П = {T, F, I, X, Y}

40. E-сети. Типы переходов

Переход типа «T»:
P1
t1
Тип
Переход типа «F»:
P1
P2
Схема
t1
Переход типа «I»:
P2
P1
P3
P2
t1
Комментарий
T(P1,P2)
(1, 0)->(0, 1)
Переход осуществляется аналогично сетям
Петри
F(P1,P2, P3)
(1, 0, 0)->(0, 1, 1)
Переход осуществляется аналогично сетям
Петри
I(P1,P2, P3)
(1, 1, 0)->(0, 0, 1)
Переход осуществляется аналогично сетям
Петри
P3

41. E-сети. Типы переходов

Переход типа «X»:
r1
P1
P2
P3
Тип
Схема
X(r1, P1,P2, P3)
(0, 1, 0, 0)->(*, 0, 1, 0)
(1, 1, 0, 0)->(*, 0, 0, 1)
(0, 1, 1, 0)->(*, 0, 1, 1)
(0, 1, 0, 1)->(*, 0, 1, 1)
(1, 1, 1, 0)->(*, 0, 1, 1)
(1, 1, 0, 1)->(*, 0, 1, 1)
Комментарий
Если M(r1) = 0: P1->P2
Если M(r1) = 1: P1->P3
Если нет конфликта, то маркер проходит на
свободную позицию

42. E-сети. Типы переходов

Переход типа «Y»:
r1
P1
P2
Тип
Схема
X(r1, P1,P2, P3)
(0, 1, 1, 0)->(*, 0, 1, 1)
(1, 1, 1, 0)->(*, 1, 0, 1)
(0, 1, 0, 0)->(*, 0, 0, 1)
(0, 0, 1, 0)->(*, 0, 0, 1)
(1, 1, 0, 0)->(*, 0, 0, 1)
(1, 0, 1, 0)->(*, 0, 0, 1)
P3
Комментарий
Если M(r1) = 0: P1->P3
Если M(r1) = 1: P2->P3
Если нет конфликта, то переход
срабатывает на пропуск маркера

43. Е-сети. Аналитическое представление

E-сеть: E = <P, B, R, A, I(A), O(A), Z, V, Q, Y, M0>
P – множество позиций
P = (P1, P2, … , Pn)
B – множество внутренних позиций
B = (B1, B2, … , Bk) P
R – множество решающих позиций
R = (r1, r2, … , rm) P
A – множество переходов
A = (a1, a2, … , an)
I(A), O(A) – функции связи переходов и позиций по входам и выходам
Z: A– >R – функции времени перехода
V – множество переменных
V = (vs1, vs2, … , vsi)
Q – множество решающих процедур
Q = (q1, q2, … , qn)
Y – множество процедур перехода
Y = (y1, y2, … , yn)
M0 – начальная разметка сети
M0 = M0(Pi)
M0(Pi) {0, 1}