Шаріфов Ф. А. Методи та алгоритми розв' язування задач синтезу мереж зі складною структурою

Дисертація присвячена задачам синтезу мереж з різними обмеженнями на проектованій мережі. У термінах ізоморфізму графів зформульована загальна задача синтезу надійних мереж. Розроблений строго поліноміальний алгоритм для рішення задачі знаходження різних шляхів між джерелом і стоком при виході з ладу одиничного ребра мережі. Запропоновано метод для знаходження точного рішення оцінних задач для загальної задачі розміщення. Доведено, що існує цілочисельне оптимальне рішення задачі атаки для гіперграфів, а також поліноміальна розв'язність задачі атаки для мережі зі зваженими вершинами. Запропонований строго поліноміальний алгоритм рішення найпростішої багатоетапної задачі розміщення на деревоподібної мережі. Доведено поліноміальну розв'язність задачі синтезу мережі які не співпадають, циклами на орієнтованій мережі у випадку, коли різниця ваг довільного ребра дводольного графа можна представити як алгебраїчну суму ваг кінцевих його вершин. Алгоритми знаходження рішень ряду задач, розглянутих у роботі, були використані при рішенні реальних задач. Ключові слова: синтез мереж, ізоморфізм графів, гіперграф, субмодулярна функція, поліматроід, строго поліноміальні алгоритми.