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

Август 1, 2022

Главная
Информатика
Методы системного анализа и синтеза: графы и сети Петри

Содержание

2. ГРАФ. ОПРЕДЕЛЕНИЕ Граф есть пара G = 〈V, А 〉, где V – множество вершин v,
3. Полный неориентированный граф Между любыми двумя вершинами есть связь Ориентированный взвешенный граф ОТНОШЕНИЯ И ГРАФЫ Ребрам
4. ОТНОШЕНИЯ И ГРАФЫ Наглядно представлять в виде графов можно различные отношения. Представление отношений с помощью графов
5. ПРИМЕРЫ ГРАФОВ Неориентированный граф с петлей Взвешенный мультиграф Между v1 и v5 две дуги с разным
6. ГРАФЫ ОТНОШЕНИЙ v1 ТИПЫ ОТНОШЕНИЙ Z = {+, −, 0} ВЗАИМНЫЕ v1 v2 + + v1
7. ПУТЬ В ГРАФЕ Путь – термин для ориентированного графа; Цепь – для неориентированного. Путем в графе
8. ПУТЬ В ГРАФЕ Путь называется: простым, если все вершины vi различны; замкнутым, если vi+1 = v1;
9. ПРИМЕРЫ ПУТЕЙ В ГРАФЕ Для графа постройте простой путь, замкнутый путь, полный путь, контур, полный контур.
10. ТУРНИРЫ Ориентированный граф DG = 〈 V, А 〉 называется турниром, если между любыми двумя вершинами
11. ХАРАКТЕРИСТИКИ ГРАФА: СВЯЗНОСТЬ Важным понятием в теории графов является понятие связности. Если для любых двух вершин
12. ПОКАЗАТЕЛЬ СВЯЗНОСТИ Пусть |Rmin | − минимальное число связей, необходимых для связности графа структуры. Если граф
13. ХАРАКТЕРИСТИКИ ГРАФА: МОЩНОСТЬ Мощностью графа называется количество дуг, связывающих две вершины. При этом дуги, имеющие встречное
14. ХАРАКТЕРИСТИКИ ГРАФА: РАЗМЕРНОСТЬ Размерность графа определяется общим количеством вершин и дуг, существующих в графе. В одних
15. ПОНЯТИЯ СМЕЖНОСТИ И ИНЦИДЕНТНОСТИ Если две различные дуги графа инцидентны одной и той же вершине, то
16. ПОДГРАФ, НАДГРАФ, ПОЛНЫЙ ГРАФ Подграфом ориентированного графа G называется граф, у которого все вершины и дуги
17. ДВУДОЛЬНЫЙ ГРАФ Двудольный граф – это граф G, множество вершин V которого можно разбить на два
18. ПРИМЕР ДВУДОЛЬНОГО ГРАФА. СЕТИ ПЕТРИ
19. СЕТИ ПЕТРИ. ВВЕДЕНИЕ Одним из инструментов моделирования дискретных процессов, протекающих в производственных системах (ПС), являются сети
20. СЕТИ ПЕТРИ. ВВЕДЕНИЕ Процесс функционирования ПС отображается как изменения маркировки сети Петри, представляющей данную ПС. Маркировка
21. ИСПОЛЬЗОВАНИЕ СЕТЕЙ ПЕТРИ Моделирование временными сетями Петри применяют для различных целей: изучение процессов, протекающих в ПС,
22. СЕТИ ПЕТРИ. ОСНОВНЫЕ ПОНЯТИЯ В любой сложной системе можно выделить две составляющих: Условия возникновения событий События
23. СЕТИ ПЕТРИ. РАЗМЕТКА СЕТИ Условие выполнено один раз: Pn Все условия в сети имеют кратность выполнения,
24. СЕТИ ПЕТРИ. ДИНАМИКА СЕТИ Динамика сети Петри представляет собой совокупность действий, которые называются срабатыванием переходов Переход
25. СЕТИ ПЕТРИ. ДИНАМИКА СЕТИ Станок свободен: t1 Робот свободен: В накопителе 3 детали: P1 P3 P2
26. СЕТИ ПЕТРИ. ИНГИБИТОРНЫЕ ДУГИ t1 Переход может сработать, только если в P2 не более трех маркеров
27. СЕТИ ПЕТРИ. АНАЛИТИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ Сеть Петри: N = (P, T, F, W, M0) 1. Множества мест
28. СЕТИ ПЕТРИ. АНАЛИТИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ Сеть Петри: N = (P, T, F, W, M0) W – кратности
29. СЕТИ ПЕТРИ. АНАЛИТИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ На основании отношений инцидентности построим матрицы дуг для данной сети: W (k,
30. СЕТИ ПЕТРИ. АНАЛИТИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ Множество всех маркировок, достижимых изначальной, называется множеством достижимости сети Петри и обозначается
31. СЕТИ ПЕТРИ. СЕТИ С ПРИОРИТЕТОМ Переход t1 обладает более высоким приоритетом, чем t2 Представленная сеть будет
32. ВРЕМЕННЫЕ СЕТИ ПЕТРИ. АНАЛИТИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ Временная сеть Петри: N = (P, T, F, W, M0, Z)
33. ВРЕМЕННЫЕ СЕТИ ПЕТРИ. АНАЛИТИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ Временная сеть Петри называется детерминированной, если для нее выполняется условие: |I(Pi)|
34. СЕТИ ПЕТРИ. СВОЙСТВА СЕТИ 1. Место P сети называется ограниченным, если существует число n, такое, что
35. СЕТИ ПЕТРИ. СВОЙСТВА СЕТИ 5. Переход t называется мертвым при разметке M, если он не является
36. Е-сети
37. E-сети. Основные понятия Е-сети представляют собой более «жесткий» с точки зрения ограничений вариант сетей Петри. Дополнительные
38. E-сети. Основные понятия Прибытие в позицию маркера означает, что соответствующее условие выполнено. При попадании маркера в
39. E-сети. Динамика сети 1. Проверяется условие возбуждения перехода 2. Реализуется задержка времени, и в каждой выходной
40. E-сети. Типы переходов Переход типа «T»: t1 P1 P2 t1 P1 P2 P3 t1 P2 P3
41. E-сети. Типы переходов r1 P2 P3 P1 Переход типа «X»:
42. E-сети. Типы переходов r1 P2 P3 P1 Переход типа «Y»:
44. Скачать презентацию

Слайд 2

ГРАФ. ОПРЕДЕЛЕНИЕ
Граф есть пара
G = 〈V, А 〉,
где

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

Слайд 3

Полный неориентированный граф
Между любыми двумя
вершинами есть связь
Ориентированный взвешенный граф
ОТНОШЕНИЯ

И ГРАФЫ

Ребрам графа можно приписывать:
знаки (знаковые графы);
числа (взвешенные графы).

Ориентированный граф с изолированной вершиной

Слайд 4

ОТНОШЕНИЯ И ГРАФЫ
Наглядно представлять в виде графов можно различные отношения.
Представление отношений

с помощью графов выражает следующие их свойства:

Слайд 5

ПРИМЕРЫ ГРАФОВ
Неориентированный граф с петлей
Взвешенный мультиграф
Между v1 и v5 две дуги

с разным весом

Слайд 6

ГРАФЫ ОТНОШЕНИЙ
v1
ТИПЫ ОТНОШЕНИЙ Z = {+, −, 0}
ВЗАИМНЫЕ
v1
v2
+
+
v1
v2
−
−
СЛАБОКОНТРАСТНЫЕ
0
0
v1
v2
v1
v2
+
−
v2
−
+
КОНТРАСТНЫЕ
v2
v2

+
0

0
+

−
0

0
−

Ориентированные знаковые графы

Слайд 7

ПУТЬ В ГРАФЕ
Путь – термин для ориентированного графа;
Цепь – для неориентированного.
Путем

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

Слайд 8

ПУТЬ В ГРАФЕ
Путь называется:
простым, если все вершины vi различны;
замкнутым, если vi+1

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

Слайд 9

ПРИМЕРЫ ПУТЕЙ В ГРАФЕ
Для графа постройте простой путь, замкнутый путь, полный

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

Слайд 10

ТУРНИРЫ
Ориентированный граф DG = 〈 V, А 〉 называется турниром, если

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

Слайд 11

ХАРАКТЕРИСТИКИ ГРАФА: СВЯЗНОСТЬ
Важным понятием в теории графов является понятие связности.
Если

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

Является ли граф связным, рассчитайте количественную характеристику связности

Слайд 12

ПОКАЗАТЕЛЬ СВЯЗНОСТИ
Пусть |Rmin | − минимальное число связей, необходимых для связности

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

Каково минимальное количество вершин для графа?
Рассчитайте меру избыточности структуры по связям

Слайд 13

ХАРАКТЕРИСТИКИ ГРАФА: МОЩНОСТЬ
Мощностью графа называется количество дуг, связывающих две вершины.
При

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

Как рассчитывается мощность графа? Какова мощность для невзвешенных графов, для мультиграфов?

Слайд 14

ХАРАКТЕРИСТИКИ ГРАФА: РАЗМЕРНОСТЬ
Размерность графа определяется общим
количеством вершин и дуг, существующих

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

Рассчитайте размерность для графа несколькими методами

Слайд 15

ПОНЯТИЯ СМЕЖНОСТИ И ИНЦИДЕНТНОСТИ
Если две различные дуги графа инцидентны одной и

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

Запишите матрицу смежности для взвешенного ориентированного графа

Слайд 16

ПОДГРАФ, НАДГРАФ, ПОЛНЫЙ ГРАФ
Подграфом ориентированного графа G называется граф, у которого

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

Слайд 17

ДВУДОЛЬНЫЙ ГРАФ
Двудольный граф – это граф G, множество вершин V которого

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

Слайд 18

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

Слайд 19

СЕТИ ПЕТРИ. ВВЕДЕНИЕ
Одним из инструментов моделирования дискретных процессов, протекающих в производственных

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

Слайд 20

СЕТИ ПЕТРИ. ВВЕДЕНИЕ
Процесс функционирования ПС отображается как изменения маркировки сети Петри,

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

Слайд 21

ИСПОЛЬЗОВАНИЕ СЕТЕЙ ПЕТРИ
Моделирование временными сетями Петри применяют для различных целей:
изучение процессов,

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

Слайд 22

СЕТИ ПЕТРИ. ОСНОВНЫЕ ПОНЯТИЯ
В любой сложной системе можно выделить две

составляющих:
Условия возникновения событий
События

В сетях Петри условия образуют множество мест и обозначаются кругами:

События образуют множество переходов и обозначаются «барьерами»:

Причинно-следственные отношения между условиями-местами и событиями-переходами изображаются направленными дугами:

…

Слайд 23

СЕТИ ПЕТРИ. РАЗМЕТКА СЕТИ
Условие выполнено один раз:
Pn
Все условия в сети

имеют кратность выполнения, т.е. условие может быть выполнено несколько раз:

Условие выполнено два раза:

Условие выполнено m раз:

Если для срабатывания перехода требуется выполнения какого-либо условия несколько раз, то применяют вес дуги, который ставится над ней:

Сети Петри, у которых все дуги имеют вес равный 1, ординарными

Слайд 24

СЕТИ ПЕТРИ. ДИНАМИКА СЕТИ
Динамика сети Петри представляет собой совокупность действий,

которые называются срабатыванием переходов

Переход может сработать в том случае, если ВСЕ предусловия выполнены

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

Слайд 25

СЕТИ ПЕТРИ. ДИНАМИКА СЕТИ
Станок свободен:
t1
Робот свободен:
В накопителе 3 детали:
P1
P3
P2
Загрузка станка
2
P4
-

станок свободен

Станок загружен:

Робот загружен:

В накопителе 1 деталь:

Загрузка станка

- станок загружен

Слайд 26

СЕТИ ПЕТРИ. ИНГИБИТОРНЫЕ ДУГИ
t1
Переход может сработать, только если в P2

не более трех маркеров

Ингибиторные дуги применяются для ограничения максимального числа маркеров, которые могут одновременно находиться в позиции

Слайд 27

СЕТИ ПЕТРИ. АНАЛИТИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ
Сеть Петри: N = (P, T, F,

W, M0)

1. Множества мест и переходов не пересекаются (P мьT= 0)

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) - конечная сеть. Для неё выполняются следующие условия:

2. Любой элемент сети инцидентен минимум одному элементу другого типа

3. Сеть не содержит пары мест, которые инцидентны одному и тому же множеству переходов

Слайд 28

СЕТИ ПЕТРИ. АНАЛИТИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ
Сеть Петри: N = (P, T, F,

W, M0)

W – кратности дуг

Если кратность равна 1 для всех дуг сети, то такая сеть называется ординарной

M0 – начальная разметка сети M0: P Ю N

M0(P1) = 1
M0(P2) = 2
M0(P3) = 0
M0 (1, 2, 0)

Слайд 29

СЕТИ ПЕТРИ. АНАЛИТИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ
На основании отношений инцидентности построим матрицы дуг

для данной сети:

W (k, m) =

n, если W (k, m) мь F ( k, m )

0, если нет дуги

Дуги от Pj к ti :

Дуги от tj к Pi :

Слайд 30

СЕТИ ПЕТРИ. АНАЛИТИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ
Множество всех маркировок, достижимых изначальной, называется множеством

достижимости сети Петри и обозначается R(N)

(1, 2, 0)

(1, 4, 0)

(1, 3, 0)

(1, 5, 0)

(1, 2, 0)

(1, 1, 1)

(1, 0, 1)

(1, 2, 1)

(1, 1, 1)

(2, 1, 0)

(1, 2, 0)

(2, 0, 0)

(2, 1, 0)

(1, 3, 0)

Слайд 31

СЕТИ ПЕТРИ. СЕТИ С ПРИОРИТЕТОМ
Переход t1 обладает более высоким приоритетом,

чем t2
Представленная сеть будет работать бесконечно

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

Слайд 32

ВРЕМЕННЫЕ СЕТИ ПЕТРИ. АНАЛИТИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ
Временная сеть Петри: N = (P,

T, F, W, M0, Z)

1. Если текущее время t находится в интервале (τ < t < τ + Δt) – маркер находится в состоянии «недоступен». Станет доступным при t > t + Δt

Z – определяет время задержки маркера

Маркеры в позициях могут находиться в двух состояниях: доступном и недоступном

2. Переход ti Н T считается инициированным, если для него выполнено условие возбуждения (ингибиторные дуги) и в каждой позиции имеется соответствующее этому условию число доступных маркеров

3. Переход срабатывает мгновенно в момент инициирования

4. Каждый маркер, совершивший переход из Pk в Pn, будет недоступен позиции Pn в течение времени Zn начиная с момента его появления в Pn, где Zn – время блокировки позиции

…

Δt

Слайд 33

ВРЕМЕННЫЕ СЕТИ ПЕТРИ. АНАЛИТИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ
Временная сеть Петри называется детерминированной, если

для нее выполняется условие:

|I(Pi)| = |O(Pi)| = 1, а также если |I(Pi)| > 1 и |O(Pi)| > 1, но конфликты в Pi однозначно решены текущей маркировкой сети

|O(Pi)| - число выходов из позиции

|I(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 называется мертвым, если он мертв при любой достижимой в сети разметке

7. Переход в сети t называется устойчивым, если он может сработать и срабатывание любого другого перехода не может лишить его этой возможности
Сеть N устойчива, если все её переходы устойчивы

t1 и t2 - устойчивы

t2 – мертвый в сети

Слайд 36

Е-сети

Слайд 37

E-сети. Основные понятия
Е-сети представляют собой более «жесткий» с точки зрения

ограничений вариант сетей Петри. Дополнительные ограничения позволяют избежать конфликтов в сети.

В Е-сетях запрещено вхождение в / выход из позиции более одной дуги. При этом в позиции не бывает более одного маркера

Каждой решающей позиции ставится в соответствие некоторый предикат.
rm О R (решающая позиция rm принадлежит множеству реш.позиций R)
qm О Q(R) (условие срабатывания qm принадлежит множеству условий Q)

Слайд 38

E-сети. Основные понятия
Прибытие в позицию маркера означает, что соответствующее условие

выполнено.

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

Маркер является носителем некоторого конечного числа атрибутов, которые обозначаются M[L], где L – длина вектора

Позиция Pi О P в сети имеет список переменных (vi1, vi2, …, vis) с помощью которых характеризуются связанные с позицией условия

Слайд 39

E-сети. Динамика сети
1. Проверяется условие возбуждения перехода
2. Реализуется задержка времени,

и в каждой выходной позиции меняется маркировка в соответствии с процедурой перехода атрибутов маркера

Каждый переход в E-сетях осуществляется в три фазы:

3. Завершение перехода: маркировка меняется в полном соответствии со схемой перехода, маркеры удаляются из входных позиций и заносятся в выходные

Переход в Е-сети записывается тройкой an = (πn, zn, ϕn)

πn О П – тип перехода П = {T, F, I, X, Y}

zn О Z – время выполнения перехода

ϕn – процедура перехода

Слайд 40

E-сети. Типы переходов
Переход типа «T»:
t1
P1
P2
t1
P1
P2
P3
t1
P2
P3
P1
Переход типа «F»:
Переход типа «I»:

Слайд 41

E-сети. Типы переходов
r1
P2
P3
P1
Переход типа «X»:

Слайд 42

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

Содержание

ГРАФ. ОПРЕДЕЛЕНИЕ Граф есть пара G = 〈V, А 〉, где

Полный неориентированный граф Между любыми двумя вершинами есть связьОриентированный взвешенный графОТНОШЕНИЯ

ОТНОШЕНИЯ И ГРАФЫНаглядно представлять в виде графов можно различные отношения.Представление отношений

ПРИМЕРЫ ГРАФОВНеориентированный граф с петлейВзвешенный мультиграфМежду v1 и v5 две дуги

ГРАФЫ ОТНОШЕНИЙv1ТИПЫ ОТНОШЕНИЙ Z = {+, −, 0} ВЗАИМНЫЕv1v2++ v1v2−−СЛАБОКОНТРАСТНЫЕ00v1v2v1v2+−v2−+ КОНТРАСТНЫЕv2v2

ПУТЬ В ГРАФЕПуть – термин для ориентированного графа;Цепь – для неориентированного.Путем

ПУТЬ В ГРАФЕПуть называется:простым, если все вершины vi различны;замкнутым, если vi+1

ПРИМЕРЫ ПУТЕЙ В ГРАФЕДля графа постройте простой путь, замкнутый путь, полный

ТУРНИРЫОриентированный граф DG = 〈 V, А 〉 называется турниром, если

ХАРАКТЕРИСТИКИ ГРАФА: СВЯЗНОСТЬВажным понятием в теории графов является понятие связности. Если

ПОКАЗАТЕЛЬ СВЯЗНОСТИПусть |Rmin | − минимальное число связей, необходимых для связности

ХАРАКТЕРИСТИКИ ГРАФА: МОЩНОСТЬМощностью графа называется количество дуг, связывающих две вершины. При

ХАРАКТЕРИСТИКИ ГРАФА: РАЗМЕРНОСТЬРазмерность графа определяется общим количеством вершин и дуг, существующих

ПОНЯТИЯ СМЕЖНОСТИ И ИНЦИДЕНТНОСТИЕсли две различные дуги графа инцидентны одной и

ПОДГРАФ, НАДГРАФ, ПОЛНЫЙ ГРАФПодграфом ориентированного графа G называется граф, у которого

ДВУДОЛЬНЫЙ ГРАФДвудольный граф – это граф G, множество вершин V которого

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

СЕТИ ПЕТРИ. ВВЕДЕНИЕОдним из инструментов моделирования дискретных процессов, протекающих в производственных

СЕТИ ПЕТРИ. ВВЕДЕНИЕПроцесс функционирования ПС отображается как изменения маркировки сети Петри,

ИСПОЛЬЗОВАНИЕ СЕТЕЙ ПЕТРИМоделирование временными сетями Петри применяют для различных целей:изучение процессов,

СЕТИ ПЕТРИ. ОСНОВНЫЕ ПОНЯТИЯ В любой сложной системе можно выделить две

СЕТИ ПЕТРИ. РАЗМЕТКА СЕТИ Условие выполнено один раз:PnВсе условия в сети

СЕТИ ПЕТРИ. ДИНАМИКА СЕТИ Динамика сети Петри представляет собой совокупность действий,

СЕТИ ПЕТРИ. ДИНАМИКА СЕТИ Станок свободен:t1Робот свободен:В накопителе 3 детали:P1P3P2Загрузка станка2P4-

СЕТИ ПЕТРИ. ИНГИБИТОРНЫЕ ДУГИ t1Переход может сработать, только если в P2

СЕТИ ПЕТРИ. АНАЛИТИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ Сеть Петри: N = (P, T, F,

СЕТИ ПЕТРИ. АНАЛИТИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ Сеть Петри: N = (P, T, F,

СЕТИ ПЕТРИ. АНАЛИТИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ На основании отношений инцидентности построим матрицы дуг

СЕТИ ПЕТРИ. АНАЛИТИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ Множество всех маркировок, достижимых изначальной, называется множеством

СЕТИ ПЕТРИ. СЕТИ С ПРИОРИТЕТОМ Переход t1 обладает более высоким приоритетом,

ВРЕМЕННЫЕ СЕТИ ПЕТРИ. АНАЛИТИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ Временная сеть Петри: N = (P,

ВРЕМЕННЫЕ СЕТИ ПЕТРИ. АНАЛИТИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ Временная сеть Петри называется детерминированной, если

СЕТИ ПЕТРИ. СВОЙСТВА СЕТИ 1. Место P сети называется ограниченным, если

СЕТИ ПЕТРИ. СВОЙСТВА СЕТИ 5. Переход t называется мертвым при разметке

Е-сети

E-сети. Основные понятия Е-сети представляют собой более «жесткий» с точки зрения

E-сети. Основные понятия Прибытие в позицию маркера означает, что соответствующее условие

E-сети. Динамика сети 1. Проверяется условие возбуждения перехода2. Реализуется задержка времени,

E-сети. Типы переходов Переход типа «T»:t1P1P2t1P1P2P3t1P2P3P1Переход типа «F»:Переход типа «I»:

E-сети. Типы переходов r1P2P3P1Переход типа «X»:

E-сети. Типы переходов r1P2P3P1Переход типа «Y»:

Похожие презентации

ГРАФ. ОПРЕДЕЛЕНИЕ
Граф есть пара
G = 〈V, А 〉,
где

Полный неориентированный граф
Между любыми двумя
вершинами есть связь
Ориентированный взвешенный граф
ОТНОШЕНИЯ

ОТНОШЕНИЯ И ГРАФЫ
Наглядно представлять в виде графов можно различные отношения.
Представление отношений

ПРИМЕРЫ ГРАФОВ
Неориентированный граф с петлей
Взвешенный мультиграф
Между v1 и v5 две дуги

ГРАФЫ ОТНОШЕНИЙ
v1
ТИПЫ ОТНОШЕНИЙ Z = {+, −, 0}
ВЗАИМНЫЕ
v1
v2
+
+
v1
v2
−
−
СЛАБОКОНТРАСТНЫЕ
0
0
v1
v2
v1
v2
+
−
v2
−
+
КОНТРАСТНЫЕ
v2
v2

ПУТЬ В ГРАФЕ
Путь – термин для ориентированного графа;
Цепь – для неориентированного.
Путем

ПУТЬ В ГРАФЕ
Путь называется:
простым, если все вершины vi различны;
замкнутым, если vi+1

ПРИМЕРЫ ПУТЕЙ В ГРАФЕ
Для графа постройте простой путь, замкнутый путь, полный

ТУРНИРЫ
Ориентированный граф DG = 〈 V, А 〉 называется турниром, если

ХАРАКТЕРИСТИКИ ГРАФА: СВЯЗНОСТЬ
Важным понятием в теории графов является понятие связности.
Если

ПОКАЗАТЕЛЬ СВЯЗНОСТИ
Пусть |Rmin | − минимальное число связей, необходимых для связности

ХАРАКТЕРИСТИКИ ГРАФА: МОЩНОСТЬ
Мощностью графа называется количество дуг, связывающих две вершины.
При

ХАРАКТЕРИСТИКИ ГРАФА: РАЗМЕРНОСТЬ
Размерность графа определяется общим
количеством вершин и дуг, существующих

ПОНЯТИЯ СМЕЖНОСТИ И ИНЦИДЕНТНОСТИ
Если две различные дуги графа инцидентны одной и

ПОДГРАФ, НАДГРАФ, ПОЛНЫЙ ГРАФ
Подграфом ориентированного графа G называется граф, у которого

ДВУДОЛЬНЫЙ ГРАФ
Двудольный граф – это граф G, множество вершин V которого

СЕТИ ПЕТРИ. ВВЕДЕНИЕ
Одним из инструментов моделирования дискретных процессов, протекающих в производственных

СЕТИ ПЕТРИ. ВВЕДЕНИЕ
Процесс функционирования ПС отображается как изменения маркировки сети Петри,

ИСПОЛЬЗОВАНИЕ СЕТЕЙ ПЕТРИ
Моделирование временными сетями Петри применяют для различных целей:
изучение процессов,

СЕТИ ПЕТРИ. ОСНОВНЫЕ ПОНЯТИЯ
В любой сложной системе можно выделить две

СЕТИ ПЕТРИ. РАЗМЕТКА СЕТИ
Условие выполнено один раз:
Pn
Все условия в сети

СЕТИ ПЕТРИ. ДИНАМИКА СЕТИ
Динамика сети Петри представляет собой совокупность действий,

СЕТИ ПЕТРИ. ДИНАМИКА СЕТИ
Станок свободен:
t1
Робот свободен:
В накопителе 3 детали:
P1
P3
P2
Загрузка станка
2
P4
-

СЕТИ ПЕТРИ. ИНГИБИТОРНЫЕ ДУГИ
t1
Переход может сработать, только если в P2

СЕТИ ПЕТРИ. АНАЛИТИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ
Сеть Петри: N = (P, T, F,

СЕТИ ПЕТРИ. АНАЛИТИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ
Сеть Петри: N = (P, T, F,

СЕТИ ПЕТРИ. АНАЛИТИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ
На основании отношений инцидентности построим матрицы дуг

СЕТИ ПЕТРИ. АНАЛИТИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ
Множество всех маркировок, достижимых изначальной, называется множеством

СЕТИ ПЕТРИ. СЕТИ С ПРИОРИТЕТОМ
Переход t1 обладает более высоким приоритетом,

ВРЕМЕННЫЕ СЕТИ ПЕТРИ. АНАЛИТИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ
Временная сеть Петри: N = (P,

ВРЕМЕННЫЕ СЕТИ ПЕТРИ. АНАЛИТИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ
Временная сеть Петри называется детерминированной, если

СЕТИ ПЕТРИ. СВОЙСТВА СЕТИ
1. Место P сети называется ограниченным, если

СЕТИ ПЕТРИ. СВОЙСТВА СЕТИ
5. Переход t называется мертвым при разметке

E-сети. Основные понятия
Е-сети представляют собой более «жесткий» с точки зрения

E-сети. Основные понятия
Прибытие в позицию маркера означает, что соответствующее условие

E-сети. Динамика сети
1. Проверяется условие возбуждения перехода
2. Реализуется задержка времени,

E-сети. Типы переходов
Переход типа «T»:
t1
P1
P2
t1
P1
P2
P3
t1
P2
P3
P1
Переход типа «F»:
Переход типа «I»:

E-сети. Типы переходов
r1
P2
P3
P1
Переход типа «X»:

E-сети. Типы переходов
r1
P2
P3
P1
Переход типа «Y»: