Дослідження розкладів та нумерацій графів

В дисертаційній роботі доведено ряд тверджень щодо автоморфізмів 1-факторизацій графа Q_n. Відомо, що n-вимірний куб Q_n допускає квадратну 1-факторизацію при кожному n. Дисертантом доведено, що квадратна 1-факторизація графа Q_n єдина з точністю до ізоморфізму, для кожного n; група автоморфізмів квадратної 1-факторизації графа Q_n співпадає з групою автоморфізмів цього графа. Запропоновано алгоритм, за яким складено програму і знайдено число 1-факторизацій графа Q₅ з точністю до ізоморфізму.

В загальному вигляді описано метод побудови реберної нумерації дерев, яку названо стандартною. Введено поняття вершинного яруса центрального дерева, повного ярусного (r₀, r₁, … ,r_k)-регулярного дерева, монотонно спадного та монотонно зростаючого дерев. Із застосуванням стандартної нумерації доведено антимагічність подвійних зірок порядку n (n?5), r-регулярних дерев та повних k-ярусних (r₀, r₁, … ,r_k)-регулярних монотонно спадних дерев при k 2. Знайдено одну з антимагічних нумерацій простого ланцюга, простого цикла, повного графа, голландського вітряка, графів С_nР₃ і B(C_n, P₂, C_n). Складено алгоритм перевірки графа на антимагічність. Отримані результати, що стосуються нумерацій графів, можна охарактеризувати, як загальний підхід до знаходження антимагічних нумерацій певних спеціальних графів та дослідження часткових випадків при застосуванні програми, яка реалізує побудований алгоритм.

СПИСОК ОПУБЛІКОВАНИХ АВТОРОМ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

Семенюта М. Ф. Антимагічна нумерація графів // Вісник Київського національного університету ім. Т. Шевченка. Серія: фізико-математичні науки. - 2005. - Вип. №3. - С. 90-98.

Семенюта М. Ф. 1-факторизації булевих кубів // Вісник Київського національного університету ім. Т. Шевченка. Серія: фізико-математичні науки. - 2006. - Вип. №2. - С. 50-56.

Семенюта М. Ф. Циклічні пентагональні розклади повного графу // Вісник Київського національного університету ім. Т. Шевченка. Серія: фізико-математичні науки. - 2006. - Вип. №3. - C. 53-59.

Семенюта М. Ф. Циклічні розклади графу К_n на графи малих порядків // Вісник Тернопільського державного технічного університету ім. І. Пулюя. - 2006. - Т.11, №4. - С. 160-170.

Semenyuta M. F. Antimagic graph labelings // Тези доповідей V-ої Міжнародної алгебраїчної конференції в Україні. - Одеса: Одеський нац. університет ім. І. І. Мечникова, 2005. - C. 184.

Семенюта М. Ф., Сорока О. О. 1-факторизації булевих кубів // Матеріали IX Міжнародної науково-практичної конференції "Наука та освіта - 2006" Дніпропетровськ: Наука і освіта, 2006. - Т. 13. С. 68-71.

Семенюта М. Ф. Циклічні розклади К₂₁ на (7,10)-графи // Одинадцята міжнародна наукова конференція імені академіка М. Кравчука, Київ: Матеріали конф. - К.: ТОВ «Задруга», 2006. - С. 588.

Semenyuta M. Cyclic pentagonal decompositions of К₁₁ // Тези доповідей Міжнародної конференції по радикалах ICOR-2006. - Київ.: Київський нац. університет ім. Т. Шевченка, 2006. - С. 60-61.

Семенюта М. Ф., Сорока О. О. Побудова циклічних пентагональних розкладів повних графів// Матеріали першого міжвузівського науково-практичного семінару “Комбінаторні конфігурації та їх застосування”. - м. Кіровоград: Видавництво ДЛАУ, 2006 р. - С. 43-44.

Semenyuta M. F. On cyclic decompositions of graphs // Тези доповідей VI-ої Міжнародної алгебраїчної конференції в Україні. - Кам'янець-Подільський: Кам'я нець-Подільський держ. університет, 2007. - С. 182-183.

АНОТАЦІЯ

Семенюта М. Ф. Дослідження розкладів та нумерацій графів. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.01.08 - математична логіка, теорія алгоритмів і дискретна математика.-Київський національний університет імені Тараса Шевченка, Київ, 2008.

В дисертації отримано ряд нових результатів про розклади графів та нумерації. Побудовою доведено існування циклічного (К₂₁,G)-розкладу для кожного із 132 неізоморфних зв'язних (7,10)-графів G. В роботі представлені результати про циклічні пентагональні розклади графа К_п, серед яких спосіб побудови базових компонент таких розкладів, алгоритми і програми побудови списку та специфікаційних інваріантів для (К₁₁,С₅)- і (К₂₁,С₅)-розкладів. Для розрізнення-ототожнення циклічних (К₁₁,С₅)- і (К₂₁,С₅)-розкладів введено графічні інваріанти. Знайдено список неізоморфних циклічних (К₁₁,С₅)-розкладів, верхню оцінку числа неізоморфних циклічних пентагональних розкладів графа К_п, нижні оцінки числа неізоморфних циклічних(К₂₁,С₅)- та (K₁₉, G)-розкладів, коли G=П - трикутна призма, G=В - барвінок.

В дисертаційній роботі проведено дослідження 1-факторизацій графа Q_n, зокрема графа Q₅. Його результатом є знаходження числа неізоморфних 1-факторизацій графа Q₅, доведення єдиності квадратної 1-факторизації графа Q_n для кожного n. Також доведено, що група автоморфізмів квадратної 1-факторизації графа Q_n співпадає з групою автоморфізмів цього графа.

В дисертації описано метод побудови стандартної нумерації дерев і з її допомогою встановлено антимагічність подвійних зірок, r-регулярних дерев, k-ярусних (r₀, r₁, …, r_k)-регулярних монотонно спадних дерев. Знайдено одну з антимагічних нумерацій простих ланцюгів Р_n (n>2), простих циклів С_n (n3), повних графів К_n. Доведено антимагічність голландських m-вітряків, графів С_nР₃ і B(C_n, P₂, C_n), побудовано алгоритм перевірки графа на антимагічність.

Ключові слова: граф, циклічний розклад, пентагональний розклад, n-вимірний (булів) куб Q_n, 1-факторизація, квадратна 1-факторизація, специфікаційні інваріанти, графічні інваріанти, антимагічна нумерація, дерево.

АННОТАЦИЯ

Семенюта М. Ф. Исследование разложений и нумераций графов. -Рукопись.

Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.01.08 - математическая логика, теория алгоритмов и дискретная математика. - Киевский национальный университет имени Тараса Шевченко, Киев, 2008.

Первые исследования, относящиеся к истокам теории разложений графов, велись в ХIХ столетии, их результатами были публикации о существовании и построении штейнеровых и киркмановых систем троек. В современной терминологии ШСТ порядка n - это разложения полного графа К_n на m-циклы при m=3. Условия существования разложений полных графов на графы малых порядков найдены Ж. Бермондом, Ш. Хуанг, А. Роса, Д. Сотто. Изучение и решение проблем существования разложений графа К_n на m-циклы описаны в 1999 году в работах М. Андерсена “Decomposing graph into fixed length cycles”, М. Шайна “Cycle decompositions of К_n and К_n-I”. Среди авторов последних публикаций этого направления можно указать Б. Алспаха, Х. Гавласа, А. Виєтри, M. Буратти, С. Ел-Занати, Д. Брянта, Aлена К. Х. Линга. Начало перечисления неизоморфных 1-факторизаций булевого куба Q_n положено А. Петренюком, им найдены соответствующие списки при n=2, 3, 4. В последнее время вводятся новые виды нумераций графов, среди них - реберная антимагическая нумерация. В 1989 году Хартсфилд и Рингель выдвинули предположение, что для произвольного обыкновенного конечного связного графа, отличного от К₂, существует антимагическая реберная нумерация. Также ими высказана гипотеза, что произвольное дерево порядка n (n >2) антимагично, позже эту гипотезу доказали для полных m-арных деревьев Чават и Кришна.

В диссертации получен ряд новых результатов о разложениях графов и нумерациях. С помощью созданных диссертантом алгоритма и программы установлено, что для каждого из 132 неизоморфных связных (7,10)-графов G существует циклическое (К₂₁, G)-разложение, и найдено базовую компоненту одного из таких разложений. Выделен класс спецификационных и графических инвариантов для исследования разложений. Разработан новый способ построения базовых компонент циклического (К_п, С₅)-разложения, для его реализации составлены алгоритмы и написаны программы для случаев циклических (К₁₁, С₅) и (К₂₁, С₅)-разложений. Для различения-отождествления разложений введены графические инварианты. Применение спецификационного инварианта Т(R) и графических инвариантов на множестве циклических (К_п, С₅)-разложений дало возможность получить исчерпывающий список пентагональных разложений графа К₁₁ и нижнюю оценку числа неизоморфных циклических (К₂₁,С₅)-разложений. Доказано необходимое условие изоморфности циклических (К_п,С₅)-разложений. Получена нижняя оценка числа неизоморфных циклических (K₁₉, G)-разложений, когда G=П - треугольная призма, G=В - барвинок.

В диссертационной работе доказан ряд утверждений об автоморфизмах 1-факторизаций графа Q_n. С помощью разработанного диссертантом алгоритма, реализованного программой, найдено число 1-факторизаций графа Q₅ с точностью до изоморфизма. Доказано, что квадратная 1-факторизация графа Q_n единственная с точностью до изоморфизма для каждого n, и группа автоморфизмов квадратной 1-факторизации графа Q_n совпадает с группой автоморфизмов этого графа.

Введены понятия вершинного яруса центрального дерева, полного ярусного (r₀, r₁, …, r_k)-регулярного дерева, монотонно убывающего и монотонно возрастающего деревьев. Описано построение стандартной нумерации деревьев и с ее помощью доказана антимагичность двойных звезд, r-регулярных деревьев, k-ярусных (r₀, r₁, …, r_k)-регулярных монотонно убывающих деревьев. Найдена одна из антимагических нумераций простых цепей Р_n (n>2), простых циклов С_n (n3), полных графов К_n. Доказана антимагичность голландских m-мельниц, графов С_nР₃ и B(C_n, P₂, C_n). Разработан алгоритм проверки конечного графа на антимагичность.

Ключевые слова: граф, циклическое разложение, пентагональное разложение, n-мерный (булев) куб Q_n, 1-факторизация, квадратная 1-факторизация, спецификационные инварианты, графические инварианты, антимагическая нумерация, дерево.

ANNOTATION

Semenyuta M. F. The investigation of graph decompositions and graph labelings. - Manuscript.

Thesis of the dissertation for obtaining of the degree of candidate of sciences in physics and mathematics, speciality 01.01.08 - mathematical logics, theory of algorithms and discrete mathematics. Kyiv Taras Shevchenko University, Kyiv, 2008.

The dissertation contains some new results concerning the decompositions and labelings of graphs. By constructional methods, the existence of a cyclic (K₂₁,G)-decomposition for each from the 132 non-isomorphic connected (7,10)-graphs G is established. In the work, the results about the cyclic pentagonal decompositions of the graph K_n are presented. Among them there is a method of the construction of the basic components of such decompositions, the algorithms and programs of the list constructions and the specification invariants in the cases of the (K₁₁, C₅)- and (K₂₁, C₅)-decompositions. For distinguishing-identification of cyclic (K₁₁, C₅)- and (K₂₁, C₅)-decompositions the graphic invariants are introduced. The lower valuations for the number of nonisomorphic (K₁₉, G)-decompositions are found, when G=П is the triangle prism and when G=B is the periwinkle. 1-factorisation of the graph Q_n for every n is determined. It is proved that the automorphism group of the square 1-factorisation of Q_n coincides with the automorphism group of the graph.

In the dissertation, the method constructing the standard numeration of trees is establisht is described, and with its aid the antymagicity of double stars, r-regular trees, k-storey (r₀, r₁, … ,r_k)-regular monotone decreasing trees. Also, the antimagicities of simple chains P_n (n>2), of simple cycles C_n (n?3), of complete graphs K_n, of holland m-mills, of graph series С_nР₃ and B(C_n, P₂, C_n) are proved, and the antimagicily checking algorithm is proposed.

Key words: graph, cyclic decomposition, pentagonal decomposition, n-dimensional (Boolean) cube Q_n, 1-factorization, square 1-factorization, specifications invariants, graphic invariants, antimagic labeling, tree.

Размещено на Allbest.ru