Автоморфизм гиперграфа

Автоморфизмом гиперграфа Г называется подстановка на множестве его вершин, оставляющая без изменения его список ребер. Таким образом, автоморфизм— это изоморфизм, переводящий гиперграф Г в себя. [c.38]

Легко показать, что все автоморфизмы любого гиперграфа образуют группу подстановок. Эта группа называется группой автоморфизмов гиперграфа. [c.38]

Посмотрим, как можно использовать операцию произведения в предыдущем примере. Из рис. 2.3 видно, что группа автоморфизмов гиперграфа порождается, во-первых, всеми возможными подстановками на множестве вершин 4, 5, 6), что соответствует симметрической группе 5з, во-вторых, всеми возможными подстановками на множестве 2, <3 — это уже группа 5з, и, в-третьих, на множестве (1 работает единичная группа Si. Таким образом, группа автоморфизмов этого графа равна [c.41]

Используя эту формулу и (2.11), найдем цикловой индекс группы автоморфизмов гиперграфа, изображенного на рис. 2.4, а [c.43]

Рис. 2.3. Гиперграф с группой автоморфизмов порядка 12

Именно благодаря группе автоморфизмов возникают эквивалентные раскраски вершин. Исключение составляют гиперграфы, группы автоморфизмов которых единичные. Такие гиперграфы называются асимметрическими. [c.38]

Рис. 2.4. Гиперграфы, группы автоморфизмов которых выражаются через композицию

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

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

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

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

Отсюда видно, что использование теоремы Пойа в первую очередь предполагает знание группы автоморфизмов гиперграфа, точнее,— ее циклового индекса, отыскание которого путем выписывания всех подстановок группы может быть осуществлено только в наиболее простых случаях. К сожалению, не существует общего подхода построения циклового индекса. Однако часто группу автоморфизмов удается выразить с помощью известных операций через некоторые другие группы, цикловые индексы которых известны. Здесь будут описаны две операции, которые используются в дальнейшем. [c.41]

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

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

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

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