WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 ||

Совершенная раскраска графа тесно связана со структурой группы автоморфизмов графа. Основным способом построения совершенных раскрасок (в произволных графах) является так называемый орбитный метод, суть которого выражается в следующем факте (см., например, [28]). Пусть G произвольный обыкновенный граф с группой автоморфизмов H и H некоторая подгруппа группы H. Относительно H множество вершин графа G разбивается на орбиты. Раскрашивая каждую из орбит своим цветом, получим совершенную раскраску графа G. В [10], [11] Годсил использует совершенные раскраски (equitable partitions) для изучения схем отношений и групп автоморфизмов графов. О группе автоморфизмов графа можно сделать некоторые выводы по собственным значениям и собственным векторам графа, которые связаны с собственными значениями матрицы совершенной раскраски следующим образом: характеристический многочлен матрицы совершенной раскраски делит характеристический многочлен матрицы смежности графа [28].

Ранее изучались совершенные раскраски в два цвета некоторых графов и семейств графов: n-мерного двоичного куба [27], графа бесконечной прямоугольной решетки [3], плоских триангуляций минимальной степени пять [19], графа Джонсона [25].

Голомб и Уэлш рассматривали совершенные коды в Zn [12].

Они доказали, что для всякой длины n существуют совершенные коды, исправляющие одну ошибку, в метрике Ли. Такие коды могут рассматриваться либо как регулярные периодические замощения евклидова пространства Rn сферами Ли радиуса 1 или как периодические замощения решетки Zn шарами радиуса 1. Также рассматривались совершенные коды радиусов больше 1 и были получены некоторые результаты о несуществовании таких кодов.

Задача исследования центрированных функций и совершенных раскрасок на бесконечных транзитивных решетках также связана с теорией двумерных слов. Центрированные функции и совершенные раскраски могут рассматриваться как двумерные слова над конечным алфавитом слов и значений функции соответственно. В диссертации вводится понятие R-продолжаемого слова и используется для доказательства периодичности центрированных функций и совершенных раскрасок. Этот метод или его модификации могут быть использованы для изучения периодичности других двумерных слов. Периодичность двумерных слов ранее уже изучалась. Следующая гипотеза о связи комбинаторной сложности и периодичности известна как гипотеза Нива (Nivat’s conjecture) [13]: если существует пара целых чисел (n, m), такая что функция комбинаторной сложности pw(n, m) двумерного слова w удовлетворяет условию pw(n, m) mn, то w имеет по крайней мере один вектор периодичности.

Слабые формы этой гипотезы для pw(n, m) mn/144 и для pw(n, m) mn/16 были доказаны в [8] и [16], соответственно.

Первая глава диссертации посвящена периодичности совершенных раскрасок радиуса 1 плоской бесконечной прямоугольной решетки.

Основной результат этой главы сформулирован в теореме 1, в которой утверждается, что для любой допустимой матрицы радиуса 1 существует периодическая совершенная раскраска. Матрица называется допустимой, если существует совершенная раскраска бесконечной прямоугольной решетки с такой матрицей. Для того, чтобы доказать эту теорему, предварительно доказываются восемь вспомогательных предложений (предложения 1-8). Кроме того, доказано, что периодическая раскраска может быть получена из непериодической специальными операциями, называемыми сдвигами бинарных диагоналей. Бинарная диагональ это диагональ, состоящая из двух чередующихся цветов, под сдвигом бинарной диагонали подразумевается перестановка цветов внутри диагонали. В случае существования непериодической совершенной раскраски с данной матрицей для этой матрицы существует бесконечное число (континуум) совершенных раскрасок. Метод получения периодических раскрасок сдвигами бинарных диагоналей согласуется с известным в теории кодирования методом свитчинга, используемого для получения новых кодов из известных ранее. Основная идея метода свитчинга состоит в следующем: в произвольном двоичном коде C длины n рассмотрим некоторое подмножество M кодовых слов. Если найдется в En подмножество M, отличное от множества M, причем множество C = (C\M)M является двоичным кодом с теми же параметрами, что и у кода C, то будем говорить, что код C получен из кода C свитчингом множества M, см. [18]. Впервые свитчинговый способ построения 1-совершенных кодов был предложен Васильевым [21]. Далее свитчинговый метод разввался в работах Моллара, Августиновича и Соловьевой [1], [2], Малюгина [24], Кротова [23].

В качестве следствия из Теоремы 1 получается, что для любой совершенной раскраски бесконечной прямоугольной решетки существует совершенная раскраска некоторого тороидального графа (Следствие 1). Отсюда вытекает, что мы можем использовать свойства совершенных раскрасок конечных графов для доказательства недопустимости матриц.

Граф бесконечной прямоугольной решетки является очень популярным объектом при изучении различных комбинаторных конструкций, в частности, упаковок, покрытий и замощений [17, 14]. Довольно часто при этом возникают следующий вопрос: если некоторая конструкция на графе G(Z2) существует, то следует ли отсюда существование конструкции с теми же параметрами, обладающей свойством периодичности Ответ на этот вопрос не всегда оказывается положительным. Например, в работах [17] и [14] рассматривались замощения плоскости плитками. Оказалось, что для некоторого набора плиток замощение существует, но все такие замощения оказываются непериодическими.

Во второй главе диссертации описываются параметры совершенных раскрасок бесконечной прямоугольной решетки в три цвета.

Ранее в [3] Аксенович перечислила все допустимые матрицы совершенных раскрасок радиуса 1 в 2 цвета. Основным результатом второй главы диссертации является Теорема 2, в которой утверждается, что всякая совершенная раскраска радиуса 1 бесконечной плоской прямоугольной решетки в три цвета имеет одну из перечисленных в этой теореме матриц (с точностью до перестановки строк и столбцов, соответствующей некоторому переобозначению цветов). Таких матриц оказалось 21.

Для каждой матрицы приведены примеры соответствующих раскрасок. Матрица совершенной раскраски называется допустимой, если существует совершенная раскраска бесконечной прямоугольной решетки с этой матрицей. Из 21 допустимой матрицы для пять матриц порождают непериодические совершенные раскраски.

Для доказательства Теоремы 2 было доказано 12 предложений о необходимых условиях допустимости матрицы, которые имеют самостоятельную ценность, так как выполняются для произвольного числа цветов, а некоторые не только для бесконечной прямоугольной решетки, но и для других широких классов графов.

В третьей главе рассматриваются совершенные раскраски радиуса больше 1 на бесконечной прямоугольной решетке.

Доказано, что любая совершенная раскраска радиуса r > является периодической (Теорема 3), в отличие от случая r = 1, в котором существуют также непериодические раскраски. Получена верхняя граница на период, то есть по существу доказана конечность числа совершенных раскрасок фиксированного радиуса больше 1. Приведены некоторые конструкции и примеры совершенных раскрасок произвольных графов и графа бесконечной прямоугольной решетки. Найден общий способ получения всех совершенных раскрасок бесконечной прямоугольной решетки заданного радиуса, большего 1, в заданное число цветов. Для доказательства периодичности используется метод R-продолжаемых слов, который заключается в следующем. Будем говорить, что двумерное слово является Rпродолжаемым, если для любых x, z Z2 равенство |BR(x) = |BR(z) влечет |BR+1(x) = |BR+1(z). Здесь равенство |BR(x) = |BR(z) означает, что (x+y) = (z+y) для любых y, таких что y R. Лемма 2 гласит, что если двумерное слово над конечным алфавитом является R-продолжаемым для некоторого R 0, то периодическое. Таким образом, вместо периодичности можно доказывать R-продолжаемость для некоторого R;

в некоторых случаях это оказывается удобным.

Четвертая глава посвящена центрированным и квазицентрированным функциям.

Метод R-продолжаемых слов оказался полезным при доказательстве следующего результата: любая ограниченная целочисленная центрированная функция любого радиуса на G(Z2) является периодической (теорема 4). Функция на вершинах графа называется квазицентрированной радиуса r, если сумма ее значений по любой сфере радиуса r равна нулю. Доказано, что квазицентрированные функции четного радиуса периодические, для нечетных радиусов существуют как периодические, так и непериодические квазицентрированные функции (теорема 5). В разделе 4.2 приведены конструкции непериодических центрированных функций радиуса 1 в G(Zn) (лемма 3). Аналогичные результаты получены для бесконечной треугольной и гексагональной решеток (теоремы 6, 7, 8).

В заключении приводится перечень основных результатов диссертации и некоторые нерешенные проблемы.

Список литературы [1] Avgustinovich S. V., Solov’eva F. I. Construction of perfect binary codes by sequential translations of the i-components, Proc. of Fifth Int. Workshop on Algebraic and Comb. Coding Theory. Sozopol, Bulgaria. June (1996) 9-14.

[2] Avgustinovich S. V., Solov’eva F. I. Construction of perfect binary codes by sequential translations of an -components, // Problems of Inform. Transm. 33 (3) (1997) 202-207.

[3] Axenovich M. On multiple coverings of the infinite rectangular grid with balls of constant radius. // Discrete Mathematics, 268 2003, p. 31–49.

[4] Brouwer A. E. A note on completely regular codes. // Discrete mathematics, 1990, V. 82, P. 115-117.

[5] Berthe V., Vuillon L. Tilings and rotations: a two-dimensional generalization of Sturmian sequences // Discrete Math., (2000), p. 27–53.

[6] Camion P., Courteau B., Delsarte Ph. On r-partition designs in Hamming spaces // Appl. Algebra in Engrg., Comm.

Compt. (AAECC). 1992. V. 2. P. 147–162.

[7] Delsarte P. An algebraic approach to the association schemes of coding theory // Philips Research Reports Supplements, Vol. 10, 1973.

[8] Epifanio C., Koskas M., Mignosi F. On a conjecture on bidimensional words // Theoretical Computer Science, v.n.1-3, p.123-150, 2003.

[9] Fon-Der-Flaass D.G. A bound on correlation immunity // Siberian Electronic Mathematical Reports 4 (2007) 133-135.

[10] Godsil C. Equitable partitions. // Combinatorics, Paul Erds is Eighty Vol. 1. Budapest, 1993. P. 173–192.

[11] Godsil C. D., Martin W. J. Quotients of association schemes // J. Combin. Theory. Ser. A. 1995. V. 69, N 2. P. 185–199.

[12] Golomb W., Welch L. R. Perfect codes in the Lee metric and the packing of polyominoes // SIAM J. Appl. Math. 18 (1970) 302-317.

[13] Nivat M., Invited talk at ICALP’97.

[14] Penrose R. The role of aethetics in pure and applied mathematical reserch. // Bull. Inst. Math. Appl. 1974. V. 10.

P. 266-271.

[15] Preparata F. P. A Class of optimum nonlinear double-errorcorrecting codes // Inform. and Control. 1968. V. 13, N 5. P.

378–400.

[16] Quas A., Zamboni L. Periodicity and local complexity // Theoretical Computer Science, v. 319, Issue 1-3, p. 229 - 240, 2004.

[17] Robinson R. Undecidabilty and nonperiodicity for tilings of the plane. // Inventiones Math. 1971. V. 12. P. 177–209.

[18] Solov’eva F. I. On perfect codes and related topics // Com2Mac Lecture Note Series 13, Pohang 2004.

[19] Августинович С. В., Бородин О. В., Фрид А. Э. Дистрибутивные раскраски плоских триангуляций минимальной степени 5. // Дискретный анализ и исследование операций. 2001. Т.8, № 3. С. 3–16.

[20] Августинович С. В., Васильева А. Ю. Восстановление центрированной функции по ее значениям на двух средних слоях гиперкуба // Дискр. анализ и исслед. операций, Т.

10, N. 2, 2003, P.3–16.

[21] Васильев Ю. Л. О негрупповых кодах // Проблемы кибернетики. М, Наука, 1962. Вып. 8. С. 337-339.

[22] Визинг В. Г. Дистрибутивная раскраска вершин графа // Дискрет. анализ и исслед. операций. 1995. Т. 2, № 4. С.

3–12.

[23] Кротов Д. С. Нижние границы на число m-квазигрупп порядка 4 и число совершенных двоичных кодов, // Дискр.

анализ и исслед. опер., 1 (7) 2 (2000) 47–53.

[24] Малюгин С. А. О нижней границе на число совершенных двочиных кодов // Дискр. анализ и исслед. опер., 1 (6) (1999) 44–48.

[25] Могильных И. Ю. О регулярности совершенных раскрасок графа Джонсона в два цвета // Проблемы передачи информации, 2007, т. 43, вып. 4, с. 37–44.

[26] Семаков Н. В., Зайцев Г. В., Зиновьев В. А. Равномерно упакованныхе коды // Проблемы передачи информации, том VII, Вып.1, 1971, стр. 38–50.

[27] Фон-Дер-Флаасс Д. Г. Совершенные 2-раскраски гиперкуба. // Сиб. мат. журнал, 48:4 (2007), 923–930.

[28] Цветкович Д., Дуб М., Захс Х. Спектры графов. Киев, Наукова думка, 1984. С. 121–138.

Публикации автора по теме диссертации [29] Puzynina S. A. Perfect colorings of the infinite rectangular grid // Bayreuther Mathematischen Schriften, Heft 74, 2005, p. 317-331.

[30] Puzynina S. A., Avgustinovich S. V. On periodicity of twodimensional words // CANT2006: EMS Summer School, International School and Conference on Combinatorics, Automata and Number Theory, Preproceedings.

[31] Puzynina S. A., Avgustinovich S. V. On periodicity of twodimensional words, Theoretical Computer Science 391 (2008), p. 178-187.

[32] Пузынина С. А. Периодичность совершенных раскрасок радиуса r > 1 бесконечной прямоугольной решетки, Материалы VI молодежной научной школы по дискретной математике и ее приложениям (Москва, 16-21 апреля 2007г.).

Часть II. Под редакцией А.В.Чашкина. 2007. С.29-[33] Пузынина С. А. Периодичность совершенных раскрасок бесконечной прямоугольной решетки // Дискрет. анализ и исслед. операций. Сер. 1. 2004 Т. 11, №1. С. 79-92.

[34] Пузынина С. А. Совершенные раскраски вершин графа G(Z2) в три цвета. //Дискрет. анализ и исслед. операций.

Сер. 2. 2005 Т. 12, №1. С. 37-54.

[35] Пузынина С. А. Совершенные раскраски бесконечной прямоугольной решетки. Труды VI международной конференции "Дискретные модели в теории управляющих систем", 2004, с. 209.

[36] Puzynina S. A. On perfect colorings of the infinite rectangular grid. Материалы российской конференции "Дискретный анализ и исследование операций", 2004, с. 97.

[37] Пузынина С. А. Обзор по совершенным раскраскам и другим обобщениям совершенных кодов на бесконечных транзитивных решетках. // Материалы международной конференции "Математика в современном мире", 2007, с. 279280.

Пузынина Светлана Александровна Совершенные раскраски бесконечной прямоугольной решетки Автореферат диссертации на соискание учёной степени кандидата физико-математических наук – Подписано в печать 02.04.2008. Формат 60x84 1/16.

Pages:     | 1 ||






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»