Search academic texts

Information × Registration Number 0412U002923, Candidate dissertation Status к.ф.-м.н. Date 24-05-2012 popup.evolution o Title Development of Methods and Algorithms of Solving Complete Graphs T-Factorization Problems Author Mironenko Oksana Vasilivna, popup.head Donets Georgiy Afanasyevitsh popup.opponent Шаріфов Фірдовсі Ахун-огли popup.opponent Ємець Єлизавета Михайлівна Description В дисертаційній роботі досліджуються питання розкладу повних графів на дерева. Розглядаються методи і алгоритми розв'язування задач Т-факторизації повних графів, застосування теоретичних основ до побудови і переліку деяких сімейств неізоморфних розкладів. Вперше розглянуто різнорозмірні деревні розклади згідно їх первісної класифікації: зіркові, ланцюгові, кометні, та розклади на подвійні зірки. Продовжено дослідження, в основу яких покладено задачу Л. Байнеке: з'ясувати, для яких дерев існують T-факторизації парного порядку. Для кожного дерева T порядку 10 вказано можливі типи T-факторизацій, і для більшості з цих типів подано реалізуючі T-факторизації, побудовані за допомогою комп'ютера. Результати досліджень табульовано. Знайдено необхідні умови існування T-факторизацій та відповідні достатні умови їх неіснування, які узагальнюють ідею Л. Байнеке про те, що наявність у дереві вершин досить високих степенів часто призводить до неіснування T-факторизацій. Доведено неіснування T-факторизацій серією регулярних дерев, деякими ярусно-регулярними деревами та 3-гусеничної факторизації. Побудовано базові компоненти симетричних дерев непарних порядків, які повністю підтверджують гіпотезу про існування деревної факторизації відповідних повних графів. Результати табульовано. Введено поняття паралельного перенесення міждолевого ребра. Створено алгоритм побудови всіх базових компонент біциклічної Т- факторизації для довільних значень n=4l+2. Розроблено методику, основану на лишках по модулю та використанні паралельного перенесення міждолевого ребра, яка дозволяє за допомогою низки логічних міркувань та необхідних побудов, прорахувати всі можливі Т-факторизації для повних графів Кn з великою кількістю вершин. Застосування методики практично показано на прикладах повних графів порядку 10 та 14, які мають вершину з найвищим степенем відповідно 5 та 7. Registration Date 2012-05-24 popup.nrat_date 2020-04-04 Close