Составители:
Рубрика:
Теорема 5.1. Любой гомоморфизм можно представить как
последовательность независимых и связных гомоморфизмов.
Д о к а з а т е л ь с т в о вытекает из введенных только что поня-
тий (см. определения 5.7 и 5.8).
Замечание. Рассматривают также обратную задачу — задачу
о построении гомоморфного прообраза данного графа. Эта зада-
ча решается добавлением новых вершин и ребер. В связи с этим
вводят операцию добавления новых вершин: в E ребро (u, v) исход-
ного графа заменяют парой ребер (u, w), (v, w), а к V добавляют
новую вершину w. Возможны и другие способы добавления новых
вершин, которые ведут к получению гомоморфного прообраза ис-
ходного графа.
§ 6. Построение графов параллельных форм
Предположим, что известны:
— множество переменных, преобразование которых составляет
рассматриваемый алгоритм;
— множество операций, выполняемых при реализации алгорит-
ма;
— соответствие, показывающее, какие результаты предшеству-
ющих операций являются операндами для следующих.
Дополнительные предположения:
1) число операндов в каждой операции фиксировано и не зави-
сит от результатов работы алгоритма;
2) классы переменных и классы операций фиксированы; пе-
ременные и операции, принадлежащие этим классам, называются
базовыми.
Построение графа алгоритма состоит в следующем:
— каждой операции U алгоритма ставится в соответствие вер-
шина u,
— если операнд операции V (которой поставлена в соответствие
вершина v) является результатом операции U, то соответствующие
им вершины u и v соединяются направленной (от u к v) дугой (u, v).
Полученный таким образом граф имеет следующие свойства:
— в каждую вершину u входит столько дуг, сколько входов у
операции U,
— полученный граф не содержит циклов.
Результатом является ориентированный ациклический мульти-
граф.
49
Страницы
- « первая
- ‹ предыдущая
- …
- 46
- 47
- 48
- 49
- 50
- …
- следующая ›
- последняя »
