Элементы теории графов (стр. 3 )

x1	x2	x3	x4	x5(1)	x6(5)	x7(6)	x8(6)
x1	0	11-
x2	3	4	7	18	2	6
x3	0	5
x4	0	15
x5	4+	0	10-	0
x6	0	0	0+	11	11-
x7	0	3
x8	3	4	0+	0

Третий  шаг. 1. Помечаем столбцы табл. 3, находим третий путь l3 = (x1, x5, x6, x8) и расставляем знаки.

2. Пропускная способность пути l2

Изменим пропускные способности помеченных дуг на С3  в табл. 4.

                                                               Tаблица 4

x1	x2	x3	x4	x5(1)	x6	x7	x8
x1	0	1
x2	3	4	7	18	2	6
x3	0	5
x4	0	15
x5	14	0	0	0
x6	0	0	10	11	1
x7	0	3
x8	3	4	10	0

Четвертый шаг. Просматривая строки, убеждаемся в том, что больше не существует ни одного пути с положительной пропускной способностью из вершины x1 в вершину x8. Подмножество R образуют помеченные вершины х1, х5, а подмножество   –  остальные непомеченные вершины  х2, х3, х4, х6, х7, х8. Разрез с минимальной пропускной способностью образуют дуги, начальные вершины которых принадлежат подмножеству R, а конечные – . Таким образом, разрез с минимальной пропускной способностью . Удалив дуги этого разреза, блокируем все пути из источника в сток. Пропускная способность разреза

       Заключительный шаг. Вычитая из элементов табл.1 соответствующие элементы табл.4, получим табл.5

                                                               

Tаблица 5

x1	x2	x3	x4	x5	x6	x7	x8
x1	3	14
x2	-3	0	0	0	0	3
x3	0	0
x4	0	0
x5	-14	0	10	4
x6	0	0	-10	0	10
x7	0	0
x8	-3	-4	-10	0

       Величина максимального потока равна сумме элементов x1-й строки табл. 5 или сумме элементов x8-го столбца

Максимальный поток равен  .

положительные элементы табл.5 характеризуют величины дуговых потоков:

; ;; ; ;.

Стоимость доставки груза определяется по формуле:

.

.

.

Задача 3. Анализ сетей Петри

Сеть Петри задана графически (рис. 23…30). В табл. 1 в соответствии с вариантом и указанным номером рисунка приведены различные начальные маркировки сети.

Выполнить следующие действия:

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

Таблица 1

№ варианта	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
?1	0	1	0	1	1	1	1	2	2	0	1	3	0	1	1
?2	1	2	2	2	3	1	2	2	1	2	3	1	1	2	0
?3	2	3	1	0	1	1	1	3	2	1	0	1	2	3	3
?4	3	1	3	4	0	2	1	1	0	1	1	2	1	1	2
?5	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, t5}. Начальная маркировка сети обозначается вектором  ?0 [?1,?2,?3,?4,?5],  ?0 [1 3 1 0 2]. Отсюда получим:

При аналитическом способе задания сеть Петри задается как C = (P, T,F, H,?0), где, кроме множеств позиций Р и переходов Т, задаются входная F и выходная Н функции. Через F(tj) обозначается множество входных позиций, а через H(tj) – множество выходных позиций перехода tj; ?0 – начальная маркировка сети.

F(t1) = {p1},                                        H(t1) = {p2, p3 },

F(t2) = {p2},                                        H(t2) = {p4},

F(t3) = {p3},                                        H(t3) = {p5 },

F(t4) = {p4, p5},                                H(t4) = {p1},

F(t5) = {p4, p5},                                H(t5) = {p2, p3}.