Автоморфизм - граф
Cтраница 4
Гомоморфизм был определен Рандичем [4], но, поскольку им были просто пронумерованы вершины от 1 до 30 и в графе Петерсена - от 1 до 10, он представил соответствие в виде таблицы, и в результате простота стягивания оказалась в его статье до некоторой степени скрытой. Наше обозначение позволяет нам увидеть, что каждый элемент группы S5 индуцирует автоморфизм графа с 30 вершинами ( поскольку каждая операция g e S5 переставляет вершины i jk и сохраняет смежность, как определено выше правилами 1 и 2), но мы не можем сразу же прийти к выводу об отсутствии иных автоморфизмов. [46]
 |
Выбор размножающихся над-частиц ( обведены штриховыми линиями ветвящегося процесса для модели эффекта замещения высших порядков. [47] |
Описанный выше способ перехода от комбинаторной энтропии к числу упорядоченных деревьев распространяется на случай систем с несколькими типами мономеров. Для этого достаточно раскрасить вершины графа большим количеством цветов и учитывать эту раскраску при автоморфизмах графа. Если степень узла некоторого v - ro цвета составляет fv, то выходящие из него ветви переставляются ( fv-i) ( для корня - fv) способами. [48]
Действие группы неособых точек вырожденного слоя на всем слое индуцирует ее действие на соответствующем графе, что определяет группу Г автоморфизмов графа, транзитивную на множестве вершин, соответствующих компонентам кратности один. Присоединим к системе компонент слоя кривую сг. [49]
Используемые нами свойства решетки Лича в основном проистекают из фактов о глубоких дырах этой решетки, изложенных в гл. Примечательно, что стенки фундаментальной области для этой группы Кокстера ( которые взаимно однозначно соответствуют корням Лича) транзитивно переставляются автоморфизмами графа, образующими бесконечную группу, абстрактно изоморфную группе Со всех автоморфизмов решетки Лича, включая переносы. [50]
Это было впервые замечено Херцигом, Стейнбергом и Титсом, которые независимо с разных сторон подошли к таким группам. В случае характеристик 2, 3 некоторые новые скрученные группы были найдены Ри и Судзуки с использованием систем корней типов В2, G2, F4, где автоморфизмы графов могли бы существовать, если бы мы игнорировали длины корней. [51]
Из следствия (2.5.1) теоремы Пойа, которое интерпретирует ряд Z ( А, 1 х), вытекает, что ряд Z ( I ( G), i x) перечисляет 1 ( Сг) - эквивалентные классы множеств, состоящих из ребер графа G. Эти классы эквивалентности в точности соответствуют таким остовным подграфам графа G, каждые два из которых содержатся в одном и том же классе лишь тогда, когда существует автоморфизм графа G, переводящий один из этих подграфов в другой. Если два подграфа не принадлежат одному и тому же классу, то они называются неподобными. [52]
Из следствия (2.5.1) теоремы Пойа, которое интерпретирует ряд Z ( А, 1 х), вытекает, что ряд Z ( I ( G), 1 х) перечисляет 1 ( С) - эквивалентные классы множеств, состоящих из ребер графа G. Эти классы эквивалентности в точности соответствуют таким остовным подграфам графа G, каждые два из которых содержатся в одном и том же классе лишь тогда, когда существует автоморфизм графа G, переводящий один из этих подграфов в другой. Если два подграфа не принадлежат одному и тому же классу, то они называются неподобными. [53]
 |
Граф и его автоморфизм.| Пример орграфа. [54] |
Граф называется полным, если любые две его различные вершины соединены ребром. Два графа G и Я изоморфны, если существует взаимно однозначное отображение ( называемое изоморфизмом) множества вершин графа G на множество вершин графа Н, сохраняющее смежность. Автоморфизмом графа О называется изоморфизм графа G на себя. На рис. 8.4 представлен граф G4 и его автоморфизм ср. [55]
Предложение 2 позволяет выявить связь изучения групп автоморфизмов с задачами перечисления и классификации графов. Предложение 3 показывает, что строение группы автоморфизмов графа является его внутренней характеристикой, не зависящей от его конкретного задания той или иной матрицей смежности. Это позволяет изучать автоморфизмы графа, пользуясь какой-либо удобной формой матрицы смежности. [56]
Существует также правило перегруппировки, согласно которому мы можем применять некоторые перестановки к меткам вершин. Две нумерации графа В считаются эквивалентными, если автоморфизм графа В превращает одну нумерацию в другую. В более общем случае мы, возможно, захотим рассмотреть эквивалентность для соответствующей подгруппы aut В. Для данного правила перегруппировки реакционный граф В - это граф Г, вершины которого соответствуют различным неэквивалентным нумерациям графа В и в котором имеется направленное ребро, связывающее вершину а с вершиной 8, если и только если вершина / 3 может быть получена из а при применении правила перегруппировки только один раз. Поскольку мы имеем п различных меток, легко рассчитать число вершин графа Г: оно равно я. В, где Х обозначает число элементов в множестве X. [57]
Соединим оо с 22 точками, точку с блоками, ее содержащими, и два блока, если они не пересекаются. Это приводит к графу с указанными выше параметрами. Простая группа Хигмана - Симса является подгруппой индекса два в группе автоморфизмов описанного графа. [58]
Соединим с с 22 точками, точку с блоками, ее содержащими, и два блока, если они не пересекаются. Это приводит к графу с указанными выше параметрами. Простая группа Хигмана - Симса является подгруппой индекса два в группе автоморфизмов описанного графа. [59]
Группа полевых автоморфизмов всегда циклическая. Кроме того, имеется общая формула порядка диагональной группы для каждого семейства групп типа Ли. Группа диагональных автоморфизмов нормальна в Aut ( Х) 1Х, а полевые автоморфизмы коммутируют с автоморфизмами графа. [60]
Страницы: 1 2 3 4