Группа - граф
Cтраница 1
Группа графа G определяет также классы подобных блоков. [1]
 |
Симметричные графы.| Тождественные графы. [2] |
Группой графа называется совокупность всех его автоморфизмов; это группа подстановок, действующая на множестве вершин графа. Известно [13], что каждая конечная группа изоморфна группе некоторого графа, но не известно, вообще говоря, является ли данная группа подстановок группой графа. [3]
Это означает, что группы графов, вообще говоря, допускают копредставления, число образующих которых превосходит более чем на единицу число соотношений. [4]
Теорема 14.1. Реберная и вершинная группы графа G изоморфны тогда и только тогда, когда граф G имеет не более одной изолированной вершины, а граф К2 не является его компонентой. [5]
Таким образом, с помощью группы графа G выясняется, можно или нет рассматривать два различных вхождения подграфа Н как эквивалентные. [6]
Значит, если В является группой графа G, имеющего порядок п, то N [ Ет; Г ( G) ] есть число суперпозиций, составленных из т экземпляров графа G. С другой стороны, N [ Sm Г ( G) ] есть число суперпозиций, в которых копии графа G взаимозаменяемы. [7]
 |
Два асимметрических графа. [8] |
Понятно, что реберная и вершинная группы графа Kt - х изоморфны. Но они, конечно, не могут быть идентичными, так как степень группы F. Заметим, что ребро хь остается на месте в каждом элементе реберной группы. Даже группа подстановок, полученная из группы Fi ( / C4 - х) сужением ее множества объектов до множества xit x2, х3, х4, не идентична группе Г ( / С4 - х), поскольку эти две изоморфные группы подстановок одинаковой степени имеют различные циклические структуры. Более того, можно показать, что даже если две группы подстановок имеют одинаковую степень и одинаковую циклическую структуру, то они все еще не обязательно идентичны; см. Пойа [ 1, стр. [9]
Группу графа-композиции можно часто выразить через группы составляющих графов. [10]
Таким образом, две специальные группы подстановок, именно Sp и Dp, являются группами графов с р вершинами. Для любого - 6 существует асимметрический граф с р вершинами, а для 7 существует асимметрическое дерево. [11]
 |
Дополнение графа, изображенного на.| Три графа с одинаковыми группами. [12] |
G) всех подстановок на множестве V ( G), сохраняющих смежность, называется группой графа G, или группой автоморфизмов графа G, а ее подстановки называются автоморфизмами. Таким образом, группа графа является группой подстановок, объектами которых являются вершины графа. [13]
 |
Дополнение графа, изображенного на рис.| Три графа с одинаковыми группами. [14] |
G) всех подстановок на множестве F ( G), сохраняющих смежность, называется группой графа G, или группой автоморфизмов графа G, а ее подстановки называются автоморфизмами. Таким образом, группа графа является группой подстановок, объектами которых являются вершины графа. [15]
Страницы: 1 2 3