Математические модели в управлении. Заболотский В.П - 116 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

116
25
12 25 13 35 14 43 14 45
35
12 23 35 12 24 43 35 12 24 45
12 25 13 35 14 43 35 14 45
35
0
2
11 1
0
3
111
.
u
uu uu uu uu
u
uuuuuuuuuu
uu uu uuu uu
+++ + =
=+ ++
+++ +
(2.3.15)
В результате получаем a
15
= 7.
После проведения всех вычислений получаем матрицу полных пу-
тей графа, диаграмма которого изображена на рис. 2.3.4:
[]
5
5
5
12 34 5
714271
444342
.
112213
223324
114275
ij
a
==
A
(2.3.16)
При анализе путей в графе чаще всего определяются:
– вершины, входящие в путь;
– пути, длина которых удовлетворяет определенному требованию.
Первая задача может быть решена как задача перечисления совпа-
дающих символов дуг, входящих в путь, а также символов начала и кон-
ца пути. Для путей, ведущих из первой в пятую вершину в рассмотрен-
ном ранее примере 2.3.4, из выражения (2.3.15) можно получить следу-
ющие перечисления:
1235 12435 1245 125
1351435145
,,, , ,,, , ,,, , ,, ,
,,,,,,,,,.
xxxx xxxxx xxxx xxx
xxxxxxxxxx
Вторая задача решается как задача определения длин путей и выбо-
ра из них таких, которые удовлетворяют заданному критерию.
Так, например, если надо выбрать максимальный путь из первой в
пятую вершину, то таким будет путь < u
12
, u
24
, u
43
, u
35
>, содержащий
четыре дуги. Минимальных путей будет три, причем каждый из них
содержит по две дуги: < u
12
, u
25
>, < u
13
, u
35
>, < u
14
, u
45
>.

Страницы