Вершинно-транзитивный граф

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 23:02, 18 марта 2016.

Пусть - произвольная группа. Возьмем подмножество ее элементов:

т.е.

TemplateDifinitionIcon.svg Определение «Определение 1»

Графом Кэли называется неориентированный граф с множеством вершин и множеством ребер

Свойства графа Кэли:[1]

  1. полный
  2. связен
  3. Диаметр есть , т.ч.:
TemplateTheoremIcon.svg Теорема Теорема 1

Граф Кэли - вершинно-транзитивный.

Доказательство

поставим в соответствие подстановку на

Имеет место следующая система импликации:

рассматриваем, как ребро,

Т.о. Т.к. граф вершинно-транзитивен.


TemplateTheoremIcon.svg Теорема Упражнение 1
К упражнению 8.1

Дано: неорграф (граф Петерсона).

Доказать: неорграф не является графом Кэли ни для какой группы.

Доказательство

Диаметр графа равен 2 (минимальное расстояние от вершины до вершины); - группа действует на 10 вершинах. Граф Петерсона не является графом Кэли ни для какой группы всего таких групп ровно 2: циклическая и группа диэдра , где под группой диэдра понимается группа симметрии правильного многоугольника, включающая как вращения, так и осевые симметрии.


Граф Кэли для симметрической группы

TemplateDifinitionIcon.svg Определение «Определение 2»
Множество всех перестановок множества X (т.е. биекций из X в X) с операцией композиции образуют группу, которая называется симметрической группой или группой перестановок X. Обычно обозначается

множество транспозиций, Зададим граф следующим образом:

TemplateExampleIcon.svg Пример Пример 1
Dmdg keli 2.PNG


TemplateLemmaIcon.svg Лемма «Утверждение 1»

Пусть - множество транспозиций из . Тогда и только тогда порождает когда соответствующий граф связен.[2]


TemplateTheoremIcon.svg Теорема Утверждение 2
n = 3
n = 4

Пусть множество транспозиций из Тогда следующие условия эквивалентны:

1) минимальное множество, порождающее

2) Граф дерево (связный граф без циклов).

3) Произведение всех элементов из в любом порядке есть цикл длины

Пример:

дает цикл длины 3.

Неизоморфные графы дают всевозможные системы образов.

Доказательство

Требуется минимальный граф, связный, с минимальным числом ребер: связный граф имеет ребро, а связный граф с минимальным числом ребер есть дерево.

Предположим, что граф - дерево. Чтобы он порождал , он должен быть связным. Выкидываем одно из ребер граф не связан. Т.о. число ребер равно [3]


TemplateTheoremIcon.svg Теорема Свойство 1
Dmdg keli 5.PNG

Пусть

а) В графе нет треугольников.

б) - двудолен.

Доказательство
К доказательству свойства)

Пусть есть треугольник (см. рис), и и Тогда ( не является транспозиций). Произведение двух треугольников дает либо цикл длины 3, либо 2 цикла длины 2.


TemplateDifinitionIcon.svg Определение «Определение 3»

Левым смежным классом группы по множеству — множество . Аналогично определяется и правый смежный класс .

TemplateLemmaIcon.svg Лемма «Теорема 2»

Пусть Тогда если , т.ч.:

множество правых смежных классов,

то вершинно-транзитивный граф смежных классов.


Регулярный (однородный граф)

TemplateDifinitionIcon.svg Определение «Определение 4»

Граф называется регулярным (однородным), если степени всех его вершин равны. Степенью регулярного графа называют степень его вершин.

Реберный граф

TemplateDifinitionIcon.svg Определение «Определение 5»

Для произвольного графа реберный граф определен следующими условиями:

  1. Вершины и смежны в когда ребра и смежны в

Граф пересечений

TemplateDifinitionIcon.svg Определение «Определение 6»

Произвольный граф называется графом пересечений, если и только если существует такое множество и такое покрытие этого множества такое, что где:

  1. Вершины и - смежны, если и
  • Дополнение графа имеет в качестве множества вершин множество но если 2 вершины в смежны они НЕ смежны в
  • Регулярные графы степени 3 - кубические графы.

Примечания

  1. Доказать все свойства самостоятельно.
  2. Доказать самостоятельно.
  3. Остальное доказать самостоятельно.