Мироненко О. В. Розробка методів і алгоритмів розв'язування задач Т-факторизації повних графів

В дисертаційній роботі досліджуються питання розкладу повних графів на дерева. Розглядаються методи і алгоритми розв'язування задач Т-факторизації повних графів, застосування теоретичних основ до побудови і переліку деяких сімейств неізоморфних розкладів. Вперше розглянуто різнорозмірні деревні розклади згідно їх первісної класифікації: зіркові, ланцюгові, кометні, та розклади на подвійні зірки. Продовжено дослідження, в основу яких покладено задачу Л. Байнеке: з'ясувати, для яких дерев існують T-факторизації парного порядку. Для кожного дерева T порядку 10 вказано можливі типи T-факторизацій, і для більшості з цих типів подано реалізуючі T-факторизації, побудовані за допомогою комп'ютера. Результати досліджень табульовано. Знайдено необхідні умови існування T-факторизацій та відповідні достатні умови їх неіснування, які узагальнюють ідею Л. Байнеке про те, що наявність у дереві вершин досить високих степенів часто призводить до неіснування T-факторизацій. Доведено неіснування T-факторизацій серією регулярних дерев, деякими ярусно-регулярними деревами та 3-гусеничної факторизації. Побудовано базові компоненти симетричних дерев непарних порядків, які повністю підтверджують гіпотезу про існування деревної факторизації відповідних повних графів. Результати табульовано. Введено поняття паралельного перенесення міждолевого ребра. Створено алгоритм побудови всіх базових компонент біциклічної Т- факторизації для довільних значень n=4l+2. Розроблено методику, основану на лишках по модулю та використанні паралельного перенесення міждолевого ребра, яка дозволяє за допомогою низки логічних міркувань та необхідних побудов, прорахувати всі можливі Т-факторизації для повних графів Кn з великою кількістю вершин. Застосування методики практично показано на прикладах повних графів порядку 10 та 14, які мають вершину з найвищим степенем відповідно 5 та 7.