Автоморфизм - граф
Cтраница 3
Первый топологический индекс, основанный на теории информации, введен в 1955 - 1956 гг. Рашевским [36] и Трукко [37] на базе группы автоморфизмов графа данного соединения. Так называемый хроматический информационный индекс предложен Мовшови-чем [38] и определен исходя из однозначного разбиения графа G на основе его хроматических классов. Теоретико-информационные индексы, построенные с помощью матрицы расстояний, разработаны Бончевым и Тринайстичем [39]: первый индекс зависит от разбиения полного числа расстояний на классы, а второй - от разбиения полного расстояния. [31]
Более значительная идея состоит в замене Loo на некоторого-рода пополнение, позволяющее рассматривать бесконечные линейные комбинации образующих с последующим переходом1 к подалгебре, неподвижной относительно автоморфизмов графа. Если такое возможно, то получающаяся алгебра почти наверняка не будет обладать системой корней. [32]
В каждом из ранее приведенных примеров применяемые нами обозначения для вершин реакционного графа имели три преимущества: очень просто были связаны с исходным помеченным графом, давали простое правило для построения реакционного графа и содействовали определению группы автоморфизмов реакционного графа. Рассмотрим теперь другой пример из приведенных Балабаном [11], для которого, по-видимому, трудно найти обозначение, обладающее всеми указанными преимуществами. [33]
Хигман и Симе [ Hig3 ] описали простую группу порядка 44352000 100 М как группу четных перестановок некоторого графа, имеющего 100 вершин, а Маклафлин [ McL 1 ] обнаружил простую группу порядка 898128000, являющуюся группой автоморфизмов графа с 275 вершинами. [34]
Автоморфизмы графа образуют группу. Граф, не содержащий циклов, называется лесом. Дерево - это связный граф без циклов. Корневое дерево имеет одну вершину ( корень ], веделенную из остальных. [35]
Подстановка на множестве V ( G) есть автоморфизм, если она сохраняет смежность вершин. Автоморфизмы графа G образуют группу подстановок, называемую группой автоморфизмов графа G. Если для любой пары вершин х, у е V ( G) существует автоморфизм, переводящий х в у, то группа автоморфизмов называется вершинно-транзитивной. Аналогичным образом опре деляется реберно-транзитивная группа. Граф называется регу лярным степени rf, если каждая вершина инцидентна d ребрам. Заметим, что граф с вершинно-транзитивной группой автомор физмов является регулярным. [36]
Множество всех автоморфизмов данного графа образует группу относительно операции композиции автоморфизмов. Автоморфизмы графа G порождают группу подстановок вершин Г ( С), наз. [37]
Под графом мы понимаем конечный неориентированный граф ( как определено у Харари [ 6, стр. Группа автоморфизмов графа состоит из тех и только тех подстановок множества вершин графа, которые сохраняют отношение смежности ( см. Харари [ 6, стр. [38]
Пусть даны конечная группа F и граф G ( f), полученный по теореме Фрухта. Тогда каждый нетождественный автоморфизм графа G ( F) не имеет неподвижных вершин. [39]
Предложение 2 позволяет выявить связь изучения групп автоморфизмов с задачами перечисления и классификации графов. Предложение 3 показывает, что строение группы автоморфизмов графа является его внутренней характеристикой, не зависящей от его конкретного задания той или иной матрицей смежности. Это позволяет изучать автоморфизмы графа, пользуясь какой-либо удобной формой матрицы смежности. [40]
Одной из характеристик, наиболее полно отражающих свойства симметрии графа, является цикловой индекс его группы автоморфизмов. В табл. 2 приведены цикловые индексы групп автоморфизмов исследованных графов. [41]
 |
Граф Хивуда. [42] |
Если W - такой п-путь, что существуют автоморфизмы графа G, отображающие W на любой из его последователей, то граф G п-транзитивен. [43]
Подстановка на множестве V ( G) есть автоморфизм, если она сохраняет смежность вершин. Автоморфизмы графа G образуют группу подстановок, называемую группой автоморфизмов графа G. Если для любой пары вершин х, у е V ( G) существует автоморфизм, переводящий х в у, то группа автоморфизмов называется вершинно-транзитивной. Аналогичным образом опре деляется реберно-транзитивная группа. Граф называется регу лярным степени rf, если каждая вершина инцидентна d ребрам. Заметим, что граф с вершинно-транзитивной группой автомор физмов является регулярным. [44]
Коллинеации конфигурации D на себя образуют группу. Очевидно, исследование этой группы может производиться в терминах группы автоморфизмов графа Петерсена. Мы утверждаем, что имеется 12 таких циклов, составляющих 6 пар по два не пересекающихся между собой цикла. Вершины этих непересекающихся циклив попарно соединены ( непересекающимися) ребрами. [45]
Страницы: 1 2 3 4