Пошук академічних текстів

Інформація × Реєстраційний номер 0412U002923, Кандидатська дисертація На здобуття к.ф.-м.н. Дата захисту 24-05-2012 Статус Запланована Назва роботи Розробка методів і алгоритмів розв'язування задач Т-факторизації повних графів Здобувач Мироненко Оксана Василівна, Керівник Донець Георгій Панасович Опонент Шаріфов Фірдовсі Ахун-огли Опонент Ємець Єлизавета Михайлівна Опис В дисертаційній роботі досліджуються питання розкладу повних графів на дерева. Розглядаються методи і алгоритми розв'язування задач Т-факторизації повних графів, застосування теоретичних основ до побудови і переліку деяких сімейств неізоморфних розкладів. Вперше розглянуто різнорозмірні деревні розклади згідно їх первісної класифікації: зіркові, ланцюгові, кометні, та розклади на подвійні зірки. Продовжено дослідження, в основу яких покладено задачу Л. Байнеке: з'ясувати, для яких дерев існують T-факторизації парного порядку. Для кожного дерева T порядку 10 вказано можливі типи T-факторизацій, і для більшості з цих типів подано реалізуючі T-факторизації, побудовані за допомогою комп'ютера. Результати досліджень табульовано. Знайдено необхідні умови існування T-факторизацій та відповідні достатні умови їх неіснування, які узагальнюють ідею Л. Байнеке про те, що наявність у дереві вершин досить високих степенів часто призводить до неіснування T-факторизацій. Доведено неіснування T-факторизацій серією регулярних дерев, деякими ярусно-регулярними деревами та 3-гусеничної факторизації. Побудовано базові компоненти симетричних дерев непарних порядків, які повністю підтверджують гіпотезу про існування деревної факторизації відповідних повних графів. Результати табульовано. Введено поняття паралельного перенесення міждолевого ребра. Створено алгоритм побудови всіх базових компонент біциклічної Т- факторизації для довільних значень n=4l+2. Розроблено методику, основану на лишках по модулю та використанні паралельного перенесення міждолевого ребра, яка дозволяє за допомогою низки логічних міркувань та необхідних побудов, прорахувати всі можливі Т-факторизації для повних графів Кn з великою кількістю вершин. Застосування методики практично показано на прикладах повних графів порядку 10 та 14, які мають вершину з найвищим степенем відповідно 5 та 7. Дата реєстрації 2012-05-24 Додано в НРАТ 2020-04-04 Закрити