Гиперграф блок-схемы

Гиперграф блок-схемы [c.21]

Рис. 2.5. Гиперграфы блок-схем В (а) и В (б)

Рис. 2.6. Гиперграфы блок-схем с одинаковым инвариантом

Для построения циклового индекса С (5 (3, 6)) достаточно заметить, что всевозможные вращения гиперграфа блок-схемы совпадают с вращениями треугольника, группа автоморфизмов которого равна S3. Отличие состоит лишь в том, что при различных поворотах гиперграфа друг в друга переходят не отдельные элементы, а пары элементов. В связи с этим С В (3, 6)) сразу же получается из С(5з) путем замены hj на h j, / е 1 3 [c.70]

Рис. 2.9. Гиперграфы блок-схем а—В (3, 7) б—

В гиперграфе блок-схемы В (3, 7) (рис. 2.9, е) можно менять местами вершины 6 я 7 (группа 5г) и пары вершин 2, 3 и 4, 5 (группа 52, работающая на парах вершин). Учитывая, что вершина 1 неподвижна, имеем [c.72]

Две блок-схемы В и В будем называть изоморфными, если изоморфны их гиперграфы. [c.47]

Как видно из рис. 2.5, их гиперграфы совпадают с точностью до переименования вершин. Это означает, что блок-схемы В и В изоморфны. Действительно, [c.47]

В качестве примера рассмотрим блок-схему В = = 123—145—246—1789. Ее гиперграф приведен [c.55]

Построение группы автоморфизмов для конкретных блок-схем обычно трудоемко и связано с непосредственным анализом их гиперграфов. [c.56]

Для построения системы образующих группы автоморфизмов блок-схемы использовался следующий подход. В блок-схеме выделялись все возможные оси симметрии гиперграфа или его частей (их число определяет количество образующих в системе), а затем каждая образующая строилась как отображение вершин гиперграфа (или его части) относительно оси симметрии. Естественно, при таком подходе некоторые системы содержат не минимально возможное число образующих. Однако в этом случае каждая образующая представляет собой произведение одной или нескольких транспозиций, что очень удобно для использования на следующих этапах синтеза механизмов. [c.59]

Теперь рассмотрим блок-схемы fi (3, 6) и В (3,6), гиперграфы которых изображены на рис. 2.8. Для построения их цикловых индексов можно было бы использовать образующие групп из табл. 2.6. Однако проще применить понятия произведения и композиции групп. [c.69]

Оценим теперь число режимов, получаемых на основе блок-схем В (3, 7), йе1 5 (см. табл. 2.4). Их гиперграфы приведены на рис. 2.9. [c.71]

Элементы симметрии блок-схемы В (3, 7) описываются симметрической группой Sj на вершинах гиперграфа 2 и 3, группой 54 — на вершинах 4, 5, 6, 7 и единичной группой 5i (неподвижное звено /). Поэтому [c.71]

Группа автоморфизмов блок-схемы В (3, 7) может быть получена сначала взаимной перестановкой трех вершин гиперграфа внутри каждого четырехугольника (группа 5з), а затем взаимной перестановкой самих четырехугольников (группа 52). Учитывая, что на неподвижной вершине 1 работает группа S, получаем [c.72]

Для установления изоморфности блок-схем в этом случае удобно пользоваться либо непосредственно рисунками гиперграфов блок-схем, либо минимальными кодами блок-схем. [c.52]

В гиперграфе блок-схемы В 2>, 7) все автоморфизмы можно получить путем взаимной перестановки трех треугольников относительно неподвижной вершины J. Так как это равносильно перестановке пар вершин, принадлежаш,их треугольникам, то [c.73]

Рис. 2.7. Гиперграф Это выражение для циклового индек-са можно получить и не выписывая всех подстановок группы. Из рис. 2.7 видно, что все автоморфизмы блок-схемы В (3, б) можно получить выполняя еначала перестановки звеньев 2, 3 и 4, 5 на каждом треугольнике гиперграфа (этим перестановкам соответствует симметрическая группа S2), а затем совершая взаимную перестановку самих треугольников (снова работает группа S2). При этом вершина 1 остается неподвижной (учитывается группой 5i). Используя обозначения, относящиеся к произведению и композиции групп, получаем

Энциклопедия по машиностроению XXL

Оборудование, материаловедение, механика и ...