Шарифов Ф.А. Методи та алгоритми розв'язування задач синтезу мереж зі складною структурою.- Рукопис. Дисертація на здобуття наукового ступеня доктора фізико-математичних наук за спеціальністю 01.05.01 - теоретичні основи інформатики та кібернетики. -Інститут кібернетики ім. В.М. Глушкова НАН України, Київ, 2006. Дисертація присвячена задачам синтезу мереж з різними обмеженнями на проектованій мережі. У термінах ізоморфізму графів зформульована загальна задача синтезу надійних мереж. Показано, що вона узагальнює задачу комівояжера, задачу Штейнера, задачу синтезу деревоподібних мереж, задачу синтезу міцних мереж з різними обмеженнями на зв'язність мережі, гру Шеннона другого типу на графах і задачу знаходження двозв'язних мереж Штейнера. Оцінні задачі, отримані після її лінійної релаксації, належать до числа NP- важких задач. Якщо у заданому графі, можна знайти підграф, ізоморфний іншому заданому графові за поліноміальний час, то оцінні задачі належать класові Р. Розроблений строго поліноміальний алгоритм для рішення задачі знаходження різних шляхів між джерелом і стоком при виході з ладу одиничного ребра мережі. Запропоновано метод для знаходження точного рішення оцінних задач для загальної задачі розміщення. Доведено, що існує цілочисельне оптимальне рішення задачі атаки для гіперграфів, а також полі-номіальна розв'язність задачі атаки для мережі зі зваженими вершинами. Запропонований строго поліноміальний алгоритм рішення найпростішої багато-етапної задачі розміщення, коли пункти розміщення довільного рівня, пункти постачальників розташовані на вершинах деревоподібної мережі. Доведено поліноміальну розв'язність задачі синтезу мережі які не співпадають і які не перетинаються, циклами на орієнтованій мережі у випадку, коли різниця ваг довільного ребра дводольного графа можна представити як алгебраїчну суму ваг кінцевих його вершин. Алгоритми знаходження рішень ряду задач, розглянутих у роботі, були використані при рішенні реальних задач. Ключові слова: синтез мереж, зв'язність мереж, оптимізація мереж, ізоморфізм графів, гіперграф, розміщення, наближені алгоритми, субмодулярна функція, пара-метрични мережі, поліматроід, строго поліноміальні алгоритми.