Составители:
Рубрика:
операции, находящейся в начале j-й дуги. Согласно сделанным ра-
нее предположениям будем всегда считать векторы h и t целочис-
ленными и неотрицательными.
Замечание. При формулировке некоторых утверждений бу-
дем использовать термин система без ограничений в отношении
системы, у которых принимаются во внимание лишь ограничения,
явно указанные при формулировке того или иного утверждения;
при этом на остальные параметры системы никаких ограничений
не накладывается (предполагается, что по тем или иным причина-
ми они не оказывают влияния на реализацию алгоритма). Такая
точка зрения оправдана, ибо, с одной стороны, она акцентирует
внимание на определенном аспекте ситуации, а с другой стороны,
способствует упрощению рассмотрений. Кроме того, она не умень-
шает общности рассмотрений, позволяя распространить их на все
интересующие стороны ситуации обычными приемами (подключе-
нием дополнительных функциональных устройств).
Теорема 2.1. Для того чтобы алгоритм с матрицей инци-
денций A был реализуем на данной системе с вектором временной
развертки t и вектором реализации h, необходимо, а в случае ба-
зовой системы и достаточно выполнение неравенства
−A
T
t ≥ h. (2.1)
Д о к а з а т е л ь с т в о. Поскольку реализация алгоритма озна-
чает реализацию одной из его базовых программ, то осталось заме-
тить, что строки неравенства (2.1) представляют собой не что иное,
как условия теоремы 2.2.
Действительно, в j-й строке матрицы A
T
находятся элементы
a
ij
, i = 1, 2, . . . , n, указывающие, является ли i-я вершина одним
из концов рассматриваемой дуги, и если является (т.е. a
ij
6= 0), то
служит ли она входом (в этом случае a
ij
= +1) или выходом (тогда
a
ij
= −1) для этой вершины. Как было замечено ранее, в каждой
строке имеется лишь два ненулевых элемента (их абсолютная ве-
личина равна единице, а знаки противоположны).
Пусть в рассматриваемой j-й строке
a
i
0
j
= 1, a
i
00
j
= −1, a
ij
= 0 для i 6= i
0
, i
00
.
Таким образом, j-я дуга исходит из вершины с номером i
0
= i
0
(j)
(начало дуги) и входит в вершину i
00
= i
00
(j) (конец дуги). Ска-
84
Страницы
- « первая
- ‹ предыдущая
- …
- 81
- 82
- 83
- 84
- 85
- …
- следующая ›
- последняя »
