Київський національний університет
Київський національний університет
імені Тараса Шевченка
Семенюта Марина Фролівна
УДК 519.17
ДОСЛІДЖЕННЯ РОЗКЛАДІВ ТА НУМЕРАЦІЙ ГРАФІВ
01.01.08 – математична логіка, теорія алгоритмів
і дискретна математика
АВТОРЕФЕРАТ
дисертації на здобуття наукового ступеня
кандидата фізико-математичних наук
Київ – 2008
Дисертацією є рукопис.
Робота виконана на кафедрі геометрії Київського національного університету імені Тараса Шевченка, Кабінет Міністрів України.
Науковий керівник: доктор фізико-математичних наук, професор
КИРИЧЕНКО Володимир Васильович,
Київський національний університет
імені Тараса Шевченка, м. Київ,
професор кафедри геометрії.
Офіційні опоненти: доктор фізико-математичних наук, професор
Кривий Сергій Лук’янович,
Інститут кібернетики імені В. М. Глушкова НАН України, м. Київ,
провідний науковий співробітник відділу мікропроцесорної техніки;
кандидат фізико-математичних наук, доцент
ГАНЮШКІН Олександр Григорович,
Київський національний університет
імені Тараса Шевченка, м. Київ,
доцент кафедри алгебри та математичної логіки.
Захист відбудеться 26 травня 2008 року о 14 годині на засіданні спеціалізованої вченої ради Д .001.18 при Київському національному університеті імені Тараса Шевченка за адресою: 03127, м. Київ, проспект акад. Глушкова, 2, корпус 7, механіко-математичний факультет.
З дисертацією можна ознайомитись у Науковій бібліотеці імені М. Максимовича Київського національного університету імені Тараса Шевченка (м. Київ, вул. Володимирська, 58)
Автореферат розісланий 22 квітня 2008 року
Учений секретар
спеціалізованої вченої ради В. В. Плахотник
ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
В теорії розкладів графів вивчаються задачі існування, побудови, переліку розкладів. Історія досліджень в цьому напрямку починалася з публікацій про існування і побудову кіркманових та штейнерових систем трійок. У 1847 році Т. П. Кіркман розв’язав задачу існування систем трійок, що пізніше названі штейнеровими (ШСТ), ним також була поставлена задача про знаходження умов існування кіркманових систем трійок (КСТ). КСТ – це такі ШСТ, які допускають розбиття сукупності своїх трійок на паралельні класи, кожен з яких є розбиттям основної множини на трійки. Необхідну умову існування КСТ встановив Кіркман, а її достатність довели в 1971 році Р. Чоудхурі і Р. Вільсон. В 1960 році Х. Ханані знайшов спектр порядків штейнерових систем четвірок, а в 1966 році А. Роса довів необхідну і достатню умову існування пентагональних систем. По суті, нинішня теорія розкладів є широким узагальненням згаданих понять і результатів. Перші результати вказаного напрямку одержані в теоретико-множинній термінології і пов’язані з вивченням таких комбінаторних конфігурацій, як схеми блоків. З іншого боку, ці конфігурації мають витоки геометричного характеру: у скінченній проективній геометрії ведуться подібні дослідження. Наприклад, Р. Брук і Г. Райзер в роботі “The nonexistence of certain finite projective planes” вивчають скінченні системи точок і прямих – скінченні проективні площини – із застосуванням теорії матриць. Початок сучасної теорії графів заклав у 1937 році Д. Пойа, а конфігурації з точок і відрізків одержали назву “графів” у 1936 році. Назва “граф” запропонована угорським математиком Д. Кьонігом. Оформлення теорії графів, як окремої математичної дисципліни, привело до розширення і переосмислення згаданого класу комбінаторних задач: стало можливим розглядати розклади графів різних видів на підграфи. В статті “Graph factorizations, general triple systems, and cyclic triple systems” Р. Стентона та I. Гулдена прослідковується еквівалентність комбінаторних задач і задач теорії графів. В сучасній термінології ШСТ порядку n – це розклади повного графа Кn на 3-цикли. Вивчення та розв’язання проблем існування розкладів графа Кn на m-цикли описано в 1999 році в роботах М. Андерсена “Decomposing graph into fixed length cycles”, М. Шайна “Cycle decompositions of Кn and Кn–I”. Серед авторів останніх публікацій цього напрямку (в період з 2000 року до теперішнього часу) можна вказати Б. Алспаха, Х. Гавласа, А. Вієтрі, М. Буратті, С. Ел-Занаті, Д. Брянта, Aлена К. Х. Лінга.
Як допоміжні конфігурації у дослідженнях Ф. Коула, Л. Каммінгс, Г. Уайта з’явилися системи груп пар, які тепер називаються 1-факторизаціями. Пізніше вони відокремилися у самостійний клас конфігурацій. Найбільш вивчені 1-факторизації повних графів Кn, які існують при будь-якому парному n; перші результати їх переліку одержані Л. Діксоном і Ф. Саффордом у 1906 році. Цей результат заклав основи дослідженням, пов’язаним зі знаходженням числа неізоморфних
1-факторизацій графа Кn. П. Камероном у 1976 році знайдено найбільш відому оцінку цього числа для досить великих n. Даній проблемі присвячено ряд публікацій – Ч. Лінднера, Е. Мендельсона, А. Роса, Е. Гелінга і багатьох інших. А. Я. Петренюком започатковано перелік неізоморфних
1-факторизацій n-вимірного куба Qn – ним знайдено відповідні списки при n=2, 3, 4.
Узагальнення понять 1-факторизацій, штейнерових і кіркманових систем трійок, зрівноважених блок-схем та інших приводять у 70-х роках минулого століття до задач про розклади графів на підграфи із заданої множини. Одним із піонерів у цьому напрямку досліджень став Р. Вільсон – він дослідив розклади повних графів на ізоморфні підграфи. Далі Ж. Бермонд, Ш. Хуанг, А. Роса, Д. Сотто у 1980 році знайшли умови існування G-розкладу повного графа Кn для випадку, коли G – граф з п’ятьма вершинами і не містить ізольованих вершин. А перед цим у 1977 році подібні дослідження провели Ж. Бермонд та Шонхейм для графа G з чотирма вершинами, узагальнюючи результати численних попередників.
В іншому напрямку теорії відбувається розробка методів побудови розкладів, серед яких історично першим є циклічний метод та споріднені з ним – біциклічний, півобертовий та інші. А. Петренюком розроблюється метод рівновагових перетворень, різновиди якого – метод рівновагових замін, метод Н-перетворень та метод зріз-перетворень. Все це, разом з рекурсивними методами та методами комп’ютерного переліку, дає можливість отримання списків розкладів. Ще на початку XX століття розв’язувалася задача конструктивного переліку розкладів з точністю до ізоморфізму. Першими результатами тут стали перелік неізоморфних ШСТ порядку 13 (де Паскуале, Г. Брунель, К. Цулауф) та вищезгаданий результат Діксона – Саффорда про перелік 1-факторизацій порядку 8.
Поставлені завдання приводять до задачі розрізнення-ототожнення (Q, G)-розкладів; для її вирішення винайдені і застосовуються інваріанти: числові, специфікаційні, графічні та інші. Як наслідок, було одержано списки неізоморфних розкладів графа Кn на повні підграфи, регулярні графи, дерева, колеса, митри, голландські вітряки та інші, а також (Q, G)-розкладів, де Q, G – певні графи. Вказані проблеми вивчаються в роботах Ф. Коула, Е. Мендельсона, Ш. Хуанг, Ж. Дуайєна, А. Роса, Ч. Колбурна, Ч. Лінднера, Х. Роджера, М. Мартінової, А. Петренюка та інших.
Досліджуючи розклади графів на ізоморфні підграфи, А. Роса в 1967 році ввів б- та в-нумерації графів. Роса також показав, що якщо граф G з q ребрами має б-нумерацію, то для кожного натурального числа р повний граф К2qp+1 може бути розкладеним на копії графа G. В останні 30 років потік публікацій, пов’язаних з нумераціями графів, не припиняється. Вводяться нові види нумерацій, серед них антимагічна реберна нумерація. Поняття антимагічного графа було введено Н. Хартсфілд і Г. Рингелем в 1989 році. Вони припустили, що для звичайного скінченного зв’язного графа, відмінного від К2, існує антимагічна реберна нумерація. Також ними висловлено гіпотезу, що довільне дерево порядку n (n>2) антимагічне, в 2002 році цю гіпотезу довели для повних m-арних дерев П. Чават та В. Крішна.
Актуальність теми. В дисертаційній роботі продовжуються дослідження (Q, G)-розкладів, пов’язані з частковими постановками задач, що виникають в залежності від конкретики Q і G: знаходження умов існування (Q, G)-розкладів; знаходження базових компонент та побудова циклічних (Q, G)-розкладів; обчислення числа не ізоморфних (Q, G)-розкладів; проведення конструктивного переліку неізоморфних (Q, G)-розкладів. В дисертації викладено одержані дисертантом результати про циклічні розклади графа К21 на (7,10)-графи, графа К19 на призми і барвінки, про циклічні пентагональні розклади графа Кn, зокрема графів К11 і К21, про
1-факторизації n-вимірного куба Qn та антимагічність деяких класів графів. Ці дослідження органічно вплітаються до описаного раніше розвитку розглядуваного напряму теорії графів.
Зв'язок роботи з науковими програмами, планами, темами. Тема дисертаційної роботи пов’язана з тематикою наукових досліджень кафедри геометрії механіко-математичного факультету Київського національного університету імені Тараса Шевченка. Результати дисертації частково використані при виконанні завдань підрозділу «Геометричні структури та їх застосування» держбюджетної теми 01БФ038-03 (номер державної реєстрації 0101U002479).
Мета і задачі дослідження. Об’єктом дослідження у даній дисертації виступають розклади та нумерації графів. Предметом дослідження є розклади графів на ізоморфні підграфи та реберна антимагічність графів.
Метою дисертаційної роботи є
побудова, перелік циклічних розкладів повних графів на ізоморфні підграфи певних видів і
1-факторизацій n-вимірного куба Qn;
реберна антимагічність графів.
Задачі дослідження:
розв’язання задачі існування циклічного (К21, G)-розкладу для кожного із 132 існуючих неізоморфних зв’язних (7,10)-графів G;
розв’язання задачі переліку циклічних пентагональних розкладів графа Кn для n?1(mod10);
розв’язання задачі знаходження нижньої оцінки числа неізоморфних циклічних (K19, G)-розкладів для випадків, коли G=П – трикутна призма та G=В – барвінок;
проведення конструктивного переліку неізоморфних 1-факторизацій графа Q5, з використанням його групи автоморфізмів;
знаходження числа 1-факторизацій графа Q5 з точністю до ізоморфізму;
дослідження g-гомогенних 1-факторизацій графа Qn;
знаходження антимагічних нумерацій для деяких класів дерев та інших видів графів.
Методи дослідження. В кожному розділі дисертації знайшли застосування методи теорії графів. При побудові циклічних розкладів графів та 1-факторизацій графа Q5 використовувались методи загальної теорії груп, зокрема груп підстановок. При побудові і конструктивному переліку неізоморфних розкладів графів велику роль відіграли методи генерації комбінаторних об’єктів.
Наукова новизна одержаних результатів. Вперше отримано такі результати:
за допомогою складеної дисертантом програми встановлено, що для кожного з 132 існуючих неізоморфних зв’язних (7,10)-графів G існує циклічний (К21, G)-розклад і знайдено базову компоненту одного з таких розкладів;
розроблено новий спосіб побудови системи базових компонент циклічного (Кn, С5)-розкладу, на основі цього способу створені алгоритми і складено програми, що дозволило одержати списки циклічних (К11, С5)- та (К21, С5)-розкладів;
для розрізнення-ототожнення циклічних пентагональних розкладів введено узагальнений граф верхніх ребер GУВ та графи Inb(R) і Inс(R), які є графічними інваріантами;––
введено поняття кортежу довжин, базового набору довжин;
знайдено число неізоморфних пентагональних циклічних розкладів графа К11 та складено їх вичерпний список;
знайдено верхню оцінку числа неізоморфних циклічних пентагональних розкладів графа Кп;
доведено необхідну умову ізоморфності циклічних (Кп, С5)-розкладів;
знайдено нижню оцінку числа неізоморфних циклічних (К21, С5)-розкладів та відповідний список таких розкладів;
знайдено нижню оцінку числа неізоморфних (K19, G)-розкладів для випадків, коли G=П – трикутна призма та G=В – барвінок, і їх списки;
доведено ряд тверджень щодо автоморфізмів 1-факторизацій графа Qn;
доведено, що квадратна 1-факторизація графа Qn єдина з точністю до ізоморфізму, для кожного n;
доведено, що група автоморфізмів квадратної 1-факторизації графа Qn співпадає з групою автоморфізмів цього графа;
за допомогою розробленого дисертантом алгоритму, на основі якого складено програму, знайдено число неізоморфних 1-факторизацій графа Q5;
описано побудову стандартної реберної нумерації дерев і з її допомогою доведено антимагічність подвійних зірок та r-регулярних дерев;––
введено поняття вершинного яруса центрального дерева, повних ярусних (r0, r1, …, rk)-регулярних монотонно спадного та монотонно зростаючого дерев;
доведено, що кожне повне k-ярусне (r0, r1, …, rk)-регулярне монотонно спадне дерево антимагічне;
знайдено одну з антимагічних нумерацій простих ланцюгів Pn (n>2), простих циклів Cn (n?3), повних графів Kn (n>3), голландських m-вітряків, серій графів СnР3, B(Cn,2,n), що доводить антимагічність цих графів;
побудовано алгоритм перевірки графа на антимагічність.
Усі ці результати супроводжуються строгими доведеннями.
Теоретичне і практичне значення отриманих результатів. Результати дисертаційної роботи в основному мають теоретичний характер. Їх доцільно застосовувати в теорії комбінаторних конфігурацій, при читанні спецкурсів з теорії груп, графів, ґраток та скінченних топологій. Вони можуть бути використаними для подальших досліджень циклічних розкладів, 1-факторизацій та нумерацій графів.
Особистий внесок здобувача. Всі наукові результати одержані здобувачем особисто. Науковому керівнику – професору Кириченку В. В. належить постановка задач, з професором Кириченко В. В. та професором Кіровоградського національного технічного університету Петренюком А. Я. обговорювалися можливі шляхи їх розв’язання. У працях 6, 9 тези конференції і семінару), опублікованих у співавторстві, всі одержані наукові результати належать дисертанту.
Апробація результатів дисертації. Основні положення дисертаційної роботи доповідалися на П’ятій Міжнародній алгебраїчній конференції в Україні (м. Одеса, 20 – липня 2005 р.); Дев’ятій Міжнародній науково-практичній конференції "Наука та освіта – 2006" – в Україні
(м. Дніпропетровськ, 23 – січня 2006 р.); Одинадцятій Міжнародній науковій конференції імені академіка М. Кравчука (м. Київ, 18 – травня 2006 р.); Міжнародній конференції по радикалах ICOR-2006 (м. Київ, 30.07.2006 – .08. 2006 р.); Першому міжвузівському науково-практичному семінарі "Комбінаторні конфігурації та їх застосування" (м. Кіровоград, 19 – квітня 2006 р.); Алгебраїчному семінарі Київського національного університету імені Тараса Шевченка (м. Київ, 18 вересня 2006 р.); Другому міжвузівському науково-практичному семінарі "Комбінаторні конфігурації та їх застосування" (м. Кіровоград, 19 – жовтня 2006 р.); Шостій Міжнародній алгебраїчній конференції в Україні (м. Кам’янець-Подільський, 01.07.2007 – .07.2007 р.).
Публікації. Основні результати дисертації опубліковано в роботах [1–10], які наводяться в кінці автореферату, з них статті [1–3] – у фахових виданнях з переліку, який затверджено ВАК України, стаття [4] – у науковому журналі та тези [5–10] – у матеріалах міжнародних математичних конференцій та науково-практичних семінарів.
Структура і обсяг роботи. Дисертація складається із вступу, чотирьох розділів (містить 19 підрозділів), висновків, списку використаних джерел і додатків. Загальний обсяг роботи – 190 сторінок, з яких 8 займає список використаних джерел, що складається з 88 найменувань, та 70 сторінок додатків.
ОСНОВНИЙ ЗМІСТ
У вступі обґрунтовано актуальність теми дисертаційного дослідження, сформульовано його мету і задачі, показаний зв’язок роботи з планами наукових досліджень кафедри, охарактеризовано наукову новизну роботи, практичне значення отриманих результатів, особистий внесок дисертанта, апробацію результатів дисертації, вказані структура й обсяг дисертації. В дисертації виділяється чотири розділи.
РОЗДІЛ 1 «ОГЛЯД ЛІТЕРАТУРИ ТА ПОПЕРЕДНІ ТЕОРЕТИЧНІ ВІДОМОСТІ» носить допоміжний та систематизуючий характер. Введено необхідні теоретичні відомості з теорії графів, які в дисертації знайшли застосування в доведенні теорем, винаходах способів побудови розкладів, нумерацій графів та в створенні відповідних алгоритмів і комп’ютерних програм. Розділ складається з чотирьох підрозділів.
У підрозділі .1 «Огляд літератури» наведено огляд праць, присвячених теорії розкладів та нумераціям графів. У підрозділі 1.2 «Необхідні поняття теорії графів» подано основні означення та деякі твердження з теорії графів, зокрема стосовно розкладів та факторизацій.
(Н,)-розкладом графа Н на графи із сукупності Q=q1, q2, …, qk називається розбиття множини ребер графа Н на такі підмножини, що породжені ними підграфи (компоненти розкладу) попарно пореберно не перетинаються і кожний з них ізоморфний одному з елементів множини Q. Розкладом графа Кп на графи, ізоморфні графові G, називають розбиття множини ребер графа Кп на підмножини, кожна з яких породжує підграф (компоненту розкладу), ізоморфний G, і кожне ребро Кп належить одній і тільки одній компоненті розкладу. Такий розклад називатимемо
(Кп, G)-розкладом. (Кп, G)-розклад називають циклічним, якщо всі його компоненти одержуються з однієї базової (або кількох базових) дією на неї степенями деякої циклічної підстановки б вершин графа Кп. Вказана циклічна підстановка називається твірною розкладу, і її степені суть автоморфізми (Кп, G)-розкладу. Якщо всі компоненти розкладу графа Н є фактори, то такий розклад називають факторизацією графа Н.
У підрозділі 1.3 «Способи ототожнення та розрізнення» йде мова про ізоморфізм розкладів; описано один із специфікаційних інваріантів, який застосовано при розв’язуванні задач ототожнення-розрізнення в множині (Н, G)-розкладів в розділах 2 та 3 дисертації.
Граф Гij з множиною вершин V(Гij)=V(Рi)V(Рj)V(Н) і множиною ребер Е(Гij)=Е(Рі)Е(Рj)Е(Н) називають графом переплетень компонент Рі та Рj деякого (Н, G)-розкладу. Розглянемо список усіх можливих попарно неізоморфних графів переплетень цього розкладу, записаних у певному порядку. Позначимо потужність одержаного списку k. Складові цього списку називаються типами переплетення компонент розкладу.
Індексом компоненти Р деякого розкладу R називають вектор (s1, s2, sk), де sі – кількість таких компонент у розкладі, які утворюють тип переплетення і з компонентою Р. Очевидно, s1+s2+...+sk=t–1, де t – число компонент у розкладі.
Тоді таблиця
в якій mj означає число компонент у розкладі R, що мають індекс (s1(j), s2(j), sk(j)), являє собою специфікаційний інваріант у множині (Н, G)-розкладів відносно ізоморфності розкладів. Індекси у цій таблиці попарно різні і розташовані в порядку лексикографічного зростання.
Якщо всі пари компонент розкладу мають тип переплетення і, то такий розклад називають і-гомогенним, індекси всіх його компонент однакові і мають вид (0, , …, , si, , ). Для циклічного розкладу R всі його компоненти мають один й той самий індекс, а тому p=1 і Т(R) таблиця-рядок. У випадку, коли (Н, G)-розклад є 1-факторизацією, а Рі та Рj – деякі її 1-фактори, граф переплетень Гij є множиною циклів парної довжини, які попарно не перетинаються.
Крім специфікаційних, суттєву роль при розрізненні-ототожненні розкладів відіграють графічні інваріанти, множина значень яких є множина графів, а роль еквівалентності у множині значень відіграє ізоморфність.
У підрозділі 1.4 «Способи задання графів» наводяться найбільш важливі способи задання графів, серед яких суттєве значення мають такі способи машинного зображення графів, які б вирізнялися з-поміж інших малим об’ємом займаної пам’яті і значною швидкістю виконання операцій на графах. До таких способів відносяться: стандартне, матричне задання графа та шаблонне представлення графа.
У РОЗДІЛІ 2 «ЦИКЛІЧНІ РОЗКЛАДИ ПОВНИХ ГРАФІВ» викладено результати, що стосуються способів побудови циклічних розкладів повних графів та розрізнення одержаних розкладів за допомогою інваріантів. У підрозділі 2.1 «Побудова циклічних розкладів графа К21 на (7,10)-графи» доведено для кожного (7,10)-графа G існування циклічного (К21,G)-розкладу. Відповідно до способу реалізації циклічного методу створено алгоритм 2.1 – знаходження лексикографічно найменшої базової компоненти циклічного (К21, G)-розкладу. Виділимо основні етапи цього алгоритму: вибір початкового об’єкта; перевірка базовості одержаної компоненти; перетворення об’єкта в наступний; виведення результатів пошуку. Складено програму і побудовою здійснено доведення наступної теореми.
Теорема 2.1.1. Для кожного з 132 існуючих неізоморфних зв’язних (7,10)-графів G існує циклічний (К21, G)-розклад.
У підрозділі 2.2 «Циклічні пентагональні розклади графа Кn» введено поняття пентагонального розкладу графа Кn, кортежу довжин, базового набору довжин. Розроблено загальний спосіб побудови (n–1)/10 базових компонент циклічного (Кn, С5)-розкладу на основі взаємно однозначної відповідності між ребрами (i, j) вписаного циклу та числами lk, де lk=d(i, j)=min(|ij|, nij|). Встановлено умову реалізації набору чисел lk проекцією графа С5 у вигляді рівності .
Означення 2.2.1. Пентагональним розкладом графа Кn будемо називати кожний (Кп, С5)-розклад.
Означення 2.2.2. Впорядковану множину різних чисел , елементи якої задовольняють умову , назвемо кортежем довжин, що відповідає деякій (базовій) компоненті циклічного (Кп, С5)-розкладу.
Проекція графа С5 реалізується кортежем довжин 1, –2, , , ), який назвемо початковим. Здійснено побудову охоплюючого списку циклічних (К11, С5)-розкладів та застосовано до нього три прийоми вилучення дублікатів.
Для одержання всіх базових компонент циклічного (Кп, С5)-розкладу знаходимо всі розбиття множини L=1, , …,n1)/2 на (n1)/10 множин потужності п’ять
(±l1, ±l2, ±l3, ±l4, ±l5), …, (±l(n–1)/2–4, ±l(n1)/2–3, ±l(n1)/2–2, ±l(n1)/2–1, ±l(n1)/2), що попарно не перетинаються та задовольняють умовам:
1) lі?lj, для будь-яких i?j з множини {1, 2, …, (n1)/2};
2) знак «+» або «» перед lk обираємо так, щоб для кожного із вказаних кортежів довжин виконувалася рівність .
Означення 2.2.3. Кожну сукупність із (n1)/10 кортежів довжин, що задовольняють умовам 1), 2), назвемо базовим набором довжин циклічного (Кп, С5)-розкладу і позначимо через k кількість різних таких наборів. Інакше кажучи, k – це число всіх циклічних (Кn, С5)-розкладів, знайдених з точністю до перестановок чисел ±lk у кожному з кортежів довжин базового набору довжин.
Доведено наступну теорему.
Теорема 2.2.4. Число неізоморфних циклічних (Кn, С5)-розкладів не більше, ніж
У підрозділі 2.3 «Конструктивний перелік циклічних пентагональних розкладів графа К11» для розв’язання задачі переліку циклічних (К11, С5)-розкладів застосовуються специфікаційний і графічні інваріанти та розроблено алгоритм 2.2.
Алгоритм 2.2. Побудова списку базових наборів довжин циклічних (К11, С5)-розкладів та відповідних значень інваріанта Т(R)
Крок . Організуємо початковий кортеж довжин С.
Крок . Трансформуємо один об’єкт (масив С) в наступний перестановкою його елементів справа наліво. Якщо всі варіанти кортежів довжин С вичерпані, то переходимо до кроку 4.
Крок . Формуємо масив СС, як список різних кортежів довжин С. Для цього будуємо циклічні перестановки кортежу С. Перевіряємо на наявність у масиві СС кортежу С та його циклічних перестановок, порівнянням із вже побудованими. У разі відсутності заносимо лексикографічно найменший кортеж у СС. Переходимо до кроку .
Крок . За кожним кортежем С з масиву СС будуємо кортеж С2=(0bcde), де 0, b, c, d, e вершини відповідної компоненти розкладу: для j=2, , , маємо С2j(С2j–1+ ССi, j–1+11)mod ), де ССi, j–1 є (j–1)-им елементом і-го кортежу в СС.
Крок . Конструюємо орбіту С1 компоненти С2. Для j=2, , …, 11 знаходимо вершини кожної компоненти орбіти за формулою с1j, k(с1j–1,k+1) mod ), де k=1, , …, .
Крок . Порівнюємо базовий набір вершин з кожним набором вершин із орбіти даної компоненти. В залежності від числа спільних вершин та кількості трикутників в попарному об’єднанні відповідних 5-циклів, визначаємо тип переплетення.
Крок . Знаходимо специфікаційний інваріант Т(R) у відповідності до типів переплетень базової компоненти з іншими компонентами в розкладі R, використовуємо крок . Зберігаємо значення Т(R) у масиві рр.
Крок . Методом бульбашок лексикографічно впорядковуємо масив рр, ставлячи йому у відповідність значення із СС.
Крок . Виводимо число знайдених розкладів та списки: базові набори довжин і відповідні значення Т(R).
Крок . Вихід.
З допомогою складеної на основі алгоритму 2.2 програми знайдено всі проекції 5-циклу, які є базовими компонентами відповідних розкладів. Одержано список з 24 циклічних (К11, С5)-розкладів. До нього застосовано один з прийомів вилучення дублікатів, чим зменшено список удвічі.
Асоційований граф верхніх ребер і введений дисертантом узагальнений граф верхніх ребер дозволили вирізнити чотири неізоморфні циклічні (К11, С5)-розклади.
Теорема 2.3.2. З точністю до ізоморфізму, існують чотири циклічних (К11, С5)-розклади. Два з них 5-гомогенні.
Ось базові компоненти цих (К11, С5)-розкладів:
(0, 1, 4, 2, 7), (0, 1, 6, 9, 2), (0, 1, 4, 8, 2), (0, 1, 5, 8, 2).
Підрозділ 2.4 «Необхідна умова ізоморфності циклічних (Кn, С5)-розкладів» присвячено пошуку способів розрізнення-ототожнення циклічних розкладів, доведено теорему .4.1 і проілюстровано одержані результати на прикладі.
Під послідовним відображенням орбіти одного циклічного (Кn, С5)-розкладу R1 в орбіту іншого циклічного (Кn, С5)-розкладу R2 розуміємо наступне: якщо і-та компонента розкладу R1 відображується в j-ту компоненту розкладу R2, то і+1 відображується в (j+l)mod n, і+2 в (j+2l)mod n і т. д., де l – крок, з яким здійснюється відображення.
Теорема 2.4.1. При ізоморфізмі циклічних (Кn, С5)-розкладів зберігається послідовне відображення орбіти одного з них в орбіту іншого.
У підрозділі 2.5 «Циклічні пентагональні розклади графа К21» на основі одержаних у підрозділах 2.2 – 2.4 результатів, із застосуванням інваріантів, знайдено нижню оцінку числа неізоморфних циклічних (К21, С5)-розкладів.
Індексом компоненти Р циклічного (К21, С5)-розкладу R назвемо вектор (х0, х1, х2, х3, х4, х5), де хs – кількість таких циклів у розкладі, які з даною компонентою мають s спільних вершин, s=0, 1, 2, 3, 4, 5. Таблиця Rs=(х0, х1, х2, х3, х4, х5) є специфікаційним інваріантом у множині циклічних (К21, С5)-розкладів відносно ізоморфності розкладів.
Дисертантом розроблено алгоритм 2.3 побудови списку базових наборів довжин циклічних (К21, С5)-розкладів та відповідних значень специфікаційних інваріантів Rs і Т(R), за яким складено програму. В результаті роботи програми встановлено, що серед 63 циклічних (K21, С5)-розкладів 21 має різні значення інваріанта Rs. Далі скористались більш чутливим інваріантом Т(R), який в даному випадку приймає 48 різних значень. Введено графічні інваріанти – графи Inb(R), Inc(R) та знайдено ототожнюючу підстановку за результатами теореми 2.4.1. Це дозволило довести наступну теорему.
Теорема 2.5.2. З точністю до ізоморфізму існує не менше, ніж 62 циклічних (К21, С5)-розклади.
У підрозділі 2.6 «Неізоморфні циклічні розклади графа К19 на компоненти певних видів» розв’язуються задачі знаходження нижньої оцінки числа неізоморфних (К19, П)- та (К19, В)-розкладів, де П – призма порядку шість, В – барвінок порядку сім.
Алгоритм 2.4. Знаходження різних циклічних (K19, П)-розкладів
Крок . Заповнюємо масив m елементами m[i]=і, де i=1, , …, .
Крок . Будуємо шаблон mn графа П.
Крок . Будуємо кортеж довжин mg до відповідного шаблону. Для і=1, , …, покладаємо mg[i]=m[mn[2i–1]]–m[mn[2i]]. Якщо mg[i]<0, то покладаємо mg[i]=–mg[i], якщо ж mg[i]>9, тоді mg[i]=19–mg[i].
Крок . Якщо кортеж довжин mg містить однакові елементи, то методом перебору шукаємо масив m, елементи якого задовольняють умову mg[i]mg[j] для будь-яких i, j, що приймають значення від 1 до 9 і ij. Якщо такий масив т знайдено, то т – базова компонента циклічного (K19, П)-розкладу, інакше переходимо до кроку 8.
Крок . Будуємо орбіту компоненти т і шукаємо число спільних вершин компоненти т з іншими компонентами орбіти.
Крок . Знаходимо специфікаційний інваріант – масив Rs наступним чином: Rs =(х0, х1, х2, х3, х4, х5), де хs – кількість таких компонент у розкладі, які з компонентою т мають s спільних вершин, s=0, 1, 2, 3, 4, 5.
Крок . Виводимо одержані результати.
Крок . Вихід.
З проведеного дослідження одержано наступний результат.
Теорема 2.6.1. З точністю до ізоморфізму існують не менше, ніж 4 циклічних (K19, П)-розклади.
За результатами роботи програми, яка побудована за модифікацією алгоритму 2.4, знайдено 3548 різних циклічних барвінкових розкладів графа K19, на яких інваріант Rs приймає 11 різних значень.
Теорема 2.6.2. З точністю до ізоморфізму існують не менше, ніж 11 циклічних (K19, В)-розкладів.
РОЗДІЛ 3 «1-ФАКТОРИЗАЦІЇ БУЛЕВИХ КУБІВ» присвячено дослідженню 1-факторизацій булевого куба Qn. У підрозділі 3.1 «1-факторизації графів» сформульовано та доведено деякі допоміжні твердження, які сприяли створенню алгоритму конструктивного переліку
1-факторизацій графа Qn та доведенню єдиності квадратної 1-факторизації графа Qn.
Твердження 3.1.4. Якщо підстановка б є автоморфізмом 1-факторизації Ф графа Qn, то число нерухомих елементів в б парне.
Твердження 3.1.5. Якщо підстановка б є автоморфізмом 1-факторизації Ф графа Qn і б має більше ніж 2n1 нерухомих елементів, то число нерухомих елементів в б дорівнює 2n.
Твердження 3.1.6. Якщо підстановка б є автоморфізмом 1-факторизації Ф графа Qn і в б існує 2n1 нерухомих елементів, то решта 2n1 елементів також нерухомі в б.
У підрозділі 3.2 «Квадратна 1-факторизація графа Qn» досліджується певний клас g-гомогенних 1-факторизацій.
1-факторизація графа Qn називається g-гомогенною, якщо Т-таблиця складається з одного вектор-індексу і всі графи переплетень Гij ізоморфні графові g. g-Гомогенну
1-факторизацію називають квадратною, якщо всі зв’язні компоненти графа g є цикли довжини чотири. Камерон довів існування єдиної квадратної 1-факторизації графа К2n. Відомо, що n-вимірний куб Qn допускає квадратну 1-факторизацію при кожному n. Дисертантом доведено наступну теорему.
Теорема 3.2.1. Квадратна 1-факторизація графа Qn єдина з точністю до ізоморфізму для кожного n.
Підрозділ 3.3 «Про будову групи автоморфізмів графа Qn» присвячено техніці побудови елементів групи автоморфізмів графа Qn, яку використано при створенні програми знаходження неізоморфних
1-факторизацій графа Q5 і доведенні твердження 3.3.1.
Твердження 3.3.1. Група автоморфізмів квадратної 1-факторизації графа Qn збігається з групою автоморфізмів цього графа.
Підрозділ 3.4. «Кількісний перелік 1-факторизацій графа Q5» присвячено знаходженню числа неізоморфних 1-факторизацій графа Q5, для цього запропоновано наступний алгоритм.
Алгоритм 3.1. Алгоритм знаходження неізоморфних 1-факторизацій графа Qп
Крок . Присвоюємо кожному ребру графа Qп мітку з множини 1, , , …, n2n–1. Починаємо з ребер, інцидентних вершині з міткою 0, потім з міткою 1 і т. д., враховуючи лексикографічний порядок: якщо (i, j)=k, (i, s)=t, тоді k<t при j<s.
Крок . Формуємо початкову 1-факторизацію, що є квадратною, наступним чином. Якщо ребро (i, j) графа Qп таке, що ij=2k, то вміщуємо його в масив, який відповідає фактору Fk+1, де k=0, , …, n–1.
Крок . Знаходимо наступну, в лексикографічному порядку, 1-факторизацію. Зафіксуємо перше ребро кожного 1-фактора, одержимо список нерухомих ребер: (0, )=1, (0, )=2, (0, )=3, …, (0, n–1)=n. Інші ребра обмінюємо між 1-факторами за правилом: якщо ребро (i, j)Е(Fk), то ребра виду (i, s) та (j, v) не належать Е(Fk), де Fk – 1-фактор, Е(Fk) – його множина ребер.
Крок . Створюємо список, який формуємо з 1-факторизацій кроку 2 та кроку 5.
Крок . Діємо на знайдену 1-факторизацію всіма можливими підстановками з групи автоморфізмів графа Qп. Якщо одна з одержаних 1-факторизацій співпадає з досліджуваною, то її не враховуємо, інакше додаємо її до списку.
Крок . Виводимо результати – список і число неізоморфних1-факторизацій графа Qп.
Крок . Вихід.
За результатами переліку, одержаними при роботі програми, складеної дисертантом, робимо висновок, сформульований в теоремі.
Теорема 3.4.3. Існують з точністю до ізоморфізму, точно 5221-факторизації графа Q5, тобто nnf(Q5)=522.
РОЗДІЛ 4 «АНТИМАГІЧНІ НУМЕРАЦІЇ ГРАФІВ» присвячений одному з видів нумерацій графів, а саме антимагічним нумераціям. Розглядаються загальні методи побудови антимагічної нумерації для деяких класів дерев, а також для окремих видів спеціальних графів. У підрозділі 4.1 «Основні поняття про нумерації графів» наводяться основні факти про нумерації графів.
Функція f: E>{1, 2, …, q}, що задана на множині ребер графа G=(V, E), де |V|=n, |E|=q, називається реберною нумерацією графа G. Реберна нумерація f породжує функцію на множині вершин V, рівну для кожної вершини х сумі номерів ребер, інцидентних вершині х у графі G. Нумерація f називається антимагічною, якщо – бієкція. Граф G антимагічний, якщо він допускає антимагічну нумерацію.
У підрозділі 4.2 «Стандартна нумерація дерев» представлено побудову нумерації дерев, названу стандартною. Нехай T=(V, E) дерево. Позначимо V0 множину його кінцевих вершин, E0 множину кінцевих ребер дерева T. Побудуємо серію дерев T0, T1, …, Th–1, де T0=T,
Ti=Ti–1\Ei–1 (i=1, , …, h–1) до появи у серії першого безреберного дерева. Одержимо розбиття E=E0E1…Eh–1, де Еі множина кінцевих ребер дерева Ti, ei=Ei. Здійснимо нумерацію ребер дерева T наступним чином. Ребрам множини E0 в певному порядку (наприклад, справа наліво) ставимо у відповідність послідовно числа від 1 до e0; …; ребрам множини Еі числа від e0+e1+…+ei–1+1 до e0+e1+…+ei–1+ei (i=1, , …, h–1), причому в кожній множині Еі нумерацію починаємо з ребра, суміжного ребру з найменшим номером в Еі–1. Побудовану нумерацію назвемо стандартною, в багатьох випадках вона антимагічна.
Твердження 4.2.1. Для подвійної зірки порядку n (n?5) стандартна нумерація ребер є антимагічною.
Дерево T назвемо r-регулярним висоти h, якщо воно містить, крім кінцевих вершин, що знаходяться на відстані h від центра, тільки вершини степеня r, r>1.
Твердження 4.2.3. r-регулярні дерева висоти h антимагічні.
У підрозділі 4.3 «Повні ярусні (r0, r1, …, rk)-регулярні дерева» введено ряд означень та доведена антимагічність розглянутих дерев з використанням стандартної нумерації.
Означення 4.3.1. Вершинним ярусом h у центральному дереві назвемо множину вершин, що знаходяться на відстані h від центра. Центральна вершина дерева утворює нульовий ярус.
Означення 4.3.2. Повним ярусним (r0, r1, …, rk)-регулярним деревом назвемо k-ярусне дерево з центральною вершиною степеня r0 і з степенями всіх вершин і-го ярусу, рівними ri.
Означення 4.3.3. Повне ярусне (r0, r1, …, rk)-регулярне дерево будемо вважати монотонно спадним (незростаючим) від центра, якщо r0?r1?…?rk –1. Аналогічно, якщо r0?r1?…?rk –1, то дерево монотонно зростаюче (неспадне) від центра.
Твердження 4.3.4. Повне двоярусне регулярне монотонно спадне дерево антимагічне.
Твердження 4.3.5. Повне триярусне (r0, r1, r2, r3)-регулярне монотонно спадне дерево антимагічне.
Проводячи аналогічні міркування для повного k-ярусного (r0, r1, …, rk)-регулярного монотонно спадного дерева, одержали узагальнений результат.
Твердження 4.3.6. Будь-яке повне kярусне (r0, r1, …, rk)-регулярне монотонно спадне дерево антимагічне.
У підрозділ 4.4 «Антимагічність деяких видів графів» побудовано певні антимагічні нумерації простих ланцюгів Pn (n>2), простих циклів Cn (n?3), повних графів Kn (n>3), а також доведено наступні твердження:
Твердження 4.4.5. Довільний голландський m-вітряк – антимагічний граф.
Твердження 4.4.7. Граф СnР3 антимагічний для всіх натуральних n.
Твердження 4.4.8. Для непарних натуральних n граф B(Cn, P2, Cn) антимагічний.
У підрозділі 4.5 «Встановлення антимагічності скінченного графа» наведено розроблений дисертантом алгоритм перевірки графа на антимагічність.
ВИСНОВКИ
В дисертаційній роботі отримано низку результатів про побудову, перелік циклічних (Кп, 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 (n?5), r-регулярних дерев та повних k-ярусних (r0, r1, …rk)-регулярних монотонно спадних дерев при k 2. Знайдено одну з антимагічних нумерацій простого ланцюга, простого цикла, повного графа, голландського вітряка, графів СnР3 і B(Cn, P2, Cn). Складено алгоритм перевірки графа на антимагічність. Отримані результати, що стосуються нумерацій графів, можна охарактеризувати, як загальний підхід до знаходження антимагічних нумерацій певних спеціальних графів та дослідження часткових випадків при застосуванні програми, яка реалізує побудований алгоритм.
СПИСОК ОПУБЛІКОВАНИХ АВТОРОМ ПРАЦЬ
ЗА ТЕМОЮ ДИСЕРТАЦІЇ
Семенюта М. Ф. Антимагічна нумерація графівВісник Київського національного університету ім. Т. Шевченка. Серія: фізико-математичні науки. – 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. С. –71.
Семенюта М. Ф. Циклічні розклади К21 на (7,10)-графи // Одинадцята міжнародна наукова конференція імені академіка М. Кравчука, Київ: Матеріали конф. – К.: ТОВ «Задруга», 2006. – С. 588.
Semenyuta M. Cyclic pentagonal decompositions of К11 // Тези доповідей Міжнародної конференції по радикалах ICOR-2006. – Київ.: Київський нац. університет ім. Т. Шевченка, 2006. – С. 60–61.
Семенюта М. Ф., Сорока О. О. Побудова циклічних пентагональних розкладів повних графів// Матеріали першого міжвузівського науково-практичного семінару “Комбінаторні конфігурації та їх застосування”. – м. Кіровоград: Видавництво ДЛАУ, 2006 р. – С. 43–44.
Semenyuta M. F. On cyclic decompositions of graphs // Тези доповідей VI-ої Міжнародної алгебраїчної конференції в Україні. – Кам’янець-Подільський: Кам’я нець-Подільський держ. університет, 2007. – С. –183.
АНОТАЦІЇ
Семенюта М. Ф. Дослідження розкладів та нумерацій графів. – Рукопис.
Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 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), побудовано алгоритм перевірки графа на антимагічність.
Ключові слова: граф, циклічний розклад, пентагональний розклад, n-вимірний (булів) куб Qn, 1-факторизація, квадратна 1-факторизація, специфікаційні інваріанти, графічні інваріанти, антимагічна нумерація,
дерево.
Семенюта М. Ф. Исследование разложений и нумераций графов. –Рукопись.
Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.01.08 – математическая логика, теория алгоритмов и дискретная математика. – Киевский национальный университет имени Тараса Шевченко, Киев, 2008.
Первые исследования,
