Методические указания к выполнению лабораторных работ по курсу "Дискретная математика" пенза 2004 (стр. 3 из 6)
Рис. 5. Граф сети Петри
При выполнении сети Петри получается две последовательности: маркировок
и запущенных переходов 
, которые связаны соотношением 
. Имея последовательность запущенных переходов (маркировок) и 
несложно получить последовательность маркировок (запущенных переходов). Переход может запускаться только в том случае, когда является разрешенным. Переход считается разрешенным, если каждая из его входных позиций имеет число фишек по крайней мере равное числу входных дуг.Функции входов и выходов могут быть представлены матрицами инцидентности
соответственно. Каждая матрица имеет 
– строк и 
– столбцов. Элементы матрицы определяются следующим образом: 
, 
.Пусть
– вектор размерности 
, содержащий нули везде, за исключением 
– компоненты. Переход в маркировке 
разрешен, если выполняется условие 
. Результат запуска перехода 
в маркировке 
определяется формулой: 
,где
– составная матрица изменений маркировок. Для последовательности запусков переходов 
вектор запусков 
определяется соотношением: 
. Элемент вектора 
– число запусков перехода в последовательности 
. При этом смена маркировки определяется соотношением: 
.Множество всех маркировок сети Петри, обладающей
– позициями, есть множество всех – векторов 
. Это множество может быть бесконечным, но всегда счетным.Позиция
маркированной сети называется 
-ограниченной, если для любой маркировки 
, достижимой из 
, 
. Если 
, то позиция называется безопасной. Принято считать, что сеть структурно ограничена, если она ограничена для любой первоначальной маркировки .Сеть Петри консервативна, или S - инвариантна, если существует положительное целое число
, связанное с каждой позицией 
, такое, что сумма маркеров постоянна для любой маркировки 
, достижимой из : 
.Сеть Петри повторяема, если существуют последовательность срабатываний
переходов из такая, что каждый переход срабатывает бесконечное число раз в 
.Сеть Петри непротиворечива, или
- инвариантна, если существуют последовательность срабатываний из в такая, что переход в последовательности запускается по крайней мере один раз.Лабораторное задание
1. Согласуйте с преподавателем вариант структуры и начальной маркировки сети Петри. Постройте граф сети в документе.
2. Определите входную и выходную функции сети Петри, матрицы инцидентности
, вектор начальной маркировки .3. Постройте дерево достижимости сети Петри с использованием матричного способа описания.
4. Определите достижимость маркировки
из начальной маркировки 
и последовательность запусков переходов .5. Исследуйте структурные свойства сети Петри: ограниченность, консервативность, повторяемость и непротиворечивость.
Содержание отчета
Протокол формализованного задания и анализа сети Петри по всем пунктам лабораторного задания средствами системы MathCAD.
Контрольные вопросы
1. Какие используются способы аналитического и графического представления маркированных сетей Петри?
2. Каким образом выполняется смена маркировки и определяется пространство состояний сети Петри?
3. Каким образом осуществляется матричный способ описания выполнения маркированной сети Петри?
4. По каким правилам и в какой последовательности строится дерево достижимости маркированной сети Петри?
5. Какие структурные свойства сети Петри зависят только от топологии и не зависят от начальной маркировки?
Лабораторная работа № 4
ВЕРШИННАЯ И РЕБЕРНАЯ НЕЗАВИСИМОСТИ
Цель работы — исследование внутренней устойчивости ориентированных и неориентированных графов, приобретение практических навыков исследования структур технических систем.
Основные понятия и определения
Множество вершин графа называется независимым (внутренне устойчивым), если никакие две вершины из этого множества несмежны. Независимое множество вершин называется максимальным, если оно не является собственным подмножеством некоторого другого независимого множества. Наибольшее по мощности из максимальных независимых множеств называется наибольшим. Число вершин в наибольшем независимом множестве графа G называется числом независимости (числом внутренней устойчивости, неплотностью) и обозначается через 
(G).
На рис.6 показан граф G, у которого число независимости (G) = 4. Множества вершин {v1, v2, v3, v7}; {v1, v2, v3, v8};{v2, v3, v5, v7} и {v2, v3, v5, v8} являются наибольшими независимыми множествами. Множество вершин {v4, v7} максимальным независимым множеством, но не наибольшим.