Библиотека диссертаций Украины Полная информационная поддержка
по диссертациям Украины
  Подробная информация Каталог диссертаций Авторам Отзывы
Служба поддержки




Я ищу:
Головна / Фізико-математичні науки / Математична логіка, теорія алгоритмів і дискретна математика


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



Анотація до роботи:

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

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

В дисертації отримано ряд нових результатів про розклади графів та нумерації. Побудовою доведено існування циклічного (К21,G)-розкладу для кожного із 132 неізоморфних зв’язних (7,10)-графів G. В роботі представлені результати про циклічні пентагональні розклади графа Кп, серед яких спосіб побудови базових компонент таких розкладів, алгоритми і програми побудови списку та специфікаційних інваріантів для (К11,С5)- і (К21,С5)-розкладів. Для розрізнення-ототожнення циклічних (К11,С5)- і (К21,С5)-розкладів введено графічні інваріанти. Знайдено список неізоморфних циклічних (К11,С5)-розкладів, верхню оцінку числа неізоморфних циклічних пентагональних розкладів графа Кп, нижні оцінки числа неізоморфних циклічних(К21,С5)- та (K19, G)-розкладів, коли G=П – трикутна призма, G=В – барвінок.

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

В дисертації описано метод побудови стандартної нумерації дерев і з її допомогою встановлено антимагічність подвійних зірок, r-регулярних дерев, k-ярусних (r0, r1, …, rk)-регулярних монотонно спадних дерев. Знайдено одну з антимагічних нумерацій простих ланцюгів Рn (n>2), простих циклів Сn (n3), повних графів Кn. Доведено антимагічність голландських m-вітряків, графів СnР3 і B(Cn, P2, Cn), побудовано алгоритм перевірки графа на антимагічність.

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

Дисертантом встановлено, що для кожного з 132 існуючих неізоморфних зв’язних (7,10)-графів G існує циклічний (К21, G)-розклад, і знайдено базову компоненту одного з таких розкладів. Під час розгляду циклічних пентагональних розкладів введено поняття кортежу довжин, базового набору довжин. Розроблено спосіб побудови базових компонент циклічного (Кn, С5)-розкладу. Він може бути модифікований на випадок циклічних (Кn, Сm)-розкладів. На основі цього способу знайдено алгоритми і складено програми пошуку списків циклічних (К11, С5)- та (К21, С5)-розкладів. Для розрізнення-ототожнення розкладів введено узагальнений граф верхніх ребер GУВ та графи Inb(R) і Inс(R), що є графічними інваріантами. Застосування специфікаційного інваріанта – таблиці Т(R) та графічних інваріантів у множині циклічних (Кn, С5)-розкладів дало можливість одержати вичерпний список неізоморфних пентагональних циклічних розкладів графа К11 та нижню оцінку числа неізоморфних циклічних (К21, С5)-розкладів. Доведено необхідну умову ізоморфності циклічних (Кп, С5)-розкладів. Знайдено верхню оцінку числа неізоморфних циклічних (Кп, С5)-розкладів, а також нижню оцінку числа неізоморфних циклічних призматичних та барвінкових розкладів графа K19.

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

В загальному вигляді описано метод побудови реберної нумерації дерев, яку названо стандартною. Введено поняття вершинного яруса центрального дерева, повного ярусного (r0, r1, … ,rk)-регулярного дерева, монотонно спадного та монотонно зростаючого дерев. Із застосуванням стандартної нумерації доведено антимагічність подвійних зірок порядку n (n5), r-регулярних дерев та повних k-ярусних (r0, r1, … ,rk)-регулярних монотонно спадних дерев при k 2. Знайдено одну з антимагічних нумерацій простого ланцюга, простого цикла, повного графа, голландського вітряка, графів СnР3 і B(Cn, P2, Cn). Складено алгоритм перевірки графа на антимагічність. Отримані результати, що стосуються нумерацій графів, можна охарактеризувати, як загальний підхід до знаходження антимагічних нумерацій певних спеціальних графів та дослідження часткових випадків при застосуванні програми, яка реалізує побудований алгоритм.

Публікації автора:

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

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

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

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

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

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

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

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

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

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