Группа - граф
Cтраница 2
 |
Восемь помеченных графов третьего порядка. s, . j. [16] |
Совокупность всея автоморфизмов графа G, обозначаемая Г ( G), образует группу, называемую группой графа G. Таким образом, элементы группы Г ( G) являются подстановками, действующими на множестве F. [17]
 |
Восемь помеченных графов третьего порядка. [18] |
Совокупность всех автоморфизмов графа G, обозначаемая Г ( G), образует группу, называемую группой графа G. Таким образом, элементы группы Г ( G) являются подстановками, действующими на множестве F. [19]
G) всех подстановок на множестве V ( G), сохраняющих смежность, называется группой графа G, или группой автоморфизмов графа G, а ее подстановки называются автоморфизмами. Таким образом, группа графа является группой подстановок, объектами которых являются вершины графа. [20]
G) всех подстановок на множестве F ( G), сохраняющих смежность, называется группой графа G, или группой автоморфизмов графа G, а ее подстановки называются автоморфизмами. Таким образом, группа графа является группой подстановок, объектами которых являются вершины графа. [21]
В большинстве задач этого параграфа требуется найти число неподобных подграфов данного графа G, изоморфных некоторому графу Я. Таким образом, с помощью группы графа G выясняется, можно или нет рассматривать два различных вхождения подграфа Н как эквивалентные. [22]
Из определения следует, что если А. Значит, если В является группой графа G, имеющего порядок / г, то N [ Ет; Г ( G) ] есть число суперпозиций, составленных из т экземпляров графа G. С другой стороны, N [ Sm; Г ( G) ] есть число суперпозиций, в которых копии графа G взаимозаменяемы. Все восемь графов, являющихся суперпозициями двух экземпляров цепи Р4 даны на рис. ТАЛ. [23]
Любая модель данной аксиоматической системы имеет группу автоморфизмов, и графы не являются исключением. Было замечено, что при определенных условиях группу графа-композиции можно охарактеризовать с помощью групп составляющих графов. В настоящей главе представлены результаты о существовании графа с заданной группой и данными структурными свойствами. Глава завершается рассмотрением графов, симметричных относительно вершин и ребер. [24]
Группой графа называется совокупность всех его автоморфизмов; это группа подстановок, действующая на множестве вершин графа. Известно [13], что каждая конечная группа изоморфна группе некоторого графа, но не известно, вообще говоря, является ли данная группа подстановок группой графа. [25]
Соответствующий критерий для групп графов не известен. [26]
Множество всех автоморфизмов данного графа образует группу относительно операции композиции автоморфизмов. Автоморфизмы графа G порождают группу подстановок вершин Г ( С), наз. Реберная и вершинная группы графа G без петель и кратных ребер изоморфны тогда и только тогда, когда граф G имеет не более одной изолированной вершины и никакая его компонента связности не является изолированным ребром. Для каждой конечной группы F существует граф, группа автоморфизмов к-рого изоморфна F. В то же время существуют группы подстановок на множестве из га элементов, не являющиеся вершинной группой никакого графа с га вершинами. А с и м-метричным называется граф, не имеющий автоморфизмов, отличных от тождественного. При п - - оо почти все графы с га вершинами являются асимметричными. [27]
Каждый обыкновенный граф обладает, по крайней мере, одним собственным изоморфизмом, а именно, тривиальным изоморфизмом, при котором каждая вершина и ребро соответствуют самим себе. Изоморфизм графа с самим собой называется автоморфизмом. Совокупность автоморфизмов графа образует группу, называемую группой графа. [28]
Как только эта процедура будет развита, мы тем самым докажем соответствующую теорему. Следовательно, при подобном положении дел чрезвычайно удобно в противоположность мудрому предостережению Уленбека сначала представить доказательство, а затем уже сформулировать теорему. Чтобы вычислить цикловой индекс группы Гг ( Я, Кр), мы определяем вершинно-реберную группу графа G, которая обозначается через Г01 ( С), как группу подстановок, индуцированную группой Г ( G) и переставляющую и вершины, и ребра графа G. Записывая цикловой индекс этой группы, мы будем различать циклы, составленные из разных переставляемых объектов, используя для этого два множества переменных: sk - для вершин и ti, - для ребер. [29]
Как только эта процедура будет развита, мы тем самым докажем соответствующую теорему. Следовательно, при подобном положении дел чрезвычайно удобно в противоположность мудрому предостережению Уленбека сначала представить доказательство, а затем уже сформулировать теорему. Чтобы вычислить цикловой индекс группы 1 ( Я, Кр), мы определяем вершинно-реберную группу графа G, которая обозначается через F0ll ( G), как группу подстановок, индуцированную группой Г ( G) и переставляющую и вершины, и ребра графа G. Записывая цикловой индекс этой группы, мы будем различать циклы, составленные из разных переставляемых объектов, используя для этого два множества переменных: sk - для вершин и tk - для ребер. [30]
Страницы: 1 2 3