Министерство образования и науки

Российской федерации

Федеральное агентство по образованию

Новосибирский государственный университет

Механико-математический факультет

Кафедра теоретической кибернетики

Выпускная квалификационная работа бакалавра

КИСЕЛЬКОВА Мария Максимилиановна

О хроматическом числе некоторых графов

Кэли

Научный руководитель к.т.н. Е.В. Константинова

Новосибирск 2009

РЕФЕРАТ

Дипломная работа называется ѕО хроматическом числе некоторых графов Кэлиї. Объём работы составляет 21 страниц, в работе 6 рисунков, 3 таблицы, при выполнении работы использовано 6 источников.

Ключевые слова: граф Кэли, хроматическое число, симметрическая группа, транспозиция, префикс-реверсал.

Объектом исследования являются графы Кэли симметрической группы S_n , порожденной транспозициями при n ≥ 3 и префикс-реверсалами при n = 4 и n = 5.

Целью дипломной работы является исследование хроматических и структур- ных свойств данных графов Кэли.

В дипломной работе доказано, что хроматическое число графа Кэли на S₅

равно трем.

Графы Кэли применяются в различный областях. Например, в молекулярной биологии перестановки используются для представления последовательности ге- нов в хромосомах и геномах. Некоторые операции над перестановками называ- ются реконструкциями генома и носят эволюционный характер. Также графы Кэли широко применяются для представления компьютерных сетей. Каждая вершина графа соответствует какому-нибудь элементу (модулю, выключателю), а рёбра линиям соединения. В силу вершинной транзитивности графов, все вер- шины ѕравноправныї, что и требуется в схемах.

Содержание

1 ВВЕДЕНИЕ 4

1.1 Основные определения и результаты . . . . . . . . . . . . . . 4

2 ТРАНСПОЗИЦИОННЫЙ ГРАФ КЭЛИ 6

3 ПРЕФИКС-РЕВЕРСАЛЬНЫЙ ГРАФ

И ЕГО СВОЙСТВА 7

3.1 Иерархическая структура S_n (P R) . . . . . . . . . . . . . . . . 7

^{3.2 Структурные свойства S}_n ^{(P R) . . . . . . . . . . . . . . . . . . 8}

^{3.3 Граф S}₄^{(P R) и его свойства . . . . . . . . . . . . . . . . . . . 9}

^{3.3.1 Хроматические cвойства S}₄^{(P R) . . . . . . . . . . . . . 9}

^{3.3.2 Структурные свойства S}₄ ^{(P R) . . . . . . . . . . . . . 10}

^{3.3.3 Число раскрасок S}₄^{(P R) . . . . . . . . . . . . . . . . . 11}

^{3.4 Граф S}₅^{(P R) и его свойства . . . . . . . . . . . . . . . . . . 14}

^{3.4.1 Структурные свойства S}₅ ^{(P R) . . . . . . . . . . . . . . 14}

^{3.4.2 Хроматические свойства S}₅^{(P R) . . . . . . . . . . . . 14}

Список литературы 22

1 Введение

1.1 Основные определения и результаты

Введем основные определения, которые нам понадобятся в дальнейшем. Пусть Γ группа, Γ =< S >, где S некоторое порождающее множество

^{группы, такое, что e ∈/}

S и S = S⁻¹ . Граф Кэли G = C ay(Γ, S) = (V, E)

^{удовлетворяет следующим условиям: множество вершин соответсвует эле-}

ментам группы, т.е. V = Γ, и множество ребер E = {(g, gs), g ∈ Γ, s ∈ S}. Известно [4], что графы Кэли являются вершинно-транзитивными и |S|- регулярным. Также известно, что не всякий вершинно-транзитивный граф

является графом Кэли.

Вершинная раскраска графа G = (V, E) это отображение c : V → C . Элементы множества C называют цветами. Раскраска называется пра-

вильной, если c(u) = c(v), когда u и v смежны. Множество вершин од- ного цвета является независимым и называется одноцветным классом. В k-раскраске графа используется k цветов и эта раскраска разбивает мно- жество V на k одноцветных классов. Хроматическое число χ(G) графа G определяется как наименьшее k, для которого граф имеет k-раскраску.

^{Граф называется k-раскрашиваемым, если χ(G) ≤ k и k-хроматическим,}

^{если χ(G) = k. Пусть ∆ максимальная степень вершин в графе G. Спра-}

ведлива следующая теорема.

Теорема Брукса. Пусть G = (V, E) связный неполный граф, ∆(G) ≥ 3. Тогда, χ(G) ≤ ∆(G).

Симметрическая группа S_n группа перестановок на множестве {1, . . . , n}. Будем записывать перестановку π как π = [π₁ , π₂, . . . , π_n ], где π_i = π(i), для каждого i ∈ {1, . . . , n}. Транспозицией t_ij называется перестановка, которая меняет местами элементы i и j:

[. . . , π_i , . . . , π_j , . . .]t_ij = [. . . , π_j , . . . , π_i , . . .].

Префикс-реверсалом r_i называется операция, действующая на перестанов- ку π ∈ S_n и меняющая порядок элементов внутри интервала [1, i + 1], 1 ≤ i < n.

[π₁, . . . , π_i+1 π_i+2 , . . . , π_n ]r_i = [π_i+1 , . . . , π₁ π_i+2 , . . . , π_n ].

Транспозиционный граф Кэли S_n (T ) определяется на симметрической груп- пе S_n , в которой порождающее множество T состоит из транспозиций t_ij ,

_{T = {tij , 1 ≤ i < j ≤ n}, |T | = C 2 =} ⁿ⁽ⁿ⁻¹⁾ _.

ⁿ ₂

^{Префикс-реверсальный граф Кэли S}_n ^{(P R) определяется на группе S}_n ^{, в ко-}

торой порождающее множество P R состоит из префикс-реверсалов, P R =

{r_i ∈ S_n , 1 ≤ i < n}, |P R| = (n − 1). Данный граф известен в иностран- ной литературе [6], как pancake graph, в связи с открытой проблемой его

диаметра.

Автоморфизмом графа называется изоморфизм графа G на себя. Граф называется вершинно-транзитивным, если для любых двух вершин гра- фа u и v существует автоморфизм графа σ, такой что σ(u) = v.

Граф G = (V, E) называется двудольным, если множество вершин V можно разбить на два подмножества V₁ и V₂ таким образом, что каждое ребро графа G соединяет вершины из разных множеств. Граф, все вер- шины которого имеют одинаковую степень называется регулярным. Диа- метром d(G) связного графа G называется длина кратчайшей простой (u, v) – цепи, u, v ∈ V (G).

^{Множество попарно несмежных вершин в графе G называется неза-}

висимым. Максимальное по мощности множество M таких вершин на- зывается максимальным независимым множеством, |M | = α(G), α(G) называется числом независимости. Из [1] известно, что для хроматиче- ского числа χ(G) произвольного графа G справедлива следующая оценка:

_{|V (G)|}

^d _α(G) ^{e ≤ χ(G) (1.1)}

Множество вершин X таких, что любая вершина графа либо принадлежит X , либо смежна с вершинами из X называется доминирующим. Число доминирования определяется как мощность наименьшего доминирующего множества в графе, γ(G) = min|X |.

^{Приведем также несколько основных формул комбинаторики, которые}

использованы в работе при подсчете числа раскрасок:

Выбор без возвращения с учетом порядка. Общее количество различных наборов при выборе k элементов из n без возвращения и с учетом порядка

_{вычисляется как Ak = n(n − 1) · . . . · (n − k + 1) =} n! _{и называется числом}

n

размещений из n элементов по k элементов.

(n−k)!

Выбор без возвращения без учета порядка. Общее количество наборов при выборе k элементов из n без возвращения и без учета порядка равняется

_{C k n!}

n ⁼ _(n−k)!k! ^{и называется числом сочетаний из n элементов по k.}