Способи розкладання графів, показники розкладності. Дослідження калейдоскопічних графів (регулярні графи скінченного степеня, максимально розкладні відносно сім"ї куль одиничного радіуса), їх алгебраїчні супутники (алейдоскопічні групи і напівгрупи).
Аннотация к работе
НАЦІОНАЛЬНА АКАДЕМІЯ НАУК УКРАЇНИАвтореферат дисертації на здобуття наукового ступеня кандидата фізико-математичних наук Робота виконана на кафедрі інформаційних систем факультету кібернетики Київського національного університету імені Тараса Шевченка. Науковий керівник: Доктор фізико-математичних наук, професор Провотар Олександр Іванович, Київський національний університет імені Тараса Шевченка, завідувач кафедри інформаційних систем факультету кібернетики Офіційні опоненти: Доктор фізико-математичних наук, професор Донець Георгій Панасович Інститут кібернетики НАНУ, завідувачвідділом 110 „Економічна кібернетика” Доктор фізико-математичних наук, професор Банах Тарас Онуфрійович Львівський національний університет імені Івана Франка, кафедра геометрії і топології механіко-математичного факультетуДеякі загальні підходи до дослідження різних математичних конфігурацій (графи, числа, групи і т. д.) розглядалися в роботах О.І. Провотаря. · Розроблено нові методи розкладання графів: індуктивний, розкладання за незалежними множинами, розкладання за кістяками, трансверсальний спосіб, розкладання за узагальненими циклами та променями. Якщо в графі Gr є гамільтонів цикл довжини n і r - дільник числа n, то пофарбувавши вершини цього циклу періодично r-кольорами, ми отримаємо розкладання графу з досить гарними властивостями. За означенням, розбиття P множини вершин графа Gr(V,E) має скінченний індекс, якщо знайдеться невідємне ціле число m, таке що ind P не перевищує m для всіх підмножин P розбиття P. Якщо кожна куля радіуса m в графі Gr(V,E) містить принаймні k вершин, то множину V можна розбити на k підмножин так, що індекс кожної підмножини розбиття не перевищує 3m.· Розроблено нові методи розкладання графів: індуктивний, розкладання за незалежними множинами, розкладання за кістяками, трансверсальний спосіб, розкладання за узагальненими циклами та променями. · Знайдено деякі необхідні та деякі достатні умови калейдоскопічності графів, вказано два способи побудови калейдоскопічних графів з використанням графів Келі груп. · Досліджено будову вільної калейдоскопічної групи та вільної калейдоскопічної напівгрупи, описано групу калейдоскопічних автоморфізмів Хемінгових графів. · Доведено квазігамільтоновість реберних графів, графів розвязок, графів інтервалів, графів Келі скінченних груп, описано квазігамільтонові дерева. · Введено нові поняття: врівноважені розбиття графів, калейдоскопічні графи.