Анотація до роботи:

Протасова К.Д., Розкладання графів - рукопис.

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.01 – теоретичні основи інформатики і кібернетики - Київський національний університет імені Тараса Шевченка, Київ, 2006.

В дисертаційній роботі введено нове поняття калейдоскопічного графу, що є природнім узагальненням кодів Хемінга. Вказано два загальні способи побудови калейдоскопічних графів на основі графів Келі груп.

Як один із загальних способів розкладання графів, знайдено кілька достатніх ознак квазігамільтонових графів. Зокрема, доведено що будь-який реберний граф скінченного зв'язного графа є квазігамільтоновим, а також раундебаут граф будь-якого скінченного зв'язного графа теж квазігамільтонів. Ці результати не покриваються жодною з існуючих ознак квазігамільтоновості.

Розроблено нові методи розкладання графів: індуктивний, розкладання за незалежними множинами, розкладання за кістяками, трансверсальний спосіб, розкладання за узагальненими циклами та променями.

Доведено теорему про врівноважені розбиття графів.

Знайдено деякі необхідні та деякі достатні умови калейдоскопічності графів, вказано два способи побудови калейдоскопічних графів з використанням графів Келі груп.

Досліджено будову вільної калейдоскопічної групи та вільної калейдо-скопічної напівгрупи, описано групу калейдоскопічних автоморфізмів Хемінгових графів.

Доведено квазігамільтоновість реберних графів, графів розв'язок, графів інтервалів, графів Келі скінченних груп, описано квазігамільтонові дерева.

Введено нові поняття: врівноважені розбиття графів, калейдоскопічні графи.