Національна академ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 при Інституті кібернетики імені В.М.Глушкова

Національної академії наук України за адресою:

03680 МСП Київ – 187, проспект Академіка Глушкова,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–2002 р.при Кіровоградському педагогічному університеті, на Всесоюзних та Міжнародних семінарах з дискретної математики та її застосувань, які періодично проводились на мехматі Московського державного Університету, на V Міжнародній конференції ім. акад. М.Кравчука. У 2001 р. зроблено пленарну доповідь на VII Міжнародному семінарі з дискретної математики та її застосувань (Москва, МДУ, 29 січня - 2 лютого 2001 р.), доповідь на Українському математичному конгресі та доповідь на теоретичному семінарі в Інституті кібернетики ім. В.М.Глушкова НАН України.

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

Публікації. За темою дисертації опубліковано 51 статтю, з них 22 статті дисертант опублікував одноосібно. У фахових виданнях опубліковано 22 статті.

Структура та обсяг. Дисертація складається із вступу, списку умовних позначень, 10 розділів, 15 додатків та списку використаних джерел, який вміщує 171 найменування. Загальний обсяг – 266 сторінок.

ЗМІСТ РОБОТИ

У вступі до дисертації коротко викладено мету та зміст розділів дисертаційної роботи.

У розділі 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–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–1) є 0(mod 2k); (6.2)

nі2k. (6.3)

Опиcано кілька прийомів побудови зіркових (n,k)-розкладів.

Зірковий (n,k)-розклад графа Kn називається регулярним степеня l, якщо кожна вершина графа Kn є центром точно l зірок цього розкладу. Доведено наступні теореми.

Теорема 6.1. Для існування регулярного зіркового (n,k)-розкладу необхідно і досить, щоб l=(n–1)/(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) підстановок, а у випадку досконалих 1-факторизацій це число дорівнює 2n2(2n–1). В підрозділі 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–1)/6. (8.1)

Розв'язки a рівняння (8.1) з невід'ємними цілими компонентами називаються допустимими типами.

Вектор a реалізовний, якщо D-розклад типу a існує. Вектор a реалізовний даною ШСТ, якщо існує D-розклад цієї ШСТ типу a.

Позначимо найменший розмір D-розкладу порядку n через g(n), і називатимемо D-розклад порядку n з розміром g(n) мінімальним. Якщо D-розклади порядку n не існують,