Составители:
Рубрика:
направлении.
Д о к а з а т е л ь с т в о. Если нет дополнительных ограничений,
то достаточно воспользоваться теоремой 2.7: сформулированное в
теореме 2.8 условие эквивалентно ортогональности h всем элемен-
тарным циклам.
Теорема 2.9. Если граф алгоритма связный и система (2.5)
совместная, то множество ее решений представляет прямую ли-
нию с направляющим вектором e = (1, 1, . . . 1).
Д о к а з а т е л ь с т в о. Зафиксируем какую-либо координату
вектора t. Тогда в силу связности графа все остальные компонен-
ты определяются из системы (2.5) однозначно. Поскольку в каж-
дой строке матрицы A
T
имеется только два ненулевых элемента,
равных +1 и −1, то разность любых двух решений системы про-
порциональна вектору e.
Cледствие 2.8. Если граф алгоритма G имеет p компонент
связности, то множество ее решений представляет плоскость
размерности p.
Следствие 2.9. Если граф алгоритма имеет p компонент
связности, n вершин и m дуг, то он имеет m −n + p независимых
векторов циклов.
Замечание 1. Если граф алгоритма связный, то вся неод-
нозначность решений системы (2.5) определяется выбором момен-
та начала выполнения алгоритма. Поэтому исследование реализа-
ций алгоритма, наилучших с точки зрения времени выполнения и
не требующих памяти для хранения промежуточных результатов,
весьма просто. Сначала проверяют условия теоремы 2.8, далее на-
ходят какое-нибудь решение задачи (2.5) и сдвигают его на вектор,
пропорциональный вектору e. Среди подобных сдвигов отыскива-
ют те, которые удовлетворяют дополнительным ограничениям, на-
кладываемым вычислительной системой.
Замечание 2. До настоящего времени формально можно счи-
тать, что исследовался специальный случай отсутствия памяти для
промежуточных результатов. Однако, если добавить в каждую ду-
гу графа по вершине, указывающей на обращение к памяти, пони-
мая под этим устройство задержки (не меняющее информацию, но
требующее некоторое время для срабатывания), мы придем снова
к задаче вида (2.5). Однако теперь в полученном векторе h некото-
рые компоненты (а именно те, которые соответствуют введенным
устройствам) не определены; их следует подобрать в зависимости
93
Страницы
- « первая
- ‹ предыдущая
- …
- 90
- 91
- 92
- 93
- 94
- …
- следующая ›
- последняя »
