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

Размещено на http://www.allbest.ru/

Київський національний університет

імені Тараса Шевченка

УДК 519.17

ДОСЛІДЖЕННЯ РОЗКЛАДІВ ТА НУМЕРАЦІЙ ГРАФІВ

01.01.08 - математична логіка, теорія алгоритмів

і дискретна математика

АВТОРЕФЕРАТ

дисертації на здобуття наукового ступеня

кандидата фізико-математичних наук

Семенюта Марина Фролівна

Київ - 2008

Дисертацією є рукопис.

Робота виконана на кафедрі геометрії Київського національного університету імені Тараса Шевченка, Кабінет Міністрів України.

Науковий керівник: доктор фізико-математичних наук, професор КИРИЧЕНКО Володимир Васильович, Київський національний університет імені Тараса Шевченка, м. Київ, професор кафедри геометрії.

Офіційні опоненти: доктор фізико-математичних наук, професор Кривий Сергій Лук'янович, Інститут кібернетики імені В. М. Глушкова НАН України, м. Київ, провідний науковий співробітник відділу мікропроцесорної техніки;

кандидат фізико-математичних наук, доцент ГАНЮШКІН Олександр Григорович, Київський національний університет імені Тараса Шевченка, м. Київ, доцент кафедри алгебри та математичної логіки.

Захист відбудеться 26 травня 2008 року о 14 годині на засіданні спеціалізованої вченої ради Д 26.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-вимірного куба Q_n - ним знайдено відповідні списки при 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 році. Вони припустили, що для звичайного скінченного зв'язного графа, відмінного від К₂, існує антимагічна реберна нумерація. Також ними висловлено гіпотезу, що довільне дерево порядку n (n>2) антимагічне, в 2002 році цю гіпотезу довели для повних m-арних дерев П. Чават та В. Крішна.

Актуальність теми. В дисертаційній роботі продовжуються дослідження (Q, G)-розкладів, пов'язані з частковими постановками задач, що виникають в залежності від конкретики Q і G: знаходження умов існування (Q, G)-розкладів; знаходження базових компонент та побудова циклічних (Q, G)-розкладів; обчислення числа не ізоморфних (Q, G)-розкладів; проведення конструктивного переліку неізоморфних (Q, G)-розкладів. В дисертації викладено одержані дисертантом результати про циклічні розклади графа К₂₁ на (7,10)-графи, графа К₁₉ на призми і барвінки, про циклічні пентагональні розклади графа К_n, зокрема графів К₁₁ і К₂₁, про 1-факторизації n-вимірного куба Q_n та антимагічність деяких класів графів. Ці дослідження органічно вплітаються до описаного раніше розвитку розглядуваного напряму теорії графів.

Зв'язок роботи з науковими програмами, планами, темами. Тема дисертаційної роботи пов'язана з тематикою наукових досліджень кафедри геометрії механіко-математичного факультету Київського національного університету імені Тараса Шевченка. Результати дисертації частково використані при виконанні завдань підрозділу «Геометричні структури та їх застосування» держбюджетної теми 01БФ038-03 (номер державної реєстрації 0101U002479).

Мета і задачі дослідження. Об'єктом дослідження у даній дисертації виступають розклади та нумерації графів. Предметом дослідження є розклади графів на ізоморфні підграфи та реберна антимагічність графів.

Метою дисертаційної роботи є

побудова, перелік циклічних розкладів повних графів на ізоморфні підграфи певних видів і 1-факторизацій n-вимірного куба Q_n;

реберна антимагічність графів.

Задачі дослідження:

 розв'язання задачі існування циклічного (К₂₁, G)-розкладу для кожного із 132 існуючих неізоморфних зв'язних (7,10)-графів G;

 розв'язання задачі переліку циклічних пентагональних розкладів графа К_n для n?1(mod10);

 розв'язання задачі знаходження нижньої оцінки числа неізоморфних циклічних (K₁₉, G)-розкладів для випадків, коли G=П - трикутна призма та G=В - барвінок;

 проведення конструктивного переліку неізоморфних 1-факторизацій графа Q₅, з використанням його групи автоморфізмів;

 знаходження числа 1-факторизацій графа Q₅ з точністю до ізоморфізму;

 дослідження g-гомогенних 1-факторизацій графа Q_n;

 знаходження антимагічних нумерацій для деяких класів дерев та інших видів графів.

Методи дослідження. В кожному розділі дисертації знайшли застосування методи теорії графів. При побудові циклічних розкладів графів та 1-факторизацій графа Q₅ використовувались методи загальної теорії груп, зокрема груп підстановок. При побудові і конструктивному переліку неізоморфних розкладів графів велику роль відіграли методи генерації комбінаторних об'єктів.

Наукова новизна одержаних результатів. Вперше отримано такі результати:

 за допомогою складеної дисертантом програми встановлено, що для кожного з 132 існуючих неізоморфних зв'язних (7,10)-графів G існує циклічний (К₂₁, G)-розклад і знайдено базову компоненту одного з таких розкладів;

 розроблено новий спосіб побудови системи базових компонент циклічного (К_n, С₅)-розкладу, на основі цього способу створені алгоритми і складено програми, що дозволило одержати списки циклічних (К₁₁, С₅)- та (К₂₁, С₅)-розкладів;

 для розрізнення-ототожнення циклічних пентагональних розкладів введено узагальнений граф верхніх ребер G_УВ та графи Inb(R) і Inс(R), які є графічними інваріантами;

-- введено поняття кортежу довжин, базового набору довжин;

 знайдено число неізоморфних пентагональних циклічних розкладів графа К₁₁ та складено їх вичерпний список;

 знайдено верхню оцінку числа неізоморфних циклічних пентагональних розкладів графа К_п;

 доведено необхідну умову ізоморфності циклічних (К_п, С₅)-розкладів;

 знайдено нижню оцінку числа неізоморфних циклічних (К₂₁, С₅)-розкладів та відповідний список таких розкладів;

 знайдено нижню оцінку числа неізоморфних (K₁₉, G)-розкладів для випадків, коли G=П - трикутна призма та G=В - барвінок, і їх списки;

 доведено ряд тверджень щодо автоморфізмів 1-факторизацій графа Q_n;

 доведено, що квадратна 1-факторизація графа Q_n єдина з точністю до ізоморфізму, для кожного n;

 доведено, що група автоморфізмів квадратної 1-факторизації графа Q_n співпадає з групою автоморфізмів цього графа;

 за допомогою розробленого дисертантом алгоритму, на основі якого складено програму, знайдено число неізоморфних 1-факторизацій графа Q₅;

 описано побудову стандартної реберної нумерації дерев і з її допомогою доведено антимагічність подвійних зірок та r-регулярних дерев;

-- введено поняття вершинного яруса центрального дерева, повних ярусних (r₀, r₁, …, r_k)-регулярних монотонно спадного та монотонно зростаючого дерев;

 доведено, що кожне повне k-ярусне (r₀, r₁, …, r_k)-регулярне монотонно спадне дерево антимагічне;

 знайдено одну з антимагічних нумерацій простих ланцюгів P_n (n>2), простих циклів C_n (n?3), повних графів K_n (n>3), голландських m-вітряків, серій графів С_nР₃, B(C_n, P₂, C_n), що доводить антимагічність цих графів;

 побудовано алгоритм перевірки графа на антимагічність.

Усі ці результати супроводжуються строгими доведеннями.

Теоретичне і практичне значення отриманих результатів. Результати дисертаційної роботи в основному мають теоретичний характер. Їх доцільно застосовувати в теорії комбінаторних конфігурацій, при читанні спецкурсів з теорії груп, графів, ґраток та скінченних топологій. Вони можуть бути використаними для подальших досліджень циклічних розкладів, 1-факторизацій та нумерацій графів.

Особистий внесок здобувача. Всі наукові результати одержані здобувачем особисто. Науковому керівнику - професору Кириченку В. В. належить постановка задач, з професором Кириченко В. В. та професором Кіровоградського національного технічного університету Петренюком А. Я. обговорювалися можливі шляхи їх розв'язання. У працях 6, 9 тези конференції і семінару), опублікованих у співавторстві, всі одержані наукові результати належать дисертанту.

Апробація результатів дисертації. Основні положення дисертаційної роботи доповідалися на П'ятій Міжнародній алгебраїчній конференції в Україні (м. Одеса, 20 - 27 липня 2005 р.); Дев'ятій Міжнародній науково-практичній конференції "Наука та освіта - 2006" - в Україні (м. Дніпропетровськ, 23 - 31 січня 2006 р.); Одинадцятій Міжнародній науковій конференції імені академіка М. Кравчука (м. Київ, 18 - 20 травня 2006 р.); Міжнародній конференції по радикалах ICOR-2006 (м. Київ, 30.07.2006 - 5.08. 2006 р.); Першому міжвузівському науково-практичному семінарі "Комбінаторні конфігурації та їх застосування" (м. Кіровоград, 19 - 20 квітня 2006 р.); Алгебраїчному семінарі Київського національного університету імені Тараса Шевченка (м. Київ, 18 вересня 2006 р.); Другому міжвузівському науково-практичному семінарі "Комбінаторні конфігурації та їх застосування" (м. Кіровоград, 19 - 20 жовтня 2006 р.); Шостій Міжнародній алгебраїчній конференції в Україні (м. Кам'янець-Подільський, 01.07.2007 - 07.07.2007 р.).

Публікації. Основні результати дисертації опубліковано в роботах [1-10], які наводяться в кінці автореферату, з них статті [1-3] - у фахових виданнях з переліку, який затверджено ВАК України, стаття [4] - у науковому журналі та тези [5-10] - у матеріалах міжнародних математичних конференцій та науково-практичних семінарів.

Структура і обсяг роботи. Дисертація складається із вступу, чотирьох розділів (містить 19 підрозділів), висновків, списку використаних джерел і додатків. Загальний обсяг роботи - 190 сторінок, з яких 8 займає список використаних джерел, що складається з 88 найменувань, та 70 сторінок додатків.

ОСНОВНИЙ ЗМІСТ

У вступі обґрунтовано актуальність теми дисертаційного дослідження, сформульовано його мету і задачі, показаний зв'язок роботи з планами наукових досліджень кафедри, охарактеризовано наукову новизну роботи, практичне значення отриманих результатів, особистий внесок дисертанта, апробацію результатів дисертації, вказані структура й обсяг дисертації. В дисертації виділяється чотири розділи.

РОЗДІЛ 1 «ОГЛЯД ЛІТЕРАТУРИ ТА ПОПЕРЕДНІ ТЕОРЕТИЧНІ ВІДОМОСТІ» носить допоміжний та систематизуючий характер. Введено необхідні теоретичні відомості з теорії графів, які в дисертації знайшли застосування в доведенні теорем, винаходах способів побудови розкладів, нумерацій графів та в створенні відповідних алгоритмів і комп'ютерних програм. Розділ 1 складається з чотирьох підрозділів.

У підрозділі 1.1 «Огляд літератури» наведено огляд праць, присвячених теорії розкладів та нумераціям графів. У підрозділі 1.2 «Необхідні поняття теорії графів» подано основні означення та деякі твердження з теорії графів, зокрема стосовно розкладів та факторизацій.

(Н, Q)-розкладом графа Н на графи із сукупності Q=q₁, q₂, …, q_k називається розбиття множини ребер графа Н на такі підмножини, що породжені ними підграфи (компоненти розкладу) попарно пореберно не перетинаються і кожний з них ізоморфний одному з елементів множини 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 називають вектор (s₁, s₂, ..., s_k), де s_і - кількість таких компонент у розкладі, які утворюють тип переплетення і з компонентою Р. Очевидно, s₁+s₂+...+s_k=t-1, де t - число компонент у розкладі.

Тоді таблиця

в якій m_j означає число компонент у розкладі R, що мають індекс (s₁(j), s₂(j), ..., s_k(j)), являє собою специфікаційний інваріант у множині (Н, G)-розкладів відносно ізоморфності розкладів. Індекси у цій таблиці попарно різні і розташовані в порядку лексикографічного зростання.

Якщо всі пари компонент розкладу мають тип переплетення і, то такий розклад називають і-гомогенним, індекси всіх його компонент однакові і мають вид (0, 0, …, 0, s_i, 0, ..., 0). Для циклічного розкладу R всі його компоненти мають один й той самий індекс, а тому p=1 і Т(R) таблиця-рядок. У випадку, коли (Н, G)-розклад є 1-факторизацією, а Р_і та Р_j - деякі її 1-фактори, граф переплетень Г_ij є множиною циклів парної довжини, які попарно не перетинаються.

Крім специфікаційних, суттєву роль при розрізненні-ототожненні розкладів відіграють графічні інваріанти, множина значень яких є множина графів, а роль еквівалентності у множині значень відіграє ізоморфність.

У підрозділі 1.4 «Способи задання графів» наводяться найбільш важливі способи задання графів, серед яких суттєве значення мають такі способи машинного зображення графів, які б вирізнялися з-поміж інших малим об'ємом займаної пам'яті і значною швидкістю виконання операцій на графах. До таких способів відносяться: стандартне, матричне задання графа та шаблонне представлення графа.

У РОЗДІЛІ 2 «ЦИКЛІЧНІ РОЗКЛАДИ ПОВНИХ ГРАФІВ» викладено результати, що стосуються способів побудови циклічних розкладів повних графів та розрізнення одержаних розкладів за допомогою інваріантів. У підрозділі 2.1 «Побудова циклічних розкладів графа К₂₁ на (7,10)-графи» доведено для кожного (7,10)-графа G існування циклічного (К₂₁,G)-розкладу. Відповідно до способу реалізації циклічного методу створено алгоритм 2.1 - знаходження лексикографічно найменшої базової компоненти циклічного (К₂₁, G)-розкладу. Виділимо основні етапи цього алгоритму: вибір початкового об'єкта; перевірка базовості одержаної компоненти; перетворення об'єкта в наступний; виведення результатів пошуку. Складено програму і побудовою здійснено доведення наступної теореми.

Теорема 2.1.1. Для кожного з 132 існуючих неізоморфних зв'язних (7,10)-графів G існує циклічний (К₂₁, G)-розклад.

У підрозділі 2.2 «Циклічні пентагональні розклади графа К_n» введено поняття пентагонального розкладу графа К_n, кортежу довжин, базового набору довжин. Розроблено загальний спосіб побудови (n-1)/10 базових компонент циклічного (К_n, С₅)-розкладу на основі взаємно однозначної відповідності між ребрами (i, j) вписаного циклу та числами l_k, де l_k=d(i, j)=min(|ij|, nij|). Встановлено умову реалізації набору чисел l_k проекцією графа С₅ у вигляді рівності .

Означення 2.2.1. Пентагональним розкладом графа К_n будемо називати кожний (К_п, С₅)-розклад.

Означення 2.2.2. Впорядковану множину різних чисел , елементи якої задовольняють умову , назвемо кортежем довжин, що відповідає деякій (базовій) компоненті циклічного (К_п, С₅)-розкладу.

Проекція графа С₅ реалізується кортежем довжин 1, -2, 3, 4, 5), який назвемо початковим. Здійснено побудову охоплюючого списку циклічних (К₁₁, С₅)-розкладів та застосовано до нього три прийоми вилучення дублікатів.

Для одержання всіх базових компонент циклічного (К_п, С₅)-розкладу знаходимо всі розбиття множини L=1, 2, …, (n1)/2 на (n1)/10 множин потужності п'ять

(±l₁, ±l₂, ±l₃, ±l₄, ±l₅), …, (±l_(n-_1)/2-4, ±l_(n1)/2-3, ±l_(n1)/2-2, ±l_(n1)/2-1, ±l_(n1)/2), що попарно не перетинаються та задовольняють умовам:

1) l_і?l_j, для будь-яких i?j з множини {1, 2, …, (n1)/2};

2) знак «+» або «» перед l_k обираємо так, щоб для кожного із вказаних кортежів довжин виконувалася рівність .

Означення 2.2.3. Кожну сукупність із (n1)/10 кортежів довжин, що задовольняють умовам 1), 2), назвемо базовим набором довжин циклічного (К_п, С₅)-розкладу і позначимо через k кількість різних таких наборів. Інакше кажучи, k - це число всіх циклічних (К_n, С₅)-розкладів, знайдених з точністю до перестановок чисел ±l_k у кожному з кортежів довжин базового набору довжин.

Доведено наступну теорему.

Теорема 2.2.4. Число неізоморфних циклічних (К_n, С₅)-розкладів не більше, ніж

У підрозділі 2.3 «Конструктивний перелік циклічних пентагональних розкладів графа К₁₁» для розв'язання задачі переліку циклічних (К₁₁, С₅)-розкладів застосовуються специфікаційний і графічні інваріанти та розроблено алгоритм 2.2.

Алгоритм 2.2. Побудова списку базових наборів довжин циклічних (К₁₁, С₅)-розкладів та відповідних значень інваріанта Т(R)

Крок 1. Організуємо початковий кортеж довжин С.

Крок 2. Трансформуємо один об'єкт (масив С) в наступний перестановкою його елементів справа наліво. Якщо всі варіанти кортежів довжин С вичерпані, то переходимо до кроку 4.

Крок 3. Формуємо масив СС, як список різних кортежів довжин С. Для цього будуємо циклічні перестановки кортежу С. Перевіряємо на наявність у масиві СС кортежу С та його циклічних перестановок, порівнянням із вже побудованими. У разі відсутності заносимо лексикографічно найменший кортеж у СС. Переходимо до кроку 2.

Крок 4. За кожним кортежем С з масиву СС будуємо кортеж С2=(0bcde), де 0, b, c, d, e вершини відповідної компоненти розкладу: для j=2, 3, 4, 5 маємо С2_j(С2_j-₁+ СС_i, j-₁+11)mod 11), де СС_i, j-₁ є (j-1)-им елементом і-го кортежу в СС.

Крок 5. Конструюємо орбіту С1 компоненти С2. Для j=2, 3, …, 11 знаходимо вершини кожної компоненти орбіти за формулою с1_j, k(с1_j-_1,k+1) mod 11), де k=1, 2, …, 5.

Крок 6. Порівнюємо базовий набір вершин з кожним набором вершин із орбіти даної компоненти. В залежності від числа спільних вершин та кількості трикутників в попарному об'єднанні відповідних 5-циклів, визначаємо тип переплетення.

Крок 7. Знаходимо специфікаційний інваріант Т(R) у відповідності до типів переплетень базової компоненти з іншими компонентами в розкладі R, використовуємо крок 6. Зберігаємо значення Т(R) у масиві рр.

Крок 8. Методом бульбашок лексикографічно впорядковуємо масив рр, ставлячи йому у відповідність значення із СС.

Крок 9. Виводимо число знайдених розкладів та списки: базові набори довжин і відповідні значення Т(R).

Крок 10. Вихід.

З допомогою складеної на основі алгоритму 2.2 програми знайдено всі проекції 5-циклу, які є базовими компонентами відповідних розкладів. Одержано список з 24 циклічних (К₁₁, С₅)-розкладів. До нього застосовано один з прийомів вилучення дублікатів, чим зменшено список удвічі.

Асоційований граф верхніх ребер і введений дисертантом узагальнений граф верхніх ребер дозволили вирізнити чотири неізоморфні циклічні (К₁₁, С₅)-розклади.

Теорема 2.3.2. З точністю до ізоморфізму, існують чотири циклічних (К₁₁, С₅)-розклади. Два з них 5-гомогенні.

Ось базові компоненти цих (К₁₁, С₅)-розкладів:

(0, 1, 4, 2, 7), (0, 1, 6, 9, 2), (0, 1, 4, 8, 2), (0, 1, 5, 8, 2).

Підрозділ 2.4 «Необхідна умова ізоморфності циклічних (К_n, С₅)-розкладів» присвячено пошуку способів розрізнення-ототожнення циклічних розкладів, доведено теорему 2.4.1 і проілюстровано одержані результати на прикладі.

Під послідовним відображенням орбіти одного циклічного (К_n, С₅)-розкладу R₁ в орбіту іншого циклічного (К_n, С₅)-розкладу R₂ розуміємо наступне: якщо і-та компонента розкладу R₁ відображується в j-ту компоненту розкладу R₂, то і+1 відображується в (j+l)mod n, і+2 в (j+2l)mod n і т. д., де l - крок, з яким здійснюється відображення.

Теорема 2.4.1. При ізоморфізмі циклічних (К_n, С₅)-розкладів зберігається послідовне відображення орбіти одного з них в орбіту іншого.

У підрозділі 2.5 «Циклічні пентагональні розклади графа К₂₁» на основі одержаних у підрозділах 2.2 - 2.4 результатів, із застосуванням інваріантів, знайдено нижню оцінку числа неізоморфних циклічних (К₂₁, С₅)-розкладів.

Індексом компоненти Р циклічного (К₂₁, С₅)-розкладу R назвемо вектор (х₀, х₁, х₂, х₃, х₄, х₅), де х_s - кількість таких циклів у розкладі, які з даною компонентою мають s спільних вершин, s=0, 1, 2, 3, 4, 5. Таблиця Rs=(х₀, х₁, х₂, х₃, х₄, х₅) є специфікаційним інваріантом у множині циклічних (К₂₁, С₅)-розкладів відносно ізоморфності розкладів.

Дисертантом розроблено алгоритм 2.3 побудови списку базових наборів довжин циклічних (К₂₁, С₅)-розкладів та відповідних значень специфікаційних інваріантів Rs і Т(R), за яким складено програму. В результаті роботи програми встановлено, що серед 63 циклічних (K₂₁, С₅)-розкладів 21 має різні значення інваріанта Rs. Далі скористались більш чутливим інваріантом Т(R), який в даному випадку приймає 48 різних значень. Введено графічні інваріанти - графи Inb(R), Inc(R) та знайдено ототожнюючу підстановку за результатами теореми 2.4.1. Це дозволило довести наступну теорему.

Теорема 2.5.2. З точністю до ізоморфізму існує не менше, ніж 62 циклічних (К₂₁, С₅)-розклади.

У підрозділі 2.6 «Неізоморфні циклічні розклади графа К₁₉ на компоненти певних видів» розв'язуються задачі знаходження нижньої оцінки числа неізоморфних (К₁₉, П)- та (К₁₉, В)-розкладів, де П - призма порядку шість, В - барвінок порядку сім.

Алгоритм 2.4. Знаходження різних циклічних (K₁₉, П)-розкладів

Крок 1. Заповнюємо масив m елементами m[i]=і, де i=1, 2, …, 6.

Крок 2. Будуємо шаблон mn графа П.

Крок 3. Будуємо кортеж довжин mg до відповідного шаблону. Для і=1, 2, …, 9 покладаємо mg[i]=m[mn[2i-1]]-m[mn[2i]]. Якщо mg[i]<0, то покладаємо mg[i]=-mg[i], якщо ж mg[i]>9, тоді mg[i]=19-mg[i].

Крок 4. Якщо кортеж довжин mg містить однакові елементи, то методом перебору шукаємо масив m, елементи якого задовольняють умову mg[i]mg[j] для будь-яких i, j, що приймають значення від 1 до 9 і ij. Якщо такий масив т знайдено, то т - базова компонента циклічного (K₁₉, П)-розкладу, інакше переходимо до кроку 8.

Крок 5. Будуємо орбіту компоненти т і шукаємо число спільних вершин компоненти т з іншими компонентами орбіти.

Крок 6. Знаходимо специфікаційний інваріант - масив Rs наступним чином: Rs =(х₀, х₁, х₂, х₃, х₄, х₅), де х_s - кількість таких компонент у розкладі, які з компонентою т мають s спільних вершин, s=0, 1, 2, 3, 4, 5.

Крок 7. Виводимо одержані результати.

Крок 8. Вихід.

З проведеного дослідження одержано наступний результат.

Теорема 2.6.1. З точністю до ізоморфізму існують не менше, ніж 4 циклічних (K₁₉, П)-розклади.

За результатами роботи програми, яка побудована за модифікацією алгоритму 2.4, знайдено 3548 різних циклічних барвінкових розкладів графа K₁₉, на яких інваріант Rs приймає 11 різних значень.

Теорема 2.6.2. З точністю до ізоморфізму існують не менше, ніж 11 циклічних (K₁₉, В)-розкладів.

РОЗДІЛ 3 «1-ФАКТОРИЗАЦІЇ БУЛЕВИХ КУБІВ» присвячено дослідженню 1-факторизацій булевого куба Q_n. У підрозділі 3.1 «1-факторизації графів» сформульовано та доведено деякі допоміжні твердження, які сприяли створенню алгоритму конструктивного переліку 1-факторизацій графа Q_n та доведенню єдиності квадратної 1-факторизації графа Q_n.

Твердження 3.1.4. Якщо підстановка б є автоморфізмом 1-факторизації Ф графа Q_n, то число нерухомих елементів в б парне.

Твердження 3.1.5. Якщо підстановка б є автоморфізмом 1-факторизації Ф графа Q_n і б має більше ніж 2ⁿ¹ нерухомих елементів, то число нерухомих елементів в б дорівнює 2ⁿ.

Твердження 3.1.6. Якщо підстановка б є автоморфізмом 1-факторизації Ф графа Q_n і в б існує 2ⁿ¹ нерухомих елементів, то решта 2ⁿ¹ елементів також нерухомі в б.

У підрозділі 3.2 «Квадратна 1-факторизація графа Q_n» досліджується певний клас g-гомогенних 1-факторизацій.

1-факторизація графа Q_n називається g-гомогенною, якщо Т-таблиця складається з одного вектор-індексу і всі графи переплетень Г_ij ізоморфні графові g. g-Гомогенну 1-факторизацію називають квадратною, якщо всі зв'язні компоненти графа g є цикли довжини чотири. Камерон довів існування єдиної квадратної 1-факторизації графа К_2n. Відомо, що n-вимірний куб Q_n допускає квадратну 1-факторизацію при кожному n. Дисертантом доведено наступну теорему.

Теорема 3.2.1. Квадратна 1-факторизація графа Q_n єдина з точністю до ізоморфізму для кожного n.

Підрозділ 3.3 «Про будову групи автоморфізмів графа Q_n» присвячено техніці побудови елементів групи автоморфізмів графа Q_n, яку використано при створенні програми знаходження неізоморфних 1-факторизацій графа Q₅ і доведенні твердження 3.3.1.

Твердження 3.3.1. Група автоморфізмів квадратної 1-факторизації графа Q_n збігається з групою автоморфізмів цього графа.

Підрозділ 3.4. «Кількісний перелік 1-факторизацій графа Q₅» присвячено знаходженню числа неізоморфних 1-факторизацій графа Q₅, для цього запропоновано наступний алгоритм.

Алгоритм 3.1. Алгоритм знаходження неізоморфних 1-факторизацій графа Q_п

Крок 1. Присвоюємо кожному ребру графа Q_п мітку з множини 1, 2, 3, …, n2ⁿ-¹. Починаємо з ребер, інцидентних вершині з міткою 0, потім з міткою 1 і т. д., враховуючи лексикографічний порядок: якщо (i, j)=k, (i, s)=t, тоді k<t при j<s.

Крок 2. Формуємо початкову 1-факторизацію, що є квадратною, наступним чином. Якщо ребро (i, j) графа Q_п таке, що ij=2^k, то вміщуємо його в масив, який відповідає фактору F_k+1, де k=0, 1, …, n-1.

Крок 3. Знаходимо наступну, в лексикографічному порядку, 1-факторизацію. Зафіксуємо перше ребро кожного 1-фактора, одержимо список нерухомих ребер: (0, 1)=1, (0, 2)=2, (0, 4)=3, …, (0, 2ⁿ-¹)=n. Інші ребра обмінюємо між 1-факторами за правилом: якщо ребро (i, j)Е(F_k), то ребра виду (i, s) та (j, v) не належать Е(F_k), де F_k - 1-фактор, Е(F_k) - його множина ребер.

Крок 4. Створюємо список, який формуємо з 1-факторизацій кроку 2 та кроку 5.

Крок 5. Діємо на знайдену 1-факторизацію всіма можливими підстановками з групи автоморфізмів графа Q_п. Якщо одна з одержаних 1-факторизацій співпадає з досліджуваною, то її не враховуємо, інакше додаємо її до списку.

Крок 6. Виводимо результати - список і число неізоморфних1-факторизацій графа Q_п.

Крок 7. Вихід.

За результатами переліку, одержаними при роботі програми, складеної дисертантом, робимо висновок, сформульований в теоремі.

Теорема 3.4.3. Існують з точністю до ізоморфізму, точно 5221-факторизації графа Q₅, тобто nnf(Q₅)=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) дерево. Позначимо V₀ множину його кінцевих вершин, E₀ множину кінцевих ребер дерева T. Побудуємо серію дерев T₀, T₁, …, T_h-₁, де T₀=T,T_i=T_i-₁\E_i-₁ (i=1, 2, …, h-1) до появи у серії першого безреберного дерева. Одержимо розбиття E=E₀E₁…E_h-₁, де Е_і множина кінцевих ребер дерева T_i, e_i=E_i. Здійснимо нумерацію ребер дерева T наступним чином. Ребрам множини E₀ в певному порядку (наприклад, справа наліво) ставимо у відповідність послідовно числа від 1 до e₀; …; ребрам множини Е_і числа від e₀+e₁+…+e_i-₁+1 до e₀+e₁+…+e_i-₁+e_i (i=1, 2, …, h-1), причому в кожній множині Е_і нумерацію починаємо з ребра, суміжного ребру з найменшим номером в Е_і-₁. Побудовану нумерацію назвемо стандартною, в багатьох випадках вона антимагічна.

Твердження 4.2.1. Для подвійної зірки порядку n (n?5) стандартна нумерація ребер є антимагічною.

Дерево T назвемо r-регулярним висоти h, якщо воно містить, крім кінцевих вершин, що знаходяться на відстані h від центра, тільки вершини степеня r, r>1.

Твердження 4.2.3. r-регулярні дерева висоти h антимагічні.

У підрозділі 4.3 «Повні ярусні (r₀, r₁, …, r_k)-регулярні дерева» введено ряд означень та доведена антимагічність розглянутих дерев з використанням стандартної нумерації.

Означення 4.3.1. Вершинним ярусом h у центральному дереві назвемо множину вершин, що знаходяться на відстані h від центра. Центральна вершина дерева утворює нульовий ярус.

Означення 4.3.2. Повним ярусним (r₀, r₁, …, r_k)-регулярним деревом назвемо k-ярусне дерево з центральною вершиною степеня r₀ і з степенями всіх вершин і-го ярусу, рівними r_i.

Означення 4.3.3. Повне ярусне (r₀, r₁, …, r_k)-регулярне дерево будемо вважати монотонно спадним (незростаючим) від центра, якщо r₀?r₁?…?r_k -1. Аналогічно, якщо r₀?r₁?…?r_k -1, то дерево монотонно зростаюче (неспадне) від центра.

Твердження 4.3.4. Повне двоярусне регулярне монотонно спадне дерево антимагічне.

Твердження 4.3.5. Повне триярусне (r₀, r₁, r₂, r₃)-регулярне монотонно спадне дерево антимагічне.

Проводячи аналогічні міркування для повного k-ярусного (r₀, r₁, …, r_k)-регулярного монотонно спадного дерева, одержали узагальнений результат.

Твердження 4.3.6. Будь-яке повне kярусне (r₀, r₁, …, r_k)-регулярне монотонно спадне дерево антимагічне.

У підрозділ 4.4 «Антимагічність деяких видів графів» побудовано певні антимагічні нумерації простих ланцюгів P_n (n>2), простих циклів C_n (n?3), повних графів K_n (n>3), а також доведено наступні твердження:

Твердження 4.4.5. Довільний голландський m-вітряк - антимагічний граф.

Твердження 4.4.7. Граф С_nР₃ антимагічний для всіх натуральних n.

Твердження 4.4.8. Для непарних натуральних n граф B(C_n, P₂, C_n) антимагічний.

У підрозділі 4.5 «Встановлення антимагічності скінченного графа» наведено розроблений дисертантом алгоритм перевірки графа на антимагічність.

ВИСНОВКИ

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

Дисертантом встановлено, що для кожного з 132 існуючих неізоморфних зв'язних (7,10)-графів G існує циклічний (К₂₁, G)-розклад, і знайдено базову компоненту одного з таких розкладів. Під час розгляду циклічних пентагональних розкладів введено поняття кортежу довжин, базового набору довжин. Розроблено спосіб побудови базових компонент циклічного (К_n, С₅)-розкладу. Він може бути модифікований на випадок циклічних (К_n, С_m)-розкладів. На основі цього способу знайдено алгоритми і складено програми пошуку списків циклічних (К₁₁, С₅)- та (К₂₁, С₅)-розкладів. Для розрізнення-ототожнення розкладів введено узагальнений граф верхніх ребер G_УВ та графи Inb(R) і Inс(R), що є графічними інваріантами. Застосування специфікаційного інваріанта - таблиці Т(R) та графічних інваріантів у множині циклічних (К_n, С₅)-розкладів дало можливість одержати вичерпний список неізоморфних пентагональних циклічних розкладів графа К₁₁ та нижню оцінку числа неізоморфних циклічних (К₂₁, С₅)-розкладів. Доведено необхідну умову ізоморфності циклічних (К_п, С₅)-розкладів. Знайдено верхню оцінку числа неізоморфних циклічних (К_п, С₅)-розкладів, а також нижню оцінку числа неізоморфних циклічних призматичних та барвінкових розкладів графа K₁₉.