Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Національна академiя наук України
Iнститут кiбернетики ім. В.М.Глушкова
Петренюк Анатолiй Якович
УДК 519.1
Екстремальнi розклади повних графiв:
iснування, перелiк
01.05.01 - теоретичнi основи iнформатики
та кiбернетики
Автореферат дисертацiї
на здобуття наукового ступеня
доктора фiзико-математичних наук
Київ 2002
Дисертацією є рукопис.
Робота виконана в Інституті кібернетики ім. В.М.Глушкова Національної академії наук України.
Науковий консультант : доктор фізико-математичних наук
Донець Георгій Панасович,
Інститут кібернетики імені В.М.Глушкова Національної академії наук України,
завідувач відділом
Офіційні опоненти:
доктор фізико-математичних наук, професор, академік Національної академії наук України Шор Наум Зуселевич , Інститут кібернетики імені В.М.Глушкова Національної академії наук України, завідувач відділом,
доктор фізико-математичних наук, професор Анісімов Анатолій Васильович, Київський національний університет імені Тараса Шевченка, завідувач кафедрою,
доктор фізико-математичних наук, професор Асельдеров Зайнутдін Макашаріпович, Інститут математичних машин і систем Національної академії наук України, провідний науковий співробітник.
Провідна установа:
Дніпропетровський державний університет, кафедра обчислювальної математики та математичної кібернетики, м. Дніпропетровськ.
Захист відбудеться 22 листопада 2002 р. об 11 годині на засіданні
спеціалізованої вченої ради Д 26.194.02 при Інституті кібернетики імені В.М.Глушкова
Національної академії наук України за адресою:
МСП Київ –, проспект Академіка Глушкова,40.
З дисертацією можна ознайомитися в науково-технічному архіві Інституту.
Автореферат розісланий 10 жовтня 2002 р.
Учений секретар
спеціалізованої вченої ради СИНЯВСЬКИЙ В.Ф.
ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Актуальність проблеми. Більше як 150 років тому, у 1847 р. Т.П.Кіркман довів, що системи, які зараз називаються штейнеровими системами трійок порядку n, існують тоді і тільки тоді, коли
n=1 або 3(mod 6).
Близько 100 років тому де Паскуаль установив факт, що існують тільки дві неізоморфні штейнерові системи трійок порядку 13.
Ці дві події можна вважати початком величезної низки досліджень і результатів, що складають тематику, до якої належить і ряд робіт автора дисертації. Основні задачі цього напряму у загальному вигляді зручно формулюються в термінах теорії графів.
Маємо мультиграф H та сімейство звичайних графів G={g1, g2,..., gk}. Розкладом мультиграфа H на графи з сімейства G називають розбиття множини ребер графа H на такі підграфи (компоненти розкладу), кожний з яких ізоморфний одному з елементів множини G. Такі розклади називають (H, G)-розкладами.
Загальна кількість компонент у розкладі називається розміром (або рангом) розкладу.
Стосовно розкладів формулюються і розв'язуються такі задачі.
Задача 1.1(задача існування). Задано H та G. Чи існують (H, G)-розклади?
Ця задача буде розв'язана позитивно, якщо розв'язана наступна задача побудови.
Задача 1.2. Задано H та G. Побудувати (H, G)-розклад.
Дослідження розкладів графів на підграфи із заданої множини розпочалося у 70-х роках XX ст. Серед багатьох дослідників назвемо Л.Байнеке, Ф.Харарі, Д.Босака, А.Роса, С.Знама, Р.Вільсона, Ш.Хуанг. Із різних аспектів цієї теми існує багато публікацій, і їх потік не виснажується.
(H, G)-розклади та щойно сформульовані задачі узагальнили задачі про 1-факторизації, штейнерові системи трійок (тобто (Kn,{K3})-розклади), неповні зрівноважені блок-схеми та ін., що на той час уже стали класичними. Класичні розклади мають істотні застосування у плануванні експериментів, при побудові ефективних кодів тощо. Природно чекати здатності до застосувань і від більш загальних розкладів.
Одне із застосувань розкладів повного графу на певні 5-вершинні підграфи описане у статті Ч.Колбурна і П.Вана (C.J.Colbourn, P.J.Wan, 2001). Робота колективу авторів (Colbourn C.J., Dinitz J.H., Stinson D.R., 1999) присвячена застосуванням комбінаторних схем у різних галузях людського життя
Типовою задачею існування є задача про існування T-факторизацій повного графа, або (Kn,T)-розкладів, про яку йдеться в розділах 3-5. Класичними роботами, де розв'язувалися подібні задачі, є роботи Х.Ханані ( Hanani H., 1975) та стаття Д. Рея-Чоудхурі і Р.Вільсона (Ray-Chaudhury D.K., Wilson R.M., 1971). У вказаних працях розв'язування задач існування проводиться "з двох кінців": спочатку за допомогою необхідних умов існування встановлюються випадки неіснування досліджуваних розкладів, а потім підключаються методи побудови, за допомогою яких встановлюється існування в усіх інших випадках. Така схема дослідження виправдала себе при розв'язуванні дисертантом задачі існування T-факторизацій порядків 10 та 14 у розділі 3.
Задача 1.3 (задача переліку). Задано H та G. Скільки, з точністю до ізоморфізму, існує (H, G)-розкладів?
Історія цієї задачі розпочалася у кінці XIX –на початку ХХ століття, коли були одержані перші результати переліку 1-факторизацій повних графів (Dickson L.E., Safford F.N. 1906) та штейнерових систем трійок (de Pasquale V., 1899; White H.S., Cole F.N., Cummings L.D., 1919). Пора її розквіту припадає приблизно на 1922 р., коли було перелічено всі 80 штейнерових систем трійок порядку 15.
З 50-х до 80-х р.р. ХХ століття вивчення класичних розкладів в основному сконцентрувалося на задачах існування та побудови, і з'являлися лише поодинокі результати, що стосувалися задачі переліку. На кінець вказаного періоду становище вирівнялося, і тепер задача переліку заволоділа увагою багатьох дослідників.
Якщо існують (H, G)-розклади, то позначимо g(H, G) найменший з можливих розмірів цих розкладів. (H, G)-розклад називається мінімальним, якщо він має розмір g(H, G).
Аналогічно вводиться поняття максимального розкладу. Мінімальні та максимальні розклади називають екстремальними. У багатьох випадках саме екстремальні розклади викликають найбільший інтерес як з точки зору існування та побудови, так і з точки зору переліку. У розділах 3-10 дисертації розглядаються екстремальні розклади того чи іншого виду з названих точок зору.
Розглядаються , як правило, розклади повних графів, тобто (H, G)-розклади з H=Kn. У більшості випадків розглядаються (Kn, G)-розклади з ЅGЅ=1, тобто ізокомпонентні розклади, хоча приділено певну увагу і розкладам з більшими значеннями ЅGЅ.
Мета роботи. У дисертації розвиваються та узагальнюються методи розв'язування сформульованих вище задач. Ці методи напрацьовані дисертантом більше, ніж за 30 років наукової діяльності.
Розклади, що розглядаються у різних розділах дисертації, відрізняються складом множини допустимих компонент. Тому розв'язування задач існування та перелік цих розкладів проводяться різними шляхами. Проте є багато спільних рис у способах проведення досліджень, отже на перший план виходить завдання уніформізації (де можливо) підходів та універсалізації методів роботи з цими та подібними комбінаторними конфігураціями.
Дисертація включає ряд результатів завершеного характеру. Одні з них стосуються побудови (Kn,G)-розкладів, інші –переліку цих комбінаторних конфігурацій.
Методи досліджень. У дисертації застосовувалися методи лінійної алгебри, теорії чисел, теорії графів та комбінаторного аналізу.
Наукова новизна. Фактично у розділах 3-10 викладаються по кілька нових результатів, одержаних дисертантом або у співпраці з співавторами. Дисертантом введено ряд нових понять (поняття півобертових та біциклічних T-факторизацій, розщеплення, D-розкладу, шаблонного представлення графів і т. ін.) , сформулювано та доведено ряд необхідних умов існування T-факто- ризацій та біциклічних T-факторизацій, сформульовано ряд нових задач та висунуто кілька гіпотез.
Теоретична та практична цінність дисертаційної роботи полягає якраз в отриманні нових результатів та методах, за допомогою яких ці результати одержано.
Особистий внесок здобувача. У працях [2], [9], [17], [27], [31-42], написаних у співавторстві, співавтор допомагав створювати програмний продукт та перевіряти результати розрахунків. В інших сумісних роботах здобувач був автором наукової ідеї та її теоретичного доведення, а співавтори під його керівництвом доводили її до завершення у вигляді наукової статті.
Апробація роботи. Результати досліджень дисертанта неодноразово доповідалися на постійно діючому семінарі "Математика, її викладання та застосування" в 1995–р.при Кіровоградському педагогічному університеті, на Всесоюзних та Міжнародних семінарах з дискретної математики та її застосувань, які періодично проводились на мехматі Московського державного Університету, на V Міжнародній конференції ім. акад. М.Кравчука. У 2001 р. зроблено пленарну доповідь на VII Міжнародному семінарі з дискретної математики та її застосувань (Москва, МДУ, 29 січня - 2 лютого 2001 р.), доповідь на Українському математичному конгресі та доповідь на теоретичному семінарі в Інституті кібернетики ім. В.М.Глушкова НАН України.
Опубліковані результати дисертації знайшли позитивний відгук у світовій математичній літературі. Так, у бібліографічних публікаціях перелічено кілька статей дисертанта. Ряд статей зарубіжних авторів вміщує посилання на його роботи, а у деяких статтях застосовуються і розвиваються розроблені ним методи з посиланням на відповідні роботи, де ці методи опубліковано.
Публікації. За темою дисертації опубліковано 51 статтю, з них 22 статті дисертант опублікував одноосібно. У фахових виданнях опубліковано 22 статті.
Структура та обсяг. Дисертація складається із вступу, списку умовних позначень, 10 розділів, 15 додатків та списку використаних джерел, який вміщує 171 найменування. Загальний обсяг – сторінок.
ЗМІСТ РОБОТИ
У вступі до дисертації коротко викладено мету та зміст розділів дисертаційної роботи.
У розділі 1 "Формулювання та сучасний стан задачі" сформульовано основні задачі, що розв'язуються у дисертації, розглянуто їх історичний генезис та сучасний стан.
Розділ 2 "Теоретичні основи розв'язування задач, що розглядаються у дисертації" присвячений теоретичним підвалинам дисертації. Мова йде, зокрема, про так зване шаблонне представлення графів; значною мірою за рахунок його застосування досягнуто помітних успіхів у комп'ютерних побудовах та переліках. Далі розглянуто способи побудови розкладів повних графів, серед них виділено напівобертовий метод, метод побудови біциклічних T-факторизацій та метод рівновагових перетворень у численних його проявах.
Розглянуто також способи розрізнення/ототожнення розкладів, серед яких центральне місце займає метод інваріантів. Застосування інваріантів для розрізнення комбінаторних конфігурацій започатковане дисертантом у статті [25]. Відтоді інваріанти надійно зайняли важливе місце в арсеналі методів розрізнення/ототожнення. У дисертації проведено класифікацію інваріантів, а саме виділено інваріанти числові, специфікаційні, графічні, групові та ін. Особливу групу інваріантів складають повні інваріанти, серед яких виділяється такий інваріант як канонічна форма розкладу.
У розділі 3 "Деревні факторизації повних графів" розв'язується задача існування T-факторизацій, яку вперше сформулював Л.Байнеке (Beineke L.W., 1964).
Сімейство n-вершинних дерев T1,T2,...,Ts називають деревною упаковкою розміру s повного n-вершинного графа Kn , якщо: 1) всі ці дерева –підграфи графа Kn ; 2) жодні два з них не мають спільних ребер. Якщо, крім того, кожне ребро графа Kn належить деякому дереву упаковки, то таку упаковку називають деревною факторизацією графа Kn. Дерева, що складають упаковку, називаються компонентами.
Деревна упаковка (факторизація), всі компоненти якої ізоморфні дереву T, називається T-упаковкою (T-факторизацією). Одна з актуальних у даний період задач: для яких дерев T існують T-факторизації графа Kn?
Л.Байнеке показав, що для існування T-факторизації необхідно, щоб n було парним числом і щоб виконувалася умова D(T)Јn/2, де D(T) позначено найбільшу степінь вершини у дереві T. Дерева, які задовольняють умові Байнеке, називаються допустимими. Ш.Хуанг і А.Роса (Huang C., Rosa A., 1978) повністю розв'язали задачу про існування T-факторизацій для парних значень nЈ8. Дисертантові [46] вдалося розв'язати цю задачу у випадку n=10; виявилося, що серед 106 існуючих неізоморфних дерев порядку 10 85 допускають T-факторизацію. Для парних значень n>10 повного розв'язку цієї задачі поки що не одержано.
Дисертант застосував метод побудови T-факторизацій, який названо напівобертовим. Суть його в тому, що для деяких дерев T порядку n=2k компоненти T-факторизації отримують у вигляді T, Ta,..., Tak-1, де a –підстановка множини вершин, що являє собою цикл довжини n. З іншого боку, напівсиметричним називається дерево порядку n=2k, що допускає такий автоморфізм порядку 2, який залишає на місці центральне ребро дерева, переставляючи його кінці. У дисертації доведено (теореми 3.1-3.3), що всі напівсиметричні дерева порядків n=12, 14 та 16 допускають напівобертові T-факторизації. На основі цих результатів висунута
Гіпотеза 3.1. Будь-яке напівсиметричне дерево T допускає напівобертову T-факторизацію.
Доведено існування напівобертових T-факторизацій для серій дерев: подвійних зірок, дзеркальних віял та H-дерев.
Допустиме дерево T порядку n=2k визначає вектор d(T)=(d1,d2,..., dk), де di –кількість вершин у T, які мають степінь i. Одержано необхідну умову d2іd4 існування T-факторизації для допустимого дерева порядку 10. Показано, що ця умова не виконується для деяких допустимих дерев, тобто вона здатна встановлювати неіснування T-факторизацій. За допомогою її, методом від супротивного та за допомогою біциклічного методу побудови T-факторизацій одержано вищезгаданий результат для n=10.
Ця необхідна умова була узагальнена до наступних необхідних умов існування T-факторизацій.
Теорема 3.14. Якщо допустиме дерево порядку n=2k і10 допускає T-факторизацію, то
d2іdk-1. (3.12)
Теорема 3.16. Якщо допустиме дерево T порядку n=2k, kі6, допускає T-факторизацію, то
d2 + 2d3 і 2dk-2. (3.13)
Теорема 3.18. Якщо допустиме дерево порядку n=2k, kі8, допускає факторизацію, то
d2+3d3+3d4 і 3dk-3. (3.15)
Щоб показати дієспроможність цих необхідних умов, для кожної з них побудовані серії дерев, неіснування T-факторизацій для яких встановлюється за допомогою саме цієї необхідної умови. Наприклад, серію дерев, що не задовольняють необхідну умову (3.15), зображено на рис.3.5.
Як виявилося, кожне дерево порядку 10, що допускає T-факторизацію, допускає також біциклічну T-факторизацію. Це стало підставою сподіватися, що біциклічні T-факторизації певною мірою зберігають цю властивість всюдисутності i для інших парно-непарних порядків. Тому дисертант зацікавився біциклічними T-факторизаціями.
Рис. 3.5. Допустиме дерево, що не задовольняє умові (3.15)
Розділ 4 "Біциклічність і T-факторизації порядку 14". T-факторизація порядку n=2k називається біциклічною, якщо вона допускає автоморфізм, який має два незалежні цикли, кожний довжиною k, тобто автоморфізм у вигляді a=(1,2,...,k)(k+1,k+2,...,n).
Такий автоморфізм називається породжуючою підстановкою біциклічної T-факторизації. Маючи одну з компонент C (базову компоненту) та породжуючу підстановку a деякої біциклічної T-факторизації, можна розвинути всю T-факторизацію {C,Ca ,...,Cak-1}.
Для існування біциклічної T-факторизації порядку n=2k необхідно, щоб k було непарним числом.
Для демонстрації побудовчої ефективності поняття біциклічної T-факторизації побудовано DS2k-факторизації для кожного kі3, де DS2k –подвійна зірка, тобто допустиме дерево порядку 2k, у якого всі вершини кінцеві, крім двох, степені яких рівні k.
Загальну необхідну умову існування біциклічних T-факторизацій описано наступною теоремою.
Теорема 4.1. Якщо дерево T допускає біциклічну T-факторизацію, то вектор d(T) може бути представлений у вигляді суми двох таких векторів d1=(d1(1),...,dk(1)) і d2=(d1(2),...,dk(2)) з невід'ємними цілими компонентами, що при j=1,2 виконуються співвідношення
d1(j)+...+dk(j)=k, (4.1)
d1(j)+2d2(j)+...+kdk(j)=n-1 . (4.2)
Представлення вектора d(T) у вигляді суми двох векторів d1, d2, які мають невід'ємні цілі компоненти та задовольняють умовам (4.1), (4.2), називається розщепленням вектора d(T).
Теорему 4.1 можна переформулювати в такому вигляді.
Теорема 4.2. Для існування T-факторизації дерева T з розподілом степенів вершин d(T) необхідно, щоб існувало розщеплення вектора d(T).
Відомо, що існують точно 3159 неізоморфних дерев порядку 14. Разом з Д.Дурачем та А.І.Приходькіною сформовано повний список цих дерев. Виявилося, що серед них точно 3081 дерево допустиме.
Множину допустимих дерев порядку 14 було розділено на 6 класів T[14,s], s=2,...,7, де клас T[14,s] складається з тих дерев порядку 14, для яких D(T)=s. Кожний з цих класів розглянуто окремо.
Клас T[14,2] складається з одного дерева –ланцюга P14, і це дерево допускає біциклічну факторизацію.
Клас T[14,3], або клас бінарних дерев, складається з 551 неізоморфних дерев. Виявилося [10, 16], що кожне дерево T з цього класу допускає біциклічну T-факторизацію. Це підтверджується додатком А, у якому для кожного дерева класу T[14,3] побудована біциклічна T-факторизація.
Дослідження класу T[14,4] показало [47], що кожне дерево цього класу теж допускає біциклічну факторизацію. Підтвердженням цього факту є додаток Б, де представлені базові компоненти біциклічної T-факторизації для кожного з дерев класу T[14,4].
Клас T[14,5] складається з 775 дерев, і 766 з них допускають біциклічні T-факторизації. Решта 9 дерев не допускають ніяких T-факторизацій.
Клас T[14,6] має потужність 321. У статті [26] дисертант встановив, що точно 304 дерева цього класу допускають біциклічні факторизації, а решта –не допускають.
Нарешті, клас T[14,7] складається з 127 дерев. Виявилося , що точно 91 з них допускають біциклічні факторизації. З решти дерев 17 не допускають небіциклічних факторизацій, а на питання про існування небіциклічних T-факторизацій для інших 20 дерев поки що не одержано відповіді.
Для допустимого дерева T класу T[14,6] з єдиною вершиною степеня 6 позначимо m(T) кількість кінцевих вершин, суміжних з вершиною степеня 6, та g(T) - кількість ребер, які з'єднують вершини проміжних (відмінних від 1 та 6) степенів.
Наступні теореми 4.8, 4.9, 4.11 та 4.12 містять необхідні умови існування біциклічних T-факторизацій для дерев класів T[14,6] та T[14,7]. Напевне, подібні твердження можна сформулювати та довести і для T-факторизацій більших порядків.
Теорема 4.8. Нехай дерево T класу T[14,6] з єдиною старшою вершиною допускає біциклічну T-факторизацію. Тоді 1) якщо Т не включає 2-вершину, суміжну або з кінцевою вершиною, або зі старшою, то m(T)і3; 2) якщо T включає 2-вершину, суміжну або зі старшою вершиною,або з кінцевою, то m(T)і2; 3) якщо T включає 2-вершину, суміжну одночасно з кінцевою та зі старшою вершиною, то m(T)і1.
Теорема 4.9. Якщо T –дерево класу T[14,6], яке допускає біциклічну T-факторизацію, то g(T)Ј5.
Теорема 4.11. Якщо дерево T класу T[14,7] допускає біциклічну T-факторизацію, то
d1іm(T)+3, (4.3)
m(T)і3. (4.4)
Теорема 4.12. Якщо дерево T класу T[14,7] допускає біциклічну T-факторизацію, то
g(T)Ј3, (4.5)
d1=6+m(T)-g(T) . (4.6)
У підрозділі 4.15 описано алгоритм побудови біциклічної T-факторизації порядку 14, заснований на стратегії стрибків, за рахунок якої економиться машинний час.
У підрозділі 4.16 введено дві функції nua(n) та nuabic(n) у такий спосіб. Значення nua(n) дорівнює m, коли для кожного дерева
T О T[n,2] И T[n,3] И...И T[n,m]
існує T-факторизація, а деяке TОT[n,m+1] не допускає T-факторизації. Функція nuabic(n) означується цілком аналогічно, лише вираз "T-факторизація" замінюється на "біциклічна T-факторизація".
Важливість цих функцій полягає в тому, що їх значення характеризують область суцільної допустимості
T[n,2] И ... И T[n, nua(n)]
та область суцільної біциклічної допустимості
T[n, 2] И ... ИT[n, nuabic(n)].
Із вищевикладеного для випадку n=14 одержується такий частковий результат.
Теорема 4.16. nua(14)=nuabic(14)=4.
Висловлено кілька правдоподібних гіпотез щодо цієї функціональної пари.
У розділі 5 "Перелік неізоморфних T-факторизацій" ставиться, і в ряді випадків розв'язується, задача про значення таких функцій :
N(T) –кількість неізоморфних T-факторизацій для дерева T порядку n;
Nб(T) –кількість неізоморфних біциклічних T-факторизацій;
Nп(Т) –кількість неізоморфних напівобертових T-факторизацій.
Крім значень N(T), Nб(T) та Nп(T), цікаво також одержати відповідні списки T-факторизацій.
Задача знаходження N(T) розв'язана для всіх дерев порядків nЈ8. У роботі [46] перелічено всі деревні факторизації порядку 6, а в дисертації Петренюк Л.П. (1996) перелічені всі T-факторизації порядку 8. Для n=2kі10 значення N(T) та відповідні списки знайдено лише для деяких дерев [3].
Для подальшого прогресу у цій задачі виявився корисним спосіб швидкого знаходження канонічної форми T-факторизації, знайдений дисертантом і описаний у підрозділі 5.3. При його реалізації використовується група автоморфізмів дерева, яке грає роль компоненти. У підрозділі 5.4 описано алгоритм переліку T-факторизацій, який застосовувався у випадку n=10.
Зірчасте дерево Y має порядок 10 і складається з ребер
1-2, 1-3, 1-4, 2-5, 2-6, 3-7, 3-8, 4-9, 4-A.
Його група автоморфізмів має порядок 48. Доведено (теорема 5.1), що N(Y)=172, і представлений повний список Y-факторизацій.
Відомі п'ять початкових значень функції N(DS2k); ці значення наводяться в табл. 5.2, яка вперше з'явилася в [48].
Вичерпний список DS10-факторизацій опублікований у [48]; його відтворено у табл.5.3. Тут DSn записується у вигляді a1a2.a3...ak+1.ak+2...an, де a1,...,an –попарно відмінні вершини, a1,a2 –кінці центрального ребра DSn, вершини a3,...,ak+1 інцидентні вершині a1, а інші вершини інцидентні вершині a2. Список неізоморфних DS12-факторизацій уперше був опублікований у [44]; його повністю відтворено в табл.5.4.
Порівняна нечисленність DS10-факторизацій пояснюється двома обставинами. По-перше, функція D досягає на DS10 найбільшого можливого для допустимих дерев порядку 10 значення 5, причому є дві вершини степеня 5. По-друге, Aut(DS10) складається з 1152 автоморфізмів; це одна з найчисленніших груп автоморфізмів дерев порядку 10.
Для дерев T16 та T18 порядку 10 знайдено значення N(T16)=23, N(T18)=230 та представлено відповідні канонічні списки неізоморфних факторизацій. Перший з них наведений в табл. 5.5, а другий представлений у додатку И до дисертації.
У підрозділі 5.6 сформульовано задачу, подібну задачі Роса (Rosa A., 1990), у якій ставиться питання про спектр розмірів упаковок кожного дерева порядку 2k.
Підрозділи 5.7 та 5.9 присвячено задачі переліку біциклічних T-факторизацій порядку 14. У цих розділах Ti означає дерево номер i в канонічному списку неізоморфних дерев класу T[14,7]. Одержано ряд значень чисел Nб(T), які наведено нижче. Ці значення стверджено повними списками базових дерев відповідних біциклічних T-факторизацій; тут список наводиться тільки для дерева T96.
Кожна з цих T-факторизацій представлена базовим деревом, що розгортається у T-факторизацію під дією автоморфізмів ai, де a=(1234567)(89ABCDE) –базовий автоморфізм. Дерева представлено стандартизованими списками їх ребер.
Доведено, що Nб(T96)=4, Nб(T111)=4, Nб(T115)=8,Nб(T1)=2, Nб(T2)=4, Nб(T3)=4, Nб(T4)=12, Nб(T5)=16, Nб(T6)=30, Nб(T7)=6, Nб(T8)=8, Nб(T9)=6 (теореми 5.5–.16).
У підрозділі 5.8 описані інваріанти, які використовувалися для обгрунтування неізоморфності T-факторизацій в одержаних списках. У підрозділі 5.7 описано алгоритм переліку біциклічних T-факторизацій, який одержано відповідною модифікацією алгоритму побудови з підрозділу 4.15. На основі алгоритму переліку написано програму, за допомогою якої були одержані вищенаведені значення Nб(T).
Конструктивно доведено, що Nп(DS14)=16 (теорема 5.17).
У цьому ж підрозділі сформульовано оцінку знизу числа неізоморфних напівобертових DS2k-факторизацій.
У підрозділі 5.11 йдеться про різнокомпонентні деревні факторизації повних графів.
Сімейство дерев {T1ґ,T2ґ,...,Tsґ} називається (T1,T2,...,Ts)-факторизацією графа Kn, якщо: 1) кожне дерево Tiґ(i=1,...,s) має порядок n, є каркасним деревом графа Kn і ізоморфне дереву Ti; 2) Tiґ, Tjґ не мають спільних ребер при 1Јi<jЈs; 3) кожне ребро графа Kn міститься в одному з дерев Tiґ(i=1,...,s).
У випадку, коли виконання умови 3) не обов'язкове, означене сімейство дерев називається (T1,T2,...,Ts)-упаковкою.
Дерева, що складають факторизацію чи упаковку, називаються її компонентами. Послідовність T1,T2,...,Ts називається заголовком (T1,T2,...,Ts)-факторизації. Якщо всі дерева, вказані в заголовку, ізоморфні дереву T, то одержується вже відома T-факторизація, або ізокомпонентна деревна факторизація. (T1,T2,...,Tk)-факторизація називається різнокомпонентною, якщо серед її компонент є дві неізоморфні.
У зв'язку з введеними поняттями постають дві задачі, що узагальнюють задачу про існування та задачу про перелік T-факторизацій. Перша: для яких заголовків T1,T2,...,Tk існують (T1,T2,...,Tk)-факторизації? Друга: для кожного заголовка (T1,T2,...,Tk) вказати перелік усіх попарно неізоморфних (T1,T2,...,Tk)-факторизацій та його потужність N(T1,T2,...,Tk).
Стосовно першої задачі слід зазначити таке.
Необхідними умовами існування (T1,T2,...,Tk)-факторизацій є: 1) n=2k; 2) D(Ti)Јk для всіх i=1,...,k (узагальнені умови Байнеке).
Покладемо d(Ti)=(di1,di2,...,dik), i=1,2,...,k.
Крім того, введемо позначення Dj = d1j+d2j+...+dkj (j=1,2,...,k) і вектор D=(D1,D2,...,Dk).
Виявилося, що поняття типу вершини та вектора a=a(R) легко переносяться на загальний випадок. У цих позначеннях можна записати матричне рівняння
aS=D, (5.1)
яке є аналогом і узагальненням рівняння (3.4), та сформулювати теорему, аналогічну теоремі 3.1. Відповідний аналог теореми 3.2 можна сформулювати у вигляді
Теорема 5.19. Якщо існує {T1,T2,...,T5}-факторизація, то D2іD4.
Друга задача для n=6 розв'язана дисертантом у згадуваній статті [46]. У дисертації Л.П.Петренюк (1996) опублікувано списки неізоморфних різнокомпонентних (T1,T2,T3,T4)-факторизацій для низки заголовків.
У дисертації викладено результат, опублікований у статті [2], який полягає в переліку різнокомпонентних деревних факторизацій порядку n=10 для кількох заголовків.
Нехай знову Ti позначено дерево, зображене на діаграмі номер i (i=1,2,...,106) у списку дерев порядку 10, вміщеному в монографії Ф.Харарі "Теория графов".
Введемо позначення
r(i,j) = N(Ti,Ti,Ti,Ti,Tj).
Ми знайшли значення r(i,j) у випадках, коли Ti,Tj мають розподіл степенів вершин d(T)=54001. Існують 5 дерев із вказаним розподілом (T15 – T19), і знайдені для них значення наведені в табл. 5.6.
Список неізоморфних T16-факторизацій наведено в табл.5.5. У дисертації маємо ще наступні три списки:
неізоморфних (T16,T16,T16,T16,T17)-факторизацій;
неізоморфних (T17,T17,T17,T17,T18)-факторизацій;
неізоморфних (T17,T17,T17,T17,T19)-факторизацій.
Нарешті, в підрозділі 5.12 описано матрично-орбітальний інваріант, що використовувався у дослідженнях як альтернативний канонічній формі для розрізнення неізоморфних деревних факторизацій.
Розділ 6 "Розклади повних графів на нерегулярні компоненти" вміщує результати переліку колісних упаковок та зіркових розкладів повних графів.
Колесом з m спицями (mі3) називають граф, що являє собою з'єднання циклу Cm та графа K1. Вершину степеня m у колесі називають центром, а інцидентні їй ребра –спицями. Решту вершин і ребер колеса називають, відповідно, вершинами та ребрами ободу. Колесо з m спицями позначають Wm і записують (a)x1x2...xm, де a –центр, x1,x2,...,xm –послідовно записані вершини ободу колеса.
Якщо за множину вершин графа Kn взяти стандартну множину Іn={1,...,n}, то підграф графа Kn, що є колесом Wm, для однозначності записуємо у стандартному вигляді (a)x1x2...xm, де a -–центр, x1 –вершина ободу з найменшим номером, а x2 –та з двох сусідніх з x1 вершин ободу, номер якої менший.
Упаковкою рангу r коліс у граф Kn називають таке сімейство P коліс, що: 1) P складається з r коліс; 2) кожне колесо з P є підграфом графа Kn ; 3) жодні два колеса з P не мають спільних ребер.
Розкладом графа Kn на колеса називають упаковку, у якій кожне ребро графу Kn належить деякому колесу. У дисертації розглядається задача переліку колісних розкладів та упаковок.
Відомо, що розклади графа K17 на колеса вміщують тільки колеса W4, і при цьому кожна вершина графа K17 є центром одного й тільки одного колеса розкладу. Задача переліку розкладів графа K17 на колеса поки що не розв'язана.
Певні результати в цьому напрямку одержано за допомогою комбінування пошуку у ширину на початкових етапах з завершальним пошуком у довжину. Кількісні результати переліку неізоморфних упаковок невеликих рангів наведено в табл. 6.1.
Наведено відповідні списки упаковок і знайдено порядки груп автоморфізмів упаковок рангу 4. Зроблено опис розрізнюючих та ототожнюючих інваріантів, зокрема інваріанта Sp.
Називатимемо k-зіркою граф порядку k+1, який має точно k ребер, що з'єднують деяку вершину (центр зірки) з іншими вершинами (периферійними) зірки. k-Зірку з центром a та периферійними вершинами a1, a2,..., ak записують (a)a1a2...ak. Розклад графа Kn на k-зірки називають зірковим (n,k)-розкладом.
Для існування зіркового (n,k)-розкладу необхідно виконання умов
n(n–) є 0(mod 2k); (6.2)
nі2k. (6.3)
Опиcано кілька прийомів побудови зіркових (n,k)-розкладів.
Зірковий (n,k)-розклад графа Kn називається регулярним степеня l, якщо кожна вершина графа Kn є центром точно l зірок цього розкладу. Доведено наступні теореми.
Теорема 6.1. Для існування регулярного зіркового (n,k)-розкладу необхідно і досить, щоб l=(n–)/(2k).
Теорема 6.2. Існує єдиний, з точністю до ізоморфізму, зірковий (6,3)-розклад.
Теорема 6.3. Будь-який зірковий (7,3)-розклад ізоморфний одному з п'ятьох попарно неізоморфних розкладів, указаних у дисертації.
Якщо позначити z(n,k) число всіх попарно неізоморфних зіркових (n,k)-розкладів, то можна узагальнити теореми 6.2, 6.3 у вигляді наступної теореми.
Теорема 6.4. z(6,3)=1, z(7,3)=5, z(8,4)=3.
Результати, викладені в теоремах 6.2-6.4, опубліковано у [5]. Далі наведено результати переліку регулярних та циклічних зіркових розкладів [29].
Теорема 6.6. З точністю до ізоморфізму, існують 58 зіркових (9,4)-розкладів; серед них 15 регулярних і 43 нерегулярних.
Для розрізнення зіркових (9,4)-розкладів застосовано два типові специфікаційні інваріанти: n-таблиця та С-інваріант.
zc(2k+1,k) позначається число неізоморфних циклічних (2k+1,k)-розкладів. Тоді справедлива
Теорема 6.7. Для кожного k О N виконується нерівність zс(2k+1,k)Ј2k-1.
На її основі висунута
Гіпотеза. Функція zc(2k+1,k) асимптотично наближається до 2k-1/k при k®Ґ за послідовністю значень k, для яких 2k+1 –прості числа.
У підрозділі 6.5 представлено результат переліку розкладів повних графів на вітряки ( рис. 6.7), а саме, доведена
Теорема 6.10. Існують 50 попарно неізоморфних циклічних розкладів графа K19 на вітряки.
Рис. 6.7. Вітряк
Підрозділ 6.6 вміщує результат про перелік розкладів повного графа на митри (рис. 6.8), представлений наступною теоремою.
Рис.6.8. Митра
Теорема 6.12. З точністю до ізоморфізму, існують точно 4 циклічні митральні розклади графа K15.
У підрозділі 6.6 вивчаються так звані циліндричні розклади графів. Установлено такі твердження.
Теорема 6.13 . З точністю до ізоморфізму, існують точно 125 3ґ3 циліндричних розкладів графа K9 на дракони D3,1.
Теорема 6.14. З точністю до ізоморфізму, існують рівно 147 розкладів графа K8 на дракони D3,1.
Підрозділи 6.4-6.6 містять детальний розбір механізмів розрізнення та ототожнення досліджуваних розкладів.
Розділ 7 називається "1-Факторизації та зв'язані з ними задачі".
Регулярний підграф степеня 1 у графі G порядку 2n називають 1-фактором графа G, якщо множина вершин цього підграфа збігається з множиною вершин графа G. Два 1-фактори Fa і Fb графа G узгоджені, якщо FaИFb = C2n, тобто якщо їх об'єднання являє собою гамільтонів цикл графа G.
Сімейство F 1-факторів графа G порядку 2n, що складається з m 1-факторів, називається досконалою (m,2n)-конфігурацією (коротко: (m,2n)-конфігурацією), якщо кожні два її 1-фактори узгоджені; (m,2n)-конфігурація F називається розширюваною, якщо існує такий 1-фактор F графа G, що FИ{F} –(m+1,2n)-конфігурація. Фактор F називають тоді продовженням (m,2n)-конфігурації F. (m,2n)-конфігурація, що не є розширюваною, називається максимальною.
A.Роса (A.Rosa, 1990) сформулював задачу: визначити множину
Mperf(2n)={m : існує максимальна (m,2n)-конфігурація}.
У роботі [15] та в підрозділах 7.1.-7.2 дисертації ця задача розв'язана для n=10 та n=12. Встановлено, що Mperf(10)={5,6,7,9}, Mperf(12) = {6,7,8,9,10,11}.
Крім того, знайдено повний список неізоморфних мінімаксних конфігурацій порядку 12, який складається з двох конфігурацій.
У підрозділі 7.3 описано наступний алгоритм перевірки, ізоморфні чи ні два даних набори 1-факторів порядку 2n, які попарно не мають спільних ребер. Розглянемо випадок, коли обидва набори вміщують точно по N пар узгоджених 1-факторів, N>0. Нехай Hi, i=1,2,...,N,–відповідні гамільтонові цикли для першого набору та Ci, i=1,2,...,N, –для другого. Існують точно 4nN підстановок, що переводять H1 в Ci, коли i пробігає множину {1,2,...,N}. Позначимо цю множину підстановок П. Підстановка, яка здійснює ізоморфізм заданих наборів, якщо така існує, мусить бути серед них. Так що для досягнення мети досить перевірити тільки ці 4nN підстановок. Оскільки побудова вказаних підстановок і самі перевірки відбуваються за поліноміальний час, то описаний алгоритм поліноміальний.
У випадку перевірки на ізоморфізм (m,2n)-конфігурацій необхідно перевірити не більше, ніж 4nN=2mn(m–) підстановок, а у випадку досконалих 1-факторизацій це число дорівнює 2n2(2n–). В підрозділі 7.4 розглянуто задачі переліку 1-факторизацій повних та, вперше у цій роботі, неповних графів. Установлено, що існують, з точністю до ізоморфізму, точно дві 1-факторизації одиничного куба Q3 та точно 35 –для куба Q4. Останні 35 факторизацій поміщено в додатку Д. У зв'язку з цим результатом у дисертації сформульовано ряд задач і висунуто одну гіпотезу.
Розділ 8 присвячений розкладам кіркманового типу.
Розбиття множини E потужності n на трійки елементів називають паралельним класом (трійок). Кіркмановим розкладом (КР) порядку n називається таке сімейство паралельних класів множини E, що кожні два елементи множини E входять разом в одну і тільки одну з трійок, які приймають участь у паралельних класах цього сімейства. Множину E називають носієм кіркманового розкладу.
Кіркманів розклад порядку n можна розглядати як розклад повного n-вершинного графа Kn на такі його n-вершинні підграфи, що зв'язні компоненти кожного з них суть трикутники.
Очевидно, що для існування кіркманового розкладу порядку n необхідно, щоб nє3(mod 6). Д.Рей-Чоудхурі та Р.Вільсон у 1971 р. довели, що ця умова достатня.
Два кіркманові розклади R1 та R2 ізоморфні, якщо існує така взаємно однозначна відповідність між їх носіями, що кожному паралельному класові розкладу R1 відповідає паралельний клас розкладу R2.
У розділі 8 розглядається така задача.
Задача 8.1. Для натурального числа nє3(mod 6) скласти список усіх попарно неізоморфних кіркманових розкладів порядку n та вказати потужність N(n) цього списку.
Очевидно, N(3)=1. Неважко впевнитися у тому, що N(9)=1. Коул (F.N.Cole) у 1922 р. повністю розв'язав цю задачу у випадку n=15 і з'ясував, що N(15)=7. Нижню оцінку величини N(n) встановили канадські дослідники Д.Р.Стінсон та С.А.Ванстон (Stinson D.R., Vanston S.A.******************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************* інваріант H, здатний розрізняти КР, і за допомогою його виділено серед відомих на той час КР порядку 21 два неізоморфні.
У 1981 р. Р.Матон, К.Фелпс та А.Роса (Mathon R.A., Phelps K.T., Rosa A., 1981) опублікували список (список MPR), який вміщує 30 неізоморфних КР порядку 21. Згодом було опубліковано список Р.Матона і А.Роса (Mathon R.A., Rosa A., 1984) –список MR, що складається з 48 КР порядку 21, жоден з яких не належить до попереднього списку. Ще 5 нових КР порядку 21 (список T) знайдено й опубліковано В.Тончевим (Tonchev V.D.) у 1987 році.
У дисертації описано метод розрізнення неізоморфних КР (H-інваріант) та два методи побудови КР, які істотно різняться від циклічних.
Перший із згаданих методів побудови називається методом H-перетворень; суть його можна коротко викласти так. Нехай K1, K2 –два сімейства паралельних класів множини E. Їх називають рівновагомими на E, якщо кожна пара елементів множини E зустрічається в тій же кількості паралельних класів сімейства K2, у якій вона зустрічається в сімействі K1.
Нехай K –кіркманів розклад з носієм E, а K1, K2 –рівновагомі сімейства паралельних класів множини E, причому K1 О K. Тоді очевидно, що K'=(K\K1)+K2 являє собою кіркманів розклад на множині E.
Перехід від K до K' називають H-перетворенням кіркманового розкладу K. Якщо K1 вміщує s паралельних класів, то йдеться про sH-перетворення. При H-перетворенні сімейство K1 зручно називати замінюваним, K2 –замінником, а K' –результатом H-перетворення.
H-перетворення дозволяють одержувати нові (з точністю до ізоморфізму) КР з відомих КР. Уперше цей факт доведено у [34, 36], де знайдено кілька нових (на той час) КР порядку 21, використавши 3H-перетворення.
Зауважимо, що в [39] метод H-перетворень та H-інваріант успішно застосовано для побудови неізоморфних КР порядку 27.
Подальший пошук нових КР порядку 21 здійснювався за допомогою програми, яка будує 4H-перетворення відомих КР порядку 21. При цьому вихідним матеріалом служили КР з уже згадуваних списків MPR, MR та T. У роботі [31] наведено список одержаних внаслідок цього дослідження КР; кількість відомих КР порядку 21 досягла 115.
У 1996 р. Дейтер, Франек та Роса (Dejter I.J., Franek F., Rosa A.) опублікували статтю, у якій повідомили про існування одержаного ними списку КР порядку 21, що вміщує 192 неізоморфних КР ( ми називаємо його DFR-списком).
Штейнеровою системою трійок порядку n, коротко ШСТ(n), називають таке сімейство трійок елементів n-множини E, коли кожні два елементи множини E зустрічаються разом в одній і тільки одній з цих трійок. Якщо трійки ШСТ(n) можна розбити на паралельні класи, які складають КР порядку n, то таку ШСТ(n) називають кіркмановою.
Зауважмо, що кіркманова система трійок S може допускати кілька КР. Сімейство всіх КР, які допускає штейнерова система трійок S, називають гніздом NEST(S) системи S. Члени гнізда не зобов'язані бути ізоморфними. Це створює нову можливість поповнення списку неізоморфних КР.
Другий метод із вищезгадих якраз і використовує можливість будувати для даної ШСТ порядку 21 гніздо; при цьому особливо цікаві випадки, коли гніздо налічує кілька неізоморфних КР.
За допомогою програми гніздування реалізовано схему пошуку нових КР порядку 21, в якій органічно поєднуються метод H-перетворень і метод гніздування. Ця схема дозволила одержати 31 новий КР порядку 21, чим обгрунтовано наступну теорему.
Теорема 8.1. N(21)і146.
Останнім часом (як повідомив дисертанту А.Роса) значного прогресу у переліку KP порядку 21 досяг Ч.Колбурн. За попередніми відомостями, він одержав список КР порядку 21, який вміщує більше як 63000 (!) неізоморфних КР, що мають нетривіальні автоморфізми. Хоча публікацій про ці результати ще нема, схоже на те, що застосовувалися методи, засновані на ідеї циклічності. Поєднання цих методів з методом H-перетворень та методом гніздування може привести до подальшого прогресу у розв'язуванні цієї задачі.
У підрозділі 8.7 викладено мінімальні D-розклади повних графів. Назвемо D-графом граф, зв'язні компоненти якого –трикутники. Розклади графу Kn на компоненти, ізоморфні D-графам, називаються D-розкладами порядку n. Кількість компонент у D-розкладі називають розміром D-розкладу.
Трикутники, які приймають участь у компонентах D-розкладу порядку n, складають ШСТ порядку n. Ми будемо також говорити, що D-розклад є D-розкладом цієї ШСТ.
Відома необхідна і достатня умова nє1 або 3(mod 6) існування ШСТ порядку n є одночасно необхідною і достатньою для існування D-розкладів.
D-розклад належить до типу a=(a1,a2,...,ab), якщо він вміщує точно at Dt-компонент для кожного t=1,2,...,b. Неважко встановити, що необхідною умовою існування D-розкладу типу a є
= n(n–)/6. (8.1)
Розв'язки a рівняння (8.1) з невід'ємними цілими компонентами називаються допустимими типами.
Вектор a реалізовний, якщо D-розклад типу a існує. Вектор a реалізовний даною ШСТ, якщо існує D-розклад цієї ШСТ типу a.
Позначимо найменший розмір D-розкладу порядку n через g(n), і називатимемо D-розклад порядку n з розміром g(n) мінімальним. Якщо D-розклади порядку n не існують, то покладаємо g(n)= Ґ.
Очевидно, що необхідною умовою того, щоб вектор a=(a1,...,ab) був реалізований мінімальним D-розкладом, є умова
a1+...+ab=g(n).
Далі називатимемо можливими типами допустимі вектори, які задовольняють цю умову.
ШСТ порядку n називається мінімально D-розкладною, якщо вона допускає мінімальний D-розклад.
У щойно визначених поняттях дисертант формулює ряд задач, які чекають своїх дослідників. Ось одна з них.
Задача 8.5. Для кожного n знайти повний список неізоморфних мінімальних D-розкладів порядку n.
У дисертації наведено повний розв'язок задачі 8.5 у випадку n=13, а саме доведено наступну теорему.
Теорема 8.3. З точністю до ізоморфізму, існує точно 446 мінімальних D-розкладів графа K13. Обидві ШСТ порядку 13 є мінімально реалізовними.
Табл.8.1 вміщує кількісну інформацію про повний список мінімальних D-розкладів порядку 13.
Цей результат одержано за допомогою алгоритму та відповідного програмного забезпечення, створеного та описаного в підрозділі 8.10.
У задачі про реалізовність типів мінімальними D-розкладами доведено наступну теорему.
Теорема 8.8. Для n=12t+7 тип (a1,...,a(n+1)/2), де всі ai=0, крім a(n–)/6+1=1, a(n+1)/2–=1, a(n+1)/2=(n+1)/2–, реалізований системою трійок Ханані.
У кінці розділу 8 висловлена наступна
Гіпотеза 8.9. Для n=6t+1, tі3, всі можливі типи реалізовні мінімальними D-розкладами.
Доведено справедливість цієї гіпотези при значеннях n=13, n=19 та n=25. Крім того, запропоновано метод побудови нових мінімальних D-розкладів з наявних за допомогою перерозподілів трійок у наявних D-розкладах. Цей метод аналогічний методу H-перетворень і може стати у пригоді при доведенні гіпотези 8.9.
У наступному розділі 9 "Пентагональні розклади повних графів" мова йде про перелік неізоморфних пентагональних розкладів повних графів та пентагональних упаковок.
Пентагональною упаковкою у граф Kn називають сімейство 5-циклів графа Kn (компонент упаковки), жодні дві з яких не мають спільних ребер. Пентагональну упаковку називають r-упаковкою, якщо вона складається з r компонент.
Граф, що являє собою об'єднання всіх компонент упаковки, будемо називати розвалом упаковки. Носієм упаковки називається множина вершин, які мають у розвалі степінь, відмінну від нуля. Потужність носія називають порядком упаковки.
Пентагональна упаковка в граф Kn називається пентагональним розкладом графа Kn, якщо кожне ребро графа Kn міститься у деякій компоненті цієї упаковки.
Відомо, що пентагональний розклад графа Kn існує тоді і тільки тоді, коли
n є 1 чи 5(mod 10). (9.1)
Очевидно, що при n=5 існує, з точністю до ізоморфізму, єдиний пентагональний розклад. Наступним значенням, що задовольняє умові (9.1), є n=11.
Досі не розв'язана наступна задача: побудувати повний список попарно неізоморфних пентагональних розкладів графа K11. У підрозділах 9.1 та 9.2 зроблено крок до розв'язання цієї задачі –побудовано повні канонічні списки неізоморфных пентагональних 2- та 3-упаковок у граф K11. А саме, доведена
Теорема 9.1. Існують, з точністю до ізоморфізму, точно 288 пентагональних 3-упаковок у граф K11.
У дисертації наведено (табл.9.1) повний список неізоморфних пентагональних 2-упаковок у граф K11; його потужність дорівнює 8.
Будемо говорити, що дві компоненти деякої пентагональної упаковки переплітаються по типу i, якщо ці дві компоненти складають 2-упаковку, ізоморфну упаковці, що має номер i у табл. 9.1 (1ЈiЈ8). Визначені таким чином типи переплетення 5-циклів зручні для розрізнення упаковок.
У підрозділі 9.3 формулюється кілька перспективних задач стосовно пентагональних розкладів.
Пентагональну упаковку будемо називати i-гомогенною, якщо кожні дві нетотожні компоненти цієї упаковки переплітаються по типу i.
У підрозділі 9.4 доведено ряд тверджень про існування та перелік i-гомогенних упаковок.
Теорема 9.5. Розмір 3-гомогенної пентагональної упаковки не більше 3.
Теорема 9.6. Розмір 4-гомогенної пентагональної упаковки не більше 6.
Теорема 9.8. З точністю до ізоморфізму, існують точно 86 5-гомогенних пентагональних упаковок у граф K11, які мають розмір 4.
Представлено повний список неізоморфних 5-гомогенних пентагональних 4-упаковок у граф K11.
Теорема 9.15. Якщо можливий 5-гомогенний пентагональний розклад графа Kn, то n=11.
Підсумок результатів, одержаних стосовно існування та переліку гомогенних пентагональних упаковок у граф K11, наведено в табл. 9.3. На перетині i-го рядка та r-го стовпця цієї таблиці стоїть кількість неізоморфних i-гомогенних пентагональних r-упаковок у граф K11. У цій таблиці є кілька ще не заповнених місць.
У дисертації представлено повні списки всіх перелічених табл. 9.3 гомогенних упаковок. Зокрема, найбільший з них –список 5-гомогенних пентагональних 5-упаковок графа K11 вміщено у додатку Н.
Описано інваріанти, придатні як для розрізнення, так і для ототожнення гомогенних пентагональних упаковок.
Теорема 9.17. З точністю до ізоморфізму 5-гомогенні розклади графа K11 вичерпуються двома розкладами:
(A) 12345 13678 1489a 16a5b 17b29 24b68,
a7 2693a 359b8 374ab 46579;
(B) 12345 13678 1498a 165b9 172ab 24796,
a68 2938b 359a7 3a46b 4857b.
Теорема 9.18. Групи автоморфізмів розкладів (A), (B) циклічні і вміщують по 55 автоморфізмів кожна.
Пентагональний розклад графа Kn вміщує підрозклад порядку p(p<n), якщо компоненти, які цілком належать деякому підграфу Kp графа Kn, складають пентагональний розклад графа Kp.
В підрозділі 9.8 започатковане розв'язування задачі переліку пентагональних розкладів графа K11 з підрозкладами порядку 5. А саме, доведено наступну допоміжну теорему, яка відігрбє ключову роль у розв'язанні цієї задачі.
Теорема 9.19. Якщо пентагональний розклад графа K11 вміщує підрозклад порядку 5, то цей підрозклад єдиний.
Підрозділ 9.9 вміщує результати у задачі знаходження максимальних розмірів розкладів та бірозкладів повних графів на цикли. (Kn,l,C)-розкладом називається таке сімейство циклів графа Kn, що кожне ребро графа Kn належить точно l різним циклам. Теореми 9.20 та 9.21 встановлюють значення G(Kn,l,C) –найбільшого розміру (Kn,l,C)-розкладу.
Теорема 9.20. G(Kn,1,C)= якщо n непарне,
G(Kn,1,C)= якщо n парне.
Теорема 9.21. Має місце формула
G(Kn,2,C)= nі3.
Заключний розділ 10 називається "Розклади на кубічні компоненти", і стосується, в основному, побудови та переліку кубічних розкладів графа K10.
Для заданого кубічного розкладу графа Kn (n>6) введено вектор (a4,a6,..., an), де ai –кількість компонентів порядку i у розкладі. Цей вектор названо типом розкладу. Легко зрозуміти, що для розкладу має місце співвідношення
S(3i/2)ai=n(n–)/2,
де сума береться по всіх парних iі4. Внаслідок очевидних спрощень одержуємо таку необхідну умову існування кубічних розкладів графа Kn:
2a4+3a6+...+(n/2)an=n(n–1)/6. (10.2)
Окремо розглядається випадок n=10. Для цього значення n умова (10.2) приймає вигляд
2a4+3a6+4a8+5a10=15. (10.3)
Розв'язуючи рівняння (10.3) щодо a4, a6, a8, a10 у невід'ємних цілих числах, одержуємо всі можливі типи кубічних розкладів графа K10. Виявилося, що існує 14 можливих типів; всі вони представлені в табл. 10.1.
Співвідношення (10.3) та табл. 10.1 вперше опубліковані дисертантом у [27].
Тепер задачу можна конкретизувати так: для будь-якого типу з табл. 10.1 з'ясувати, чи існують розклади графа K10 цього типу, і якщо існують –провести їх перелік з точністю до ізоморфізму. Ця задача повністю розв'язана в підрозділі 10.2 у випадку типу, який у табл.10.1 має номер 4, а в підрозділі 10.3 і подальших задача повністю розв'язана для типу 1.
Стосовно розкладів типу 1 одержано результати, які кількісно представлені у табл.10.3 та у наступній теоремі. Символом r(n,m,k) позначено кількість неізоморфних розкладів графа Kn на ізоморфні регулярні графи степеня k порядку m.
Теорема 10.2. r(10,10,3) = 122.
Список 122 кубічних факторизацій графа K10 з попарно ізоморфними компонентами вміщений у додатку Л.
Таблиця 10.1.
Можливі типи розкладів графа K10 на кубічні компоненти
1. 0 0 0 3 2. 0 1 3 0 3. 0 2 1 1 4. 0 5 0 0 5. 1 0 2 1 6. 1 1 0 2 7. 1 3 1 0
. 2 1 2 0 9. 2 2 0 1 10. 3 0 1 1 11. 3 3 0 0 12. 4 1 1 0 13. 5 0 0 1 14. 6 1 0 0
Раніше було відомо [45], що не існує розкладів розглядуваного типу, всі компоненти якого ізоморфні графу Петерсена G19; те ж саме було відомо про розклади з компонентами, ізоморфними призмі D5=G15. З табл.10.3 видно, що для графів G2, G14, G17 та G2O також має місце неіснування кубічних факторизацій графа K10.
У 1997 р. П.Адамс, Д.Бриант та А.Кодкар (Adams P., Bryant D.E., Khodkar A.) довели існування кубічних розкладів графа K10 для 15 кубічних графів порядку 10 та неіснування таких розкладів для 6 інших кубічних графів порядку 10. Але цей результат безпосередньо випливає з табл. 10.3, яку дисертант опублікував роком раніше [45].
У підрозділі 10.4 описується теоретичне підгрунтя згаданого результату, зокрема вводиться інваріант, названий орбітантом. Він успішно застосовувався для розрізнення/ототожнення факторизацій та для знаходження їх груп автоморфізмів.
Методами, подібними до застосовуваних вище, проведено перелік тих кубічних факторизацій графа K10, серед компонент яких точно дві неізоморфні. Кількісні результати цього дослідження наведені у табл.10.3, яка вперше з'явилася у [32]. Cимволом D(a,b,b) позначено список тих кубічних факторизацій графа K10, у яких одна компонента ізоморфна графу Ga, а дві інші ізоморфні графу Gb. У табл.10.5 на перетині рядка a та стовпця b стоїть потужність списку D(a,b,b), a діагональні місця заповнені згідно з табл.10.3. Самі списки D(a,b,b) (вірніше, ті з них, які не порожні) представлені у додатку А. Вперше цей список опублікований у [33]. Основний результат описаного дослідження коротко формулюється у вигляді наступної теореми.
Теорема 10.3. З точністю до ізоморфізму, існують точно 2316 кубічних факторизацій графа K10, серед компонент кожної з яких рівно дві ізоморфні.
Подальші зусилля було спрямовано на перелік тих кубічних факторизацій графа K10, у яких не зустрічається двох ізоморфних компонент. У роботі [40] опубліковано кількісні результати –таблицю, у якій a b c * m означає, що список D(a,b,c) складається з m факторизацій. Тут D(a,b,c) - список неізоморфних кубічних факторизацій графа K10, у яких перша компонента ізоморфна графу Ga, друга –Gb , а третя –графу Gc, де Gx –граф, який має номер x у відомому списку неізоморфних кубічних графів Бараєва А.М. та Фараджева І.А. У роботі [40] також представлено канонічні списки D(a,b,c), 1Јa<b<cЈ21, структура яких така ж, як і в списках додатку А. Обсяг роботи [40] –більше, ніж 180 машинописних сторінок; тому вона не наведена у дисертації.
Коротко результат переліку кубічних факторизацій графа K10 з попарно неізоморфними компонентами можна сформулювати так.
Теорема 10.5. З точністю до ізоморфізму, існують 6726 кубічних факторизацій графа K10, у кожній з яких немає двох ізоморфних компонент.
Об'єднання щойно описаних результатів дає наступну теорему. Символом R(n,m,k) позначено кількість неізоморфних розкладів графа Kn на регулярні графи порядку m степеня k.
Теорема 10.6. R(10,10,3)=9164.
У 1981 році А.Коціг (Kotzig A.) довів, що для кожного натурального d граф Km може бути розкладений на компоненти, ізоморфні d-вимірному кубу Qd, якщо m є 1(mod dЧ2d). Звідси випливає, що граф K25 розкладається на куби Q3. У дисертації Дж. Картер ( Carter J.E., 1989) доведено, що існують розклади графа K25 на підграфи, ізоморфні g, для будь-якого 8-вершинного кубічного графа g.
В підрозділах 10.6 –.8 увагу зосереджено на переліку циклічних розкладів графа K25 на куби Q3. Основний результат, одержаний у [52], формулюється в наступній теоремі.
Теорема 10.7. Існують точно 244 попарно неізоморфних циклічних розкладів графа K25 на куби.
Для його отримання застосовано класичний алгоритм побудови циклічних розкладів повного графа на ізоморфні компоненти та розроблені дисертантом специфічні способи уникнення дублікатів у одержаних списках. Для розрізнення/ ототожнення виділено 15 типів взаєморозміщення двох кубів, на основі яких побудовано особливий інваріант T досить великої розрізнюючої сили. Для цього інваріанту побудовано відповідні субінваріанти, що забезпечило повне розрізнення неізоморфів у результуючому списку ( додаток С до дисертації).
Поставлена задача про перелік (циклічних) розкладів графа K25 на графи, ізоморфні графу g, для довільного 8-вершинного кубічного графа g, g№Q3.
Результати переліку максимальних розкладів повних графів на кубічні компоненти викладено в підрозділі 10.10. Це передусім результати переліку блок-схем B(n,4,1), які отримані за допомогою зріз-перетворень відомих блок-схем. Установлено наступний ряд тверджень.
Теорема 10.8. Існує 16 неізоморфних схем B(25,4,1) з нетривіальними групами автоморфізмів; отже, кількість неізоморфних B(25,4,1) не менша, ніж 16.
Теорема 10.9. Існують не менше, ніж 16 неізоморфних схем B(28,4,1).
Теорема 10.10. Існують не менше, як 3 неізоморфні B(37,4,1).
Теорема 10.11. Існують не менше, як 4 неізоморфні B(40,4,1).
Метод зріз-перетворень є одним з проявів методу рівновагових перетворень розкладів. Показано значні потенціальні можливості цього методу у побудові нових блок-схем.
ВИСНОВКИ
У дисертації викладено результати, одержані дисертантом у розв'язуванні задач побудови та переліку розкладів графів, здебільшого повних, на підграфи, взяті з певних класів графів. Теоретичні досягнення та практичні результати, які отримав дисертант:
. Знайдено способи представлення графів (зокрема, шаблонне представлення), зручні для побудови та переліку розкладів графів на підграфи відповідних типів.
. Формалізовано та пристосовано до розв'язування задач розрізнення комбінаторних конфігурацій, зокрема, розкладів, поняття інваріанта. Побудовано низку інваріантів для різних розкладів та проведено їх класифікацію.
. Запропоновано кілька методів побудови розкладів повних графів, зокрема, метод H-перетворень кіркманових розкладів та метод гніздування, біциклічний та напівобертовий методи побудови деревних факторизацій.
4. Знайдено ряд необхідних та ряд достатніх умов існування деревних факторизацій повних графів.
. Повністю вирішене питання про існування T-факторизацій порядку 10; задача існування T-факторизацій порядку 14 розв'язана для всіх дерев, за винятком 20.
6. Введено поняття розщеплення вектора степенів вершин дерева і на його основі одержано необхідні умови існування біциклічних T-факторизацій.
. Запропоновано алгоритми переліку T-факторизацій, напівобертових та біциклічних T-факторизацій, за допомогою яких одержано ряд результатів переліку для порядків 10, 12 та 14.
. Одержано необхідні умови існування та ряд результатів переліку різнокомпонентних деревних факторизацій.
. Започатковано перелік W4-розкладів графа K17 отриманням вичерпних списків неізоморфних W4-упаковок рангів rЈ4 у граф K17.
10. Одержано вичерпні списки розкладів повних графів на k-зірки для ряду значень параметрів.
. Розв'язана задача Роса побудови спектра розмірів максимальних досконалих 1-факторизацій для порядку 12.
. Побудовано вичерпний список досконалих 1-факторизацій порядку 12.
. Повністю розв'язана проблема переліку мінімальних D-розкладів порядку 13.
. Сформульовано задачу про реалізовність типів мінімальних D-розкладів, одержано загальний результат про реалізовність, висунуто правдоподібну гіпотезу про повний розв'язок цієї задачі та запропоновано новий метод перерозподілів трійок, який може стати у пригоді при доведенні цієї гіпотези.
. Розпочато перелік пентагональних розкладів графа K11: перелічено пентагональні упаковки рангів rЈ3; перераховано гомогенні пентагональні упаковки для ряду значень параметрів; перераховано гомогенні пентагональні розклади графа K11.
16. Проведено повний перелік розкладів графа K10 на кубічні графи порядку 6 та повний перелік кубічних факторизацій графа K10.
Основні положення дисертації опубліковані в таких працях:
. Возняк В.В., Петренюк А.Я. Об одном алгоритме перечисления систем групп пар // Комбинаторный анализ. - 1972. - Вып.2. –С. 38–.
2. Донец A.Г., Петренюк A.Я., О перечислении разнокомпонентных древесных разложений // Теория оптимальных решений. - Киев: Ин-т кибернетики им. В.М.Глушкова НАН Украины, 2000. –С. - 70–.
. Дурач Д., Приходькина А.И., Петренюк А.Я. О деревьях и древесных факторизациях // Научные труды академии. –. - Вып.5. –Ч. 1. –Гос. летная академия Украины. –С. 34 -39.
4. Petrenjuk A.J., Zemljansky A. Enumerating cyclic 3-cube decompositions of K25 // J. of Combin. Math. and Comb. Computing. –. –42. - Р. 88 - 96.
. Курек Х.Є., Петренюк А.Я. О покрытии графов звездами // Теория графов. –Киев: Ин-т математики, УССР, 1977. –С. 145–.
. Петренюк А.Я. Минимальные D-разложения полных графов // Теория оптимальных решений. - Киев: Ин-т кибернетики им. В.М.Глушкова НАН Украины, 2001. - С. 43-49.
. Петренюк А.Я. До перелiку розкладiв графа K17 на колеса W4. // Науковi записки. Сер. Фiзико-мат. науки. –Кiровоград, 1998. - Вип. XII. -
С. 56–.
. Петренюк А.Я. Древесные факторизации полных графов: существование, построение, перечисление // Материалы 7 Междунар. семинара "Дискретная математика и ее приложения". - М., 2001. –С. - 26–.
. Petrenjuk L.P., Petrenjuk A.J. Decomposition of the complete graph K(8) into smallest dragons // Світогляд. –. –Вип. 1. - С. 101 –.
10. Петренюк А.Я., Необхідні умови існування Т-факторизацій // Доп. НАН України. - 2002. –№ 3. –С. 71-73.
. Петренюк А.Я. Каталог неизоморфных 5-гомогенных пентагональных 5-упаковок // Кибернетика и системный анализ. - 2001. –№ 5. –С. 102–
. Петренюк А.Я. О построении неизоморфных блок-схем с помощью изографических наборов блоков / Кировоградский ин-т с.-х. машиностр. - Кировоград, 1983. –с. - Рус. - Деп. в УкрНИИНТИ 30.08.89, N 985- Ук- 83.
. Петренюк А.Я. О преобразованиях, приводящих к неизоморфным тактическим конфигурациям // Материалы Всесоюз. семинара по дискретной математике и ее приложениям. –М. Изд-во Моск. ун-та, 1986. –С. 81–.
. Петренюк А.Я. О спектре максимальных совершенных семейств 1-факторов в полных графах малых порядков // Оптимизация и ее приложения. –Киев: Ин-т кибернетики им. В.М.Глушкова НАН Украины, 1997. –С. 60–.
. Петренюк А.Я. О существовании бициклических T-факторизаций порядка 14 // Научные труды академии. –. - Вып.4. –Ч. 1. –Гос. летная академия Украины. –С. 206 -212.
. Петренюк А.Я. О цилиндрических разложениях графов // Комбинаторный анализ. –. - Вып.7. –С. 46–.
17. Petrenjuk L.P., Petrenjuk A.J. Weighted blocking designs and their transformations // Світогляд. - 1996. - Вип.3. –С. 45–
18. Петренюк А.Я. Об одном семействе инвариантов и новых неизоморфных схемах B(28,4,1) / Кировоград. ин-т с.-х. машиностр. - Кировоград, 1984. – 10 с. - Деп. в УкрНИИНТИ, N 530 - Ук-Д84.
. Петренюк А.Я. Обобщения преобразований, приводящих к неизоморфным тактическим конфигурациям / Кировоград. ин-т с.-х. машиностр. - Кировоград, 1984. – 9 с. - Рус. - Деп. в УкрНИИНТИ 23.09.89, N 1560 - Ук-Д84.
. Петренюк А.Я. Ознаки неізоморфності систем трійок Штейнера // Укр. мат. журн. –. - 24, N 6. –С. 772 –.
. Петренюк А.Я., Перечень совершенных 1-факторизаций порядка 12 ранга 4 / Гос. летная академия Украины. –Кировоград, 1997. –с. –Рус. - Деп. в ГНТБ Украины 04.04.97, N 289 - Ук97.
. Петренюк А.Я. Перечисление малых неизоморфных пентагональных упаковок // Кибернетика и системный анализ. –. - № 6. –С. 72 –.
. Петренюк А.Я. Перечисление неизоморфных гомогенных пентагональных упаковок // Теория оптимальных решений. –Киев: Ин-т кибернетики им. В.М.Глушкова НАН Украины, 1999. –С. 57 –.
. Петренюк А.Я. Півобертові деревні факторизації повних графів // Укр. мат. журнал. - 2001. - 53, №5. –С. 710 –.
. Петренюк А.Я. Применение инвариантов в комбинаторных исследованиях // Вопросы кибернетики: Тр. семинара по комбинаторной математике. - М.: Сов. радио, 1973. –С.129 –.
. Петренюк А.Я. Про перелік кубічних розкладів повного графу K(10) // П'ята міжнар. наук. конф. ім. акад. М.Кравчука (16-18 травня 1996 р., Київ): Тези доп. - К., 1996. –С.332.
27. Petrenjuk L.P., Petrenjuk A.J. An enumeration method for nonisomorphic combinatorial designs // Annals of Discrete Mathematics. –. –№ 7. –
Р. 265–.
28. Петренюк А.Я., Непорожнев И.П. Конструктивное перечисление систем групп пар и оглавленные системы троек Штейнера // Комбинаторный анализ. –М.: Изд-во Моск. ун-та. –. - Вып.2. –С. 17–; 1974. - Вып.3. - С. 28–; 1980. - Вып.4. –С. 99–.
. Петренюк А.Я., Черновол А.С. Преобразование звездных покрытий графов посредством обращения звездных циклов / Кировоград. ин-т с.-х. машиностр. - Кировоград, 1983. –с. - Деп. в УкрНИИНТИ 22.06.83, N 558 - Ук-Д83.
. Петренюк А.Я., Шнитер В.Ю. О строении графа H-преобразований 1-факторизаций порядка 10 // j-преобразования и комбинаторные свойства графов. - Препр. - Ин-т математики АН УССР. –К., 1978. –С. 34–.
. Петренюк В.І., Петренюк А.Я. Про новi Кiркмановi системи трiйок порядку 21 // Научные труды академии. - 1995. - Вып.1. –Гос. летная академия Украины. –С. 134 - 145.
. Петренюк Л.П., Петренюк А.Я. К перечислению неизоморфных разложений графа K(10) на кубические факторы // Научные труды академии. –. - Вып.1. –Гос. летная академия Украины. –С. 115 - 117.
. Петренюк Л.П., Петренюк А.Я. К перечислению неизоморфных разложений графа K(10) на кубические факторы // Научные труды академии. –. - Гос. летная академия Украины. –С. 69. –Рус. - Деп. в ГНТБ Украины 24.10.96, N 2125 - Ук96.
. Петренюк Л.П., Петренюк А.Я. Метод H-преобразований в применении к киркмановым разрешениям штейнеровых систем / Кировоград. ин-т с.-х. машиностр. - Кировоград, 1983. - 26 c. - Деп. в УкрНИИНТИ 01.09.83, N 994 - УкД83.
. Петренюк Л.П., Петренюк А.Я. О конструктивном перечислении 12-вершинных кубических графов // Комбинаторный анализ. - 1974.- Вып.3.–С. 72–(испр. в вып. 4).
. Петренюк Л.П., Петренюк А.Я. О неизоморфных B(25,4,1) и KST(21) / Кировоград. ин-т с.-х. машиностр. - Кировоград, 1983. - 9 с. - Деп. в УкрНИИНТИ 06.01.84, N 84 - УкД84.
. Петренюк Л.П., Петренюк А.Я. Перечень десятивершинных однородных графов степени 4 // Вопросы кибернетики. –. - Вып. 15: Тр. II Всесоюз. семинара по комбинаторной математике. –М., Сов. радио. –С. 71–.
. Петренюк Л.П., Петренюк А.Я. О перечислении совершенных 1-факторизаций полных графов // Кибернетика. –. –№ 1. –С. 6 –.
. Петренюк Л.П., Петренюк А.Я. О семействе неизоморфных киркмановых разрешений одной штейнеровой системы троек // Комбинаторно-алгебраические методы в прикладной математике. - Горький, 1983. - Вып.5. –С. 176 –.
. Петренюк Л.П., Петренюк А.Я. Перечисление кубических факторизаций графа K(1O) с попарно неизоморфными компонентами / Гос. летная академия Украины.–Кировоград, 1997.–с. - Деп. в ГНТБ Украины 18.06.97, N 377-Ук97.
. Петренюк Л.П., Петренюк А.Я. Перечисление совершенных 1-факторизаций кубических и полных графов порядка 14 / Кировоградский ин-т с.-х. машиностр. - Кировоград, 1982. –с. - Деп.в УкрНИИНТИ 22.07.82, N 3712, Ук-Д82.
. Петренюк Л.П., Петренюк А.Я. Построение некоторых классов кубических графов и неизоморфность киркмановых систем троек // Комбинаторный анализ. –. - Вып.4. –С. 73 –.
. Petrenjuk A.J. A generalization of Kirkman triple systems / Державна льотна академія України. –Кіровоград, 2001. –c. –Деп. в ДНТБ України 03.12.2001, N 184, Ук2001.
44. Petrenjuk A.J. Decomposing K(1O) into cubic graphs of order 6 // Bull. Inst. Combin. Appl. - 1994. –№ 12. –С. 9 –.
. Petrenjuk A.J. Enumerating decompositions of K(10) into isomorphic cubic factors // Свiтогляд. –. - Вип.2. - Кіровоград, 1996. –С. 52 –.
. Petrenjuk A.J. Enumeration of minimal tree decompositions of complete graphs // J.of Combin. Math. and Combin. Computing. - 1992. - № 12 –С. 197 – 199.
. Petrenjuk A.J. Every tree from T[14,4] admits a T-factorization / Державна льотна академія України.–Кіровоград, 2001.–с. - Деп. в ДНТБ України 23.06.2001, N 147, Ук2001.
48. Petrenjuk A.J. Nonisomorphic double star factorizations of order 12 // Наук. пр. академії: Під ред. Р.М.Макарова.–Кіровоград, Вид-во Державна льотна академія України, 1999. –Вип. 4, ч. 1. –С. 212 –.
49. Petrenjuk A.J. On the constructive enumeration of packings and coverings of index 1 // Discrete Mathematics. - 1989. - 77. –С. 237 –.
. Petrenjuk A.J. On tree factorizations of K10 // J.of Combin. Math. and Combin. Computing. - 2002. - 41. –Р. 193 - 202.
. Petrenjuk A.J. On bicyclic tree factorizability over T[14,5] / Державна льотна академія України.- Кіровоград, 2001.- 18 c. –Деп. в ДНТБ України 23.06.2001, N 148 - Ук2001.
Петренюк А.Я. Екстремальні розклади повних графів: існування, перелік. - Рукопис.
Дисертація на здобуття наукового ступеня доктора фізико-математичних наук зі спеціальності 01.05.01 - теоретичні основи інформатики та кібернетики, Інститут кібернетики ім.В.М.Глушкова НАН України, Київ, 2002.
Захищаються результати, опубліковані у 51 праці і присвячені задачам існування та переліку, з точністю до ізоморфізму, розкладів повних графів на компоненти, взяті з певних класів графів. Запропоновано кілька методів побудови таких розкладів –метод Н-перетворень, метод гніздування, біциклічний та напівобертовий. Одержано нові умови існування
Т-факторизацій повних графів, повністю розв'язана задача про існування
T-факторизацій порядку 10 та задача про існування біциклічних T-факторизацій порядку 14. Отримані результати переліку T-факторизацій, 1-факторизацій та розкладів повних графів на колеса, на зірки, на митри, на 5-цикли, на
D-фактори, на кубічні графи. Зокрема, проведено повний перелік кубічних факторизацій графа K10.
Ключові слова: розклад графа, ізоморфізм, існування, перелік, розщеп -лення, біциклічність, T-факторизація, інваріант, розрізнення, ототожнення, колесо, зірка, пентагональний розклад, кіркманів розклад, мінімальний D-розклад, Н-перетворення, гніздування, перерозподіл трійок, реалізовність типів, кубічна факторизація.
Петренюк А.Я. Экстремальные разложения полных графов: существование, перечисление. –Рукопись.
Диссертация на соискание ученой степени доктора физико-математических наук по специальности 01.05.01 - теоретические основы информатики и кибернетики, Институт кибернетики им. В.М.Глушкова НАН Украины, Киев, 2002.
Защищаются результаты, опубликованные в 51 работе и посвященные задачам существования и перечисления, с точностью до изоморфизма, разложений полных графов на компоненты, взятые из заданніх классов графов. Предложено несколько методов построения таких разложений.Получены новые условия существования T-факторизаций полных графов, полностью решена задача о существовании T-факторизаций порядка 10 и задача о существовании бициклических T-факторизаций порядка 14. Получен ряд результатов перечисления T-факторизаций, 1-факторизаций и разложений полных графов на колеса, на звезды, на митры, на 5-циклы, на D-факторы и на кубические графы. В частности, проведено полное перечисление кубических факторизаций графа K10.
Ключевые слова: разложение графа, изоморфизм, существование, перечисление, расщепление, бицикличность, T-факторизация, инвариант, различение, колесо, звезда, пентагональное разложение, киркманово разложе -ние, минимальное D-разложение, H-преобразование, перераспределение троек, реализуемость типов, кубическая факторизация.
Petrenjuk A.J. Extremal decompositions of complete graphs: existence and enumeration. –Manuscript.
Doctor of Sciences thesis (physics and mathematics), specialization 01.05.01 –theoretical foundations of informatics and cybernetics. V.M.Glushkov Institute of Cybernetics of the National Academy of Sciences of Ukraine, Kyiv, 2002.
The results are defending published in 51 scientific works investigating the existence and enumeration problems for decompositions of complete graphs into subgraphs taken from some graph classes. The main results are the following.
1. The ways of the representation of graphs are found (in particular, the pattern representation) which are convenient for the construction and enumeration of the decomposition of graphs into subgraphs of certain kinds.
. The concept of invariants is formalized and adapted for distinguishing combinatorial cоnfigurations, and the graph decompositios specifically. The succession of the invariants for different decompositions is constructed, and the classification of invariants is carrying out.
. Several methods for construction of the graph decompositions are proposed, namely the method of H-transformations and the nesting method for Kirkman decompositions , bicyclical and half-rotational methods for constructing tree decompositions.
. Some new necessary and some new sufficient conditions for the existence of tree factorizations are found.
. The question about the existence of T-factorizations of order 10 is completely answered and the existence problem for T-factorizations of order 14 is solved for all but 20 trees.
. The concept of splittings of the vertex degree vector of the tree is іntroduced, and it became a foundation of the necessary conditions for the existence of bicyclic T-factorizations.
. An algorithm for enumeration of T-factorizations, half-rotational and bicyclic T-factorizatoins is proposed, and with its aid a number of enumeration results is obtained for the orders 10, 12 and 14.
. Some necessary conditions for the existence and a number of enumeration results are obtained for tree factorizations consisting of nonisomorphic trees.
. The emumeration of W4-decompositions of the graph is started by obtaining of the complete lists of nonisomorphic W4-packings of size rЈ4 into the graph K17.
. The exhaustive lists of the k-star decompositions are constructed for some complete graphs.
. The solution is done for A.Rosa's problem concerning spectra of the sizes of maximal perfect 1-factorizations for orders 10 and 12.
. The exhaustive lists of perfect 1-factorizations of order 12 is obtained.
. The enumeration of minimal D-decompositions of order 13 is completely done.
. The problem on realizability of types of minimal D-decompositions is formulated, a general result in the problem is obtained, a plausible conjecture about the complete solution of the problem is advanced and a new method of redistribution of triples is proposed which can be of use in solving the problem.
. The enumeration of pentagon decompositions of K11 is initiated; namely, the pentagon packings of sizes rЈ3, the homogeneous pentagon packings for some values of parameters and homogeneous pentagon decompositions of K11 are enumerated.
. The complete enumeration of the decompositions of K10 into cubic graphs of order 6 and the complete enumeration of the cubic factorizations of K10 are carried out. The existence and enumeration problems for different types of cubic decompositions of K10 are formulated.
Key words: graph decomposition, isomorphism, existence, enumeration, T-factorization, invariant, distinguishing, wheel, star, pentagon decomposition, Kirkman decomposition, minimal D-decomposition, H-transformation, nesting, redistribution of triples, types realizability, cubic factorization.