Задача 1. Элементы теории графов
Связный ориентированный граф G (Х , Г) задан множеством вершин X ={ x 1 , x 2 ,…,xn } и отображением Г xi ={ x | I ± k | ,x | I ± l | } ,i =1 , 2 ,… ,n . Здесь i - текущий номер вершины, n- количество вершин графа. Значение индексов n , k и l возьмем из табл.1 в соответствии с номером варианта. Индексы k и l формируют значения индексов a ,b , g … переменной x в отображении Г xi = { x a ,x b ,x g ,…} . Если значения индексов a , b ,g … переменной x не соответствуют ни одному из номеров вершин графа, то эта переменная не учитывается во множестве Г xi .
Выполнить следующие действия:
а) определить исходный граф и ассоциированный с ним неориентированный граф графическим, матричным и аналитическим способами;
б) установить центры и периферийные вершины графов, найти радиусы и диаметры графов;
в) выделить в ориентированном графе два подграфа. Найти объединение, пересечение и разность подграфов;
г) описать систему уравнений, соответствующую сигнальному графу, считая, что передача между вершинами xi и xj
i*j
при i
³
j
;
Kij =
1/ ( p +1) при i < j .
Найти передачу между вершинами x 1 и xn , используя правило Мезона. Построить структуру кибернетической системы, определяемой топологией графа;
Таблица 1
№ варианта |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| N | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 6 | 6 | 6 | 6 | 6 | 6 |
| K | 2 | 3 | 4 | 1 | 1 | 1 | 3 | 5 | 2 | 4 | 2 | 3 | 4 | 5 | 6 |
| L | 1 | 1 | 1 | 2 | 3 | 4 | 2 | 1 | 3 | 3 | 1 | 1 | 1 | 1 | 1 |
№ варианта |
16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |
| N | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 7 | 7 | 7 | 7 | 7 | 7 |
| K | 1 | 1 | 1 | 1 | 3 | 2 | 5 | 5 | 2 | 3 | 4 | 5 | 6 | 5 | 3 |
| L | 2 | 3 | 4 | 5 | 2 | 3 | 2 | 3 | 3 | 2 | 3 | 2 | 1 | 3 | 5 |
Решение:
Множество вершин
X = { x 1 , x 2 ,x 3 , x 4 , x 5 , x 6 }, n = 6 k = 2, l = 1 Г xi ={ x | I ± k | ,x | I ± l | }.
а) определим исходный граф и ассоциированный с ним неориентированный граф графическим, матричным и аналитическим способами:
Определим граф аналитическим способом:
Г x 1 = { x 1 , x 3 , x 2 };
Г x 2 = { x 4 , x 1 , x 3 };
Г x 3 = { x 1 , x 5 , x 2 , x 4 };
Г x 4 = { x 2 , x 6 , x 3 , x 5 };
Г x 5 = { x3 , x 4 , x 6 };
Г x 6 = { x4 ,x 5 }.
Ориентированный граф графическим способом:
Неориентированный граф графическим способом:
Ориентированный граф матричным способом:
RG
- матрица смежности 
| x1 | x2 | x3 | x4 | x5 | x6 | |
| x1 | 1* | 1 | 1 | 0 | 0 | 0 |
| x2 | 1 | 0 | 1 | 1 | 0 | 0 |
| x3 | 1 | 1 | 0 | 1 | 1 | 0 |
| x4 | 0 | 1 | 1 | 0 | 1 | 1 |
| x5 | 0 | 0 | 1 | 1 | 0 | 1 |
| x6 | 0 | 0 | 0 | 1 | 1 | 0 |
AG
- матрица инцидентности 
| v1 | v2 | v3 | v4 | v5 | v6 | v7 | v8 | v9 | v10 | v11 | v12 | v13 | v14 | v15 | v16 | v17 | v18 | v19 | |
| x1 | 1* | 1 | -1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | -1 | 0 | 0 | 0 | 0 | 0 | 0 |
| x2 | 0 | -1 | 1 | 1 | -1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | -1 | 0 | 0 | 0 | 0 |
| x3 | 0 | 0 | 0 | -1 | 1 | 1 | -1 | 0 | 0 | 0 | 0 | -1 | 1 | 0 | 0 | 1 | -1 | 0 | 0 |
| x4 | 0 | 0 | 0 | 0 | 0 | -1 | 1 | 1 | -1 | 0 | 0 | 0 | 0 | -1 | 1 | 0 | 0 | 1 | -1 |
| x5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | 1 | 1 | -1 | 0 | 0 | 0 | 0 | -1 | 1 | 0 | 0 |
| x6 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | 1 |
Неориентированный граф матричным способом:
RD - матрица смежности
| x1 | x2 | x3 | x4 | x5 | x6 | |
| x1 | 1* | 2 | 2 | 0 | 0 | 0 |
| x2 | 2 | 0 | 2 | 2 | 0 | 0 |
| x3 | 2 | 2 | 0 | 2 | 2 | 0 |
| x4 | 0 | 2 | 2 | 0 | 2 | 2 |
| x5 | 0 | 0 | 2 | 2 | 0 | 2 |
| x6 | 0 | 0 | 0 | 2 | 2 | 0 |
AD - матрица инцидентности
| v1 | v2 | v3 | v4 | v5 | v6 | v7 | v8 | v9 | v10 | v11 | v12 | v13 | v14 | v15 | v16 | v17 | v18 | v19 | |
| x1 | 1* | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| x2 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
| x3 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 |
| x4 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| x5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
| x6 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
б) установить центры и периферийные вершины графов, найти радиусы и диаметры графов:
- матрица отклонений имеет вид:
| x1 | x2 | x3 | x4 | x5 | x6 | |
| x1 | 1 | 1 | 1 | 2 | 2 | 3 |
| x2 | 1 | 0 | 1 | 1 | 2 | 2 |
| x3 | 1 | 1 | 0 | 1 | 1 | 2 |
| x4 | 2 | 1 | 1 | 0 | 1 | 1 |
| x5 | 2 | 2 | 1 | 1 | 0 | 1 |
| x6 | 3 | 2 | 2 | 1 | 1 | 0 |
- вектор отклонения
=>
х2 , х3 , х4 , х5 - центры графа с наименьшей удаленностью. Радиус ρ (G) = 2.
Периферийными вершинами являются вершины х1 , х6 с наибольшей удаленностью. Диаметр графа D (G) = 3.
в) выделим в ориентированном графе два подграфа и найдем объединение, пересечение и разность подграфов.
Выделяем два подграфа: G 1 и G 2
X 1 - { x 1 , x 2 }, Г1х1 = { x 1 , x 2 }, Г1х2 = { x 1 },
X 2 - { x 1 , x 2 , x 3 }, Г2х1 = { x 2 }, Г2х2 = { x 3 }, Г2х3 = { x 2 } .
Объединение 
,
,
, 
, 
.
G
Пересечение
,
,
, 
.
G
Разность
,
, 
, 
.
G
г) Считая, что передача между вершинами xi и xj
i*j
при i
³
j
;
Kij =
1/ ( p +1) при i < j .
Сигнальный граф имеет вид
Система уравнений, соответствующая сигнальному графу имеет вид
x 1 = x 1 +2 x 2 +3 x 3
x
2
=
x
1
+6
x
3
+8
x
4
x
3
=
x
1
+
x
2
+12
x
4
+15
x
5
x
4
=
x
2
+
x
3
+20
x
5
+24
x
6
x
5
=
x
3
+
x
4
+30
x
6
x
6
=
x
4
+
x
5
Определить передачу k 16 по правилу Мезона. Формула Мезона имеет вид
PS - передача пути,
DS - алгебраическое дополнение,
D - определитель.
Пути из х1 в х6 и передаточные функции для каждого из них имеют вид:
Контура:
;
;
;
;
;
;
;
;
;
;
;
;
;
.
;
.
Пары несоприкасающихся контуров
L 1 L 3 , L 1 L 4 , L 1 L 5 , L 1 L 6 , L 1 L 8 , L 1 L 9 , L 1 L 10 , L 1 L 13 , L 1 L 14 , L 1 L 15 , L 1 L 16 , L 1 L 17 , L 1 L 18 ;
L 2 L 4 , L 2 L 5 , L 2 L 6 , L 2 L 8 , L 2 L 9 , L 2 L 10 , L 2 L 15 , L 2 L 16 , L 2 L 17 , L 2 L 18 ;
L 3 L 5 , L 3 L 6 , L 3 L 10 , L 3 L 17 , L 3 L 18 ;
L 4 L 6 , L 5 L 7 ; L 5 L 11 , L 5 L 12 , L 6 L 7 , L 6 L 8 , L 6 L 11 , L 6 L 12 , L 6 L 13 , L 6 L 14 ;
L 7 L 8 , L 7 L 10 , L 7 L 17 , L 7 L 18 ;
L 8 L 9 , L 9 L 10 , L 10 L 11 , L 10 L 12 , L 11 L 17 , L 11 L 18 , L 12 L 17 , L 12 L 18 .
Независимые тройки
L 1 L 3 L 5 ,L 1 L 3 L 6 ,L 1 L 3 L 10 ,L 1 L 3 L 17 ,L 1 L 3 L 18 ,L 1 L 4 L 6 ,L 1 L 6 L 8 ,L 1 L 6 L 13 ,L 1 L 6 L 14 ,L 1 L 8 L 9, L 1 L9 L10 ,L2 L 4 L6 ,L2 L9 L10 ,L6 L7 L 8 .
Отсюда
D = 1 - ( L 1 +L 2 +L 3 +L 4 +L 5 + L 6 +L 7 +L 8 +L 9 +L 10 +L 11 +L 12 +
+ L 13 +L 14 + L 15 +L 16 + L 17 +L 18 )+ ( L 1 L 3 +L 1 L 4 +L 1 L 5 +L 1 L 6 +L 1 L 8 +L 1 L 9 +L 1 L 10 +L 1 L 13 +L 1 L 14 +L 1 L 15 +L 1 L 16 +L 1 L 17 +L 1 L 18 +L 2 L 4 +L 2 L 5 +L 2 L 6 +L 2 L 8 +L 2 L 9 +L 2 L 10 +L 2 L 15 +L 2 L 16 +L 2 L 17 +L 2 L 18 + L 3 L 5 +L 3 L 6 +L 3 L 10 +L 3 L 17 +L 3 L 18 L 4 L 6 +L 5 L 7 +L 5 L 11 +L 5 L 12 +L 6 L 7 +L 6 L 8 +L 6 L 11 +L 6 L 12 +L 6 L 13 +L 6 L 14 +L 7 L 8 +L 7 L 10 +L 7 L 17 +L 7 L 18 +L 8 L 9 +L 9 L 10 +L 10 L 11 +L 10 L 12 +L 11 L 17 +L 11 L 18 +L 12 L 17 +L 12 L 18 ) -
( L 1 L 3 L 5 +L 1 L 3 L 6 +L 1 L 3 L 10 +L 1 L 3 L 17 +L 1 L 3 L 18 +L 1 L 4 L 6 +L 1 L 6 L 8 +L 1 L 6 L 13 +L 1 L 6 L 14 +L 1 L 8 L 9 +L 1 L 9 L 10 +L 2 L 4 L 6 +L 2 L 9 L 10 +L 6 L 7 L 8 ) .
D 1 = 1- L 8 ;
D 2 = 1;
D 3 = 1;
D 4 = 1 - L 9 ;
D 5 = 1;
D 6 = 1.
.
Структура кинематической системы представлена на рисунке:
Задача 2. Задача о максимальном потоке и потоке минимальной стоимости
Транспортная сеть задана в виде ориентированного графа, приведенного на рисунке.
На каждом из ребер проставлены значения пропускной способности С (n ) ребра n .
Для заданной сети определить максимальный поток j max транспортировки груза между указанной парой вершин, считая одну из них источником, а другую — стоком.
Решение:
Максимальный поток j max транспортировки груза между указанной парой вершин, считая одну из них источником, а другую — стоком:
Первый шаг.1. Находим какой-либо путь из х 1 в х 9 с положительной пропускной способностью.
Tаблица 1.
| x1 | x2 (1) | x3 (1) | x4 (1) | x5 ( 2) | x6 ( 3) | x7 ( 3) | x8 (2) | x9 (6) |
| x1 | 7 | 9- | 4 | |||||
| x2 | 0 | 8 | 3 | 6 | ||||
| x3 | 0+ | 5 | 8- | 4 | ||||
| x4 | 0 | 0 | 0 | 9 | 2 | |||
| x5 | 0 | 2 | ||||||
| x6 | 0+ | 5 | 3- | |||||
| x7 | 0 | 0 | 0 | 7 | 6 | |||
| x8 | 0 | 0 | 0 | 0 | 8 | |||
| x9 | 0+ | 0 | 0 |
В результате получен путь l1 = (x1 , х3 , х6 , х9 ). Элементы этого пути Cij помечаем знаком минус, а симметричные элементы Cji - знаком плюс.
Определяем пропускную способность найденного пути, которая равна наименьшей из пропускных способностей дуг:
Определяем остаточные пропускные способности дуг найденного пути и симметричных ему дуг. Для этого из элементов 
табл.1 вычитаем C1
, а к элементам 
прибавляем C1
. В результате получим новую табл.2 с измененными пропускными способностями.
Tаблица 2
| x1 | x2 (1) | x3 (1) | x4 (1) | x5 ( 2) | x6 ( 3) | x7 ( 3) | x8 (2) | x9 (7) |
| x1 | 7 | 6- | 4 | |||||
| x2 | 0 | 8 | 3 | 6 | ||||
| x3 | 3+ | 5 | 5 | 4- | ||||
| x4 | 0 | 0 | 0 | 9 | 2 | |||
| x5 | 0 | 2 | ||||||
| x6 | 3 | 5 | 0 | |||||
| x7 | 0+ | 0 | 0 | 7 | 6- | |||
| x8 | 0 | 0 | 0 | 0 | 8 | |||
| x9 | 3 | 0+ | 0 |
Второй шаг.1 . Помечаем столбцы табл.2, находим второй путь l2 = (x1 ,x3 , х7 , х9 ) и расставляем знаки.
2. Пропускная способность пути l2
Изменим пропускные способности помеченных дуг на С2 в табл.3.
Tаблица 3
| x1 | x2 (1) | x3 (1) | x4 (1) | x5 ( 2) | x6 ( 3) | x7 ( 4) | x8 (2) | x9 (7) |
| x1 | 7 | 2 | 4- | |||||
| x2 | 0 | 8 | 3 | 6 | ||||
| x3 | 7 | 5 | 5 | 0 | ||||
| x4 | 0+ | 0 | 0 | 9- | 2 | |||
| x5 | 0 | 2 | ||||||
| x6 | 3 | 5 | 0 | |||||
| x7 | 4 | 0+ | 0 | 7 | 2- | |||
| x8 | 0 | 0 | 0 | 0 | 8 | |||
| x9 | 3 | 4+ | 0 |
Третий шаг.1. Пометив столбцы, находим l3 = (x1 , х4 , х7 ,x9 ) .
Величина потока по пути l3
Вычислив новые пропускные способности дуг, приходим к табл.4.
Таблица 4
| x1 | x2 (1) | x3 (1) | x4 (1) | x5 ( 2) | x6 ( 3) | x7 ( 4) | x8 (2) | x9 (8) |
| x1 | 7- | 2 | 2 | |||||
| x2 | 0+ | 8 | 3 | 6- | ||||
| x3 | 7 | 5 | 5 | 0 | ||||
| x4 | 2 | 0 | 0 | 7 | 2 | |||
| x5 | 0 | 2 | ||||||
| x6 | 3 | 5 | 0 | |||||
| x7 | 4 | 2 | 0 | 7 | 0 | |||
| x8 | 0+ | 0 | 0 | 0 | 8- | |||
| x9 | 3 | 6 | 0+ |
Четвертый шаг.1. Помечаем столбцы табл.4, находим четвертый путь l4 = (x1 , х2 , х8 , х9 ) и расставляем знаки.
2. Пропускная способность пути l 4
Изменим пропускные способности помеченных дуг на С4 в табл.5.
Таблица 5
| x1 | x2 (1) | x3 (1) | x4 (1) | x5 ( 2) | x6 ( 3) | x7 ( 4) | x8 (4) | x9 (8) |
| x1 | 1 | 2 | 2- | |||||
| x2 | 6 | 8 | 3 | 0 | ||||
| x3 | 7 | 5 | 5 | 0 | ||||
| x4 | 2+ | 0 | 0 | 7 | 2- | |||
| x5 | 0 | 2 | ||||||
| x6 | 3 | 5 | 0 | |||||
| x7 | 4 | 2 | 0 | 7 | 0 | |||
| x8 | 6 | 0+ | 0 | 0 | 2- | |||
| x9 | 3 | 6 | 6+ |
Пятый шаг.1. Помечаем столбцы табл.5, находим четвертый путь l5 = (x1 , х4 , х8 , х9 ) и расставляем знаки.
2. Пропускная способность пути l5
Изменим пропускные способности помеченных дуг на С5 в табл.6.
Таблица 6
| x1 | x2 (1) | x3 (1) | x4 (1) | x5 ( 2) | x6 ( 3) | x7 ( 4) | x8 (5) | x9 |
| x1 | 1 | 2 | 0 | |||||
| x2 | 6 | 8 | 3 | 0 | ||||
| x3 | 7 | 5 | 5 | 0 | ||||
| x4 | 4 | 0 | 0 | 7 | 0 | |||
| x5 | 0 | 2 | ||||||
| x6 | 3 | 5 | 0 | |||||
| x7 | 4 | 2 | 0 | 7 | 0 | |||
| x8 | 6 | 2 | 0 | 0 | 0 | |||
| x9 | 3 | 6 | 8 |
Шестой шаг. Просматривая строки и помечая столбцы, убеждаемся в том, больше не существует ни одного пути с положительной пропускной способностью из вершины x
1
в вершину x
9
. Подмножество R
образуют помеченные вершины х1
,х2
, х3
, х4
, х5
, х6
, х7
,х8
, а подмножество 
- одна непомеченная вершины х9
. Разрез с минимальной пропускной способностью образуют дуги, начальные вершины которых принадлежат подмножеству R
, а конечные - . Таким образом, разрез с минимальной пропускной способностью 
. Удалив дуги этого разреза, блокируем все пути из источника в сток. Пропускная способность разреза
Заключительный шаг. Вычитая из элементов табл.1 соответствующие элементы табл.6, получим табл.7
Таблица 7.
| x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 |
| x1 | 6 | 7 | 4 | |||||
| x2 | -6 | 0 | 0 | 6 | ||||
| x3 | -7 | 0 | 3 | 4 | ||||
| x4 | -4 | 0 | 0 | 2 | 2 | |||
| x5 | 0 | 0 | ||||||
| x6 | -3 | 0 | 3 | |||||
| x7 | 4 | 2 | 0 | 0 | 6 | |||
| x8 | -6 | -2 | 0 | 0 | 8 | |||
| x9 | -3 | -6 | -8 |
Величина максимального потока равна сумме элементов x 1 -й строки табл.7 или сумме элементов x 9 -го столбца.
Максимальный поток равен 
.
Задача 3. Анализ сетей Петри
Сеть Петри задана графически (рис.23…30). В табл.1 в соответствии с вариантом и указанным номером рисунка приведены различные начальные маркировки сети.
Выполнить следующие действия:
Описать сеть аналитическим и матричным способами.
Проверить условия срабатывания каждого из переходов и найти новые маркировки, к которым приведет срабатывание соответствующих переходов, путем выполнения матричных преобразований.
Построить дерево достижимости заданной сети.
Проверить, является ли достижимой одна из маркировок, получаемых на четвертом шаге построения дерева, составив и решив матричные уравнения.
Таблица 1
№ варианта |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| m1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 2 | 2 | 0 | 1 | 3 | 0 | 1 | 1 |
| m2 | 1 | 2 | 2 | 2 | 3 | 1 | 2 | 2 | 1 | 2 | 3 | 1 | 1 | 2 | 0 |
| m3 | 2 | 3 | 1 | 0 | 1 | 1 | 1 | 3 | 2 | 1 | 0 | 1 | 2 | 3 | 3 |
| m4 | 3 | 1 | 3 | 4 | 0 | 2 | 1 | 1 | 0 | 1 | 1 | 2 | 1 | 1 | 2 |
| m5 | 1 | 2 | 5 | 1 | 2 | 2 | 3 | 0 | 3 | 3 | 2 | 0 | 3 | 2 | 1 |
| № рисунка | Рис.23 | Рис.27 | Рис.28 | Рис.29 | |||||||||||
Решение:
Опишем сеть аналитическим и матричным способами. Приведем графическое представление сети Петри, в которой позиции P = {p1 , p2 , p3 , p4 , p5 } и переходы T = {t1 , t2 , t3 , t4 } .
Начальная маркировка сети обозначается вектором μ0 [μ1 ,μ2 ,μ3 ,μ4 ,μ5 ] , μ0 [1 3 0 1 2]. Отсюда получим:
При аналитическом способе задания сеть Петри задается как C = (P,T,F,H,μ0 ) , где, кроме множеств позиций Р и переходов Т , задаются входная F и выходная Н функции.
Через F (t j ) обозначается множество входных позиций, а через H (t j ) - множество выходных позиций перехода t j ; μ 0 - начальная маркировка сети.
F (t1 ) = {p5 },H (t1 ) = {p1 ,p2 },
F (t2 ) = {p1 },H (t2 ) = {p3 , p4 },
F (t3 ) = {p3 , p4 }H (t3 ) = {p1 },
F ( t 4 ) = { p 2 , p 3 , p 4 } H ( t 4 ) = { p 5 }.
μ0 [1 3 0 1 2]
Матричная форма определения сети Петри эквивалентна аналитическому способу задания C = ( P , T , D - , D + ,μ0 ) . Здесь D - и D + - матрицы входных и выходных инциденций соответственно размером m × n , где m - число переходов и n - число позиций.
Элемент dij - матрицы D - равен кратности дуг, входящих в i -й переход из j -й позиции.
Элемент dij + матрицы D + равен кратности дуг, выходящих из i -ro перехода в j -ю позицию.
Для рассматриваемой сети Петри
Матрица D = D + - D - называется матрицей инцидентности сети Петри,
2. При начальной маркировке μ0 [1 3 0 1 2] сети Петри разрешенными являются переходы t 1 и t 2 .
Условия срабатывания для перехода t 3 и t 4 не выполняется.
Переход t 1
[μ0
] ≥
[1000]*D
-
=
[1000] ·
;
[1 3 0 1 2] ≥
[00001] –
условие выполняется, переход разрешен.
Новая маркировка при срабатывании перехода t 1 равна:
.
Переход t 2
[μ0
] ≥
[0100]*
D
-
=
[0100]
·;
[1 3 0 1 2] ≥
[10000] –
условие выполняется, переход разрешен.
Новая маркировка при срабатывании перехода t 2 равна:
.
Переход t 3
[μ0
] ≥
[0010]*
D
-
=
[0010]
·;
[1 3 0 1 2] ≥
[00110] -
условие не
выполняется, переход запрещен.
Переход t 4
[μ0
] ≥
[0001]*
D
-
=
[0001]
·;
[1 3 0 1 2] ≥
[01110] –
условие не выполняется, переход запрещен.
Построим дерево достижимости заданной сети.
Проверим, является ли достижимой одна из маркировок, полученных на пятом шаге построения дерева, составив и решив матричные уравнения.
Уравнение 
принимает вид
Перенесем 
в левую часть и выполним умножение, тогда
.
Приравняем составляющие векторов
Система имеет решение x 1 = 1; x 2 = 2; x 3 = 0; x 4 = 2.
Это значит, что исследуемая маркировка достижима и в последовательности срабатываний переход t 1 срабатывает один раз, переходы t 2 и t 4 - по два раза, переход t 3 не срабатывает.
Задача 4. Элементы математической логики и теории автоматов
Конечный автомат задан графом, определенным в задаче 1. Вершины графа отождествляются с состояниями автомата таким образом, что множество состояний Q= {q 1 ,q 2 ,… , qn }. Переход автомата из одного состояния в другое осуществляется под воздействием множества входных сигналов X = {x 1 ,x 2 ,x 3 ,x 4 }. Переходы определяются законом отображения Г вершин графа, причем каждому переходу соответствует только одна из букв множества X . При задании графа эти буквы расставить произвольно.
Автомат позволяет вырабатывать выходные сигналы Y = {y 1 ,y 2 ,y 3 }:
y 1 - переход из состояния qi в состояние qi (петля);
y 2 - переход из состояния qi в qj при i < j ;
y 3 - переход из состояния qi в qj при i > j .
Осуществить структурный синтез конечного автомата. Реализацию осуществить на элементах, указанных в табл.1, в соответствии с номером варианта. Обязательной является минимизация реализуемых функций.
Таблица 1
№ варианта |
11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
Тип элементов |
И НЕ |
И ИЛИ НЕ |
И НЕ |
ИЛИ НЕ |
И НЕ |
И ИЛИ НЕ |
И НЕ |
ИЛИ НЕ |
И ИЛИ НЕ |
И НЕ |
Тип триггера |
D | JK | T | D | RS | RSD | D | JK | T | D |
Решение:
Множество вершин X = { x 1 , x 2 ,x 3 , x 4 , x 5 , x 6 },
Вершины графа отожествляются с состояниями автомата таким образом, что множество состояний Q= {q 1 ,q 2 , q 3 , q 4 , q 5 , q 6 }. Переход автомата из одного состояния в другое осуществляется под воздействием множества входных сигналов X = {x 1 ,x 2 ,x 3 ,x 4 }.
Автомат позволяет вырабатывать выходные сигналы Y = {y 1 , y 2 ,y 3 }.
На основании аналитического описания ориентированного графа из задания № 1 запишем закон отображения состояний автомата:
Г q1 = {q1 (x1 /y1 ), q3 (x2 /y2 ), q2 (x3 /y2 )},
Г q2 = {q4 (x3 /y2 ), q1 (x4 /y3 ), q3 (x1 /y2 )},
Г q3 = {q1 (x1 /y3 ), q5 (x2 /y2 ), q2 (x3 /y3 ), q4 (x4 /y2 )},
Г q4 = {q2 (x1 /y3 ), q6 (x2 /y2 ), q3 (x3 /y3 ), q5 (x4 /y2 )},
Г q5 = {q3 (x4 /y3 ), q4 (x1 /y3 ), q6 (x2 /y2 )},Г q 6 = {q 4 (x 3 / y 3 ),q 5 (x 4 / y 3 )}.
Обобщенная таблица переходов и выходов соответствующего конечного автомата представлена в табл.2.
Таблица 2
| X | Q | q1 | q2 | q3 | q4 | q5 | q6 |
| X1 | q1 /y1 | q3 /y2 | q1 /y3 | q2 /y3 | q4 /y3 | ─ | |
| X2 | q3 /y2 | ─ | q5 /y2 | q6 /y2 | q6 /y2 | ─ | |
| X3 | q2 /y2 | q4 /y2 | q2 /y3 | q3 /y3 | ─ | q4 /y3 | |
| X4 | ─ | q1 /y3 | q4 /y2 | q5 /y2 | q3 /y3 | q5 /y3 | |
Осуществим структурный синтез автомата, заданного табл.1. В качестве элементов памяти используем D-триггеры, в качестве элементной базы используем логические элементы И-НЕ.
Количество букв входного алфавита n = 4
Количество входовp ≥ log2 n = log2 4 = 2;
Количество букв выходного алфавита m = 2
Количество выходовe ≥ log2 m = log2 3 = 2;
Количество состояний r = 6
Количество триггеровz ≥ log2 r = log2 6 = 3.
Приступаем к кодированию:
x |
u | u1 | u2 | |
| x1 | 1 | 0 | 5 | |
| x2 | 1 | 1 | 4 | |
| x3 | 0 | 0 | 5 | |
| x4 | 0 | 1 | 5 | |
| v1 | v2 | ||
| y1 | 1 | 0 | 1 |
| y2 | 0 | 1 | 9 |
| y3 | 0 | 0 | 9 |
q |
w |
w1 | w2 | w3 | |
| q1 | 0 | 0 | 1 | 3 | |
| q2 | 0 | 1 | 0 | 3 | |
| q3 | 0 | 0 | 0 | 4 | |
| q4 | 1 | 0 | 0 | 4 | |
| q5 | 0 | 1 | 1 | 3 | |
| q6 | 1 | 1 | 0 | 2 | |
На основании результатов кодирования строим обобщенную таблицу переходов и выходов структурного автомата (табл.3), заменяя состояния, входные и выходные переменные их кодами.
Таблица 3
u1 u2 |
w1 w2 w3 |
001 | 010 | 000 | 100 | 011 | 110 |
| 10 | 001/10 | 000/01 | 001/00 | 010/00 | 100/00 | ─ | |
| 11 | 000/01 | ─ | 011/01 | 110/01 | 110/01 | ─ | |
| 00 | 010/01 | 100/01 | 010/00 | 000/00 | ─ | 100/00 | |
| 01 | ─ | 001/00 | 100/01 | 011/01 | 000/00 | 011/00 | |
Используя таблицу переходов D-триггера и данные предыдущей таблицы, составим обобщенную таблицу функционирования структурного автомата (табл.4). Функции возбуждения трех триггеров обозначены через D1 , D2 , D3 , соответственно.
Таблица 4
| u1 | u2 | w1 (t) | w2 (t) | w3 (t) | w1 ( t+1) |
w2 ( t+1) |
w3 ( t+1) |
v1 | v2 | D1 | D2 | D3 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 | 1 | * | * | * | * | * | * | * | * |
| 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 0 | * | * | * | * | * | * | * | * |
| 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 |
| 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 |
| 0 | 0 | 0 | 1 | 1 | * | * | * | * | * | * | * | * |
| 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 0 | * | * | * | * | * | * | * | * |
| 1 | 1 | 1 | 1 | 0 | * | * | * | * | * | * | * | * |
| 0 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 |
По этой таблице запишем СДНФ выходных функций V и функций возбуждения триггеров D1 , D2 , и D3 , зависящих от набора переменных u1 , u2 , w1 (t), w2 (t), w3 (t). В результате получим систему логических функций для построения комбинационной части автомата:
.
.
.
.
.
Минимизируем функции согласно картам Карно:
После минимизации имеем набор функций в базисе И-НЕ
=
.
.
.
Функциональная схема структурного автомата:
