Составители:
Рубрика:
от требований, налагаемых вычислительной системой на решение
задачи.
Следующая теорема иллюстрирует роль матрицы смежности.
Теорема 2.10 Пусть G = (V, E) ориентированный граф без
петель и пусть B — его матрица смежности. В графе G конту-
ры отсутствуют тогда и только тогда, когда существует такая
матрица перестановок P, что матрица P
T
BP — верхнетреуголь-
ная.
Д о к а з а т е л ь с т в о. Переход от матрицы B к матрице P
T
BP
соответствует определенной перенумерации вершин.
Если в G контуры отсутствуют, то существуют параллельные
формы. Возьмем одну из них и перенумеруем вершины подряд сна-
чала в первом ярусе, затем во втором и т.д. При такой нумерации
дуги будут всегда идти от вершины с меньшим номером к вершине
с большим номером. А это означает, что у матрицы смежности
P
T
BP ненулевыми будут лишь элементы b
0
ij
, i < j, т.е. матрица
будет верхнетреугольной.
Обратно, если P
T
BP — верхнетреугольная, то это означает,
что существует перенумерация, при который все дуги идут от мень-
ших номеров вершин к большим, т.е. циклов в графе нет.
Справедливо также следующее утверждение.
Теорема 2.11. Ациклический ориентированный граф с мат-
рицей смежностей B имеет параллельную форму высоты l и ши-
рины s тогда и только тогда, когда существует матрица пере-
становкой P такая, что P
T
BP является блочной правой тре-
угольной блочного порядка l с нулевыми квадратными диагональ-
ными блоками порядка не выше s.
Д о к а з а т е л ь с т в о аналогично доказательству предыдущей
теоремы, если ярусы параллельной формы рассматривать как
макрооперации, а блоки как элементы соответствующей матрицы
смежностей.
§ 3. Об NP -сложности задачи отыскания графа
вычислительной системы из графа алгоритма
3.1. Метод перебора
Предыдущие построения показали принципиальную возмож-
ность из графа алгоритма получить граф вычислительной систе-
94
Страницы
- « первая
- ‹ предыдущая
- …
- 91
- 92
- 93
- 94
- 95
- …
- следующая ›
- последняя »
