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

Індекс рубрикатора НБУВ: З810.2

Рубрики:

Теорія мереж

Шифр НБУВ: РА343485 Пошук видання у каталогах НБУВ 
Повний текст  Автореферати дисертацій 

---

Додаткова інформація про автора(ів) публікації:
(cписок формується автоматично, до списку можуть бути включені персоналії з подібними іменами або однофамільці)

• Шаріфов Фірдовсі Ахун-огли (фізико-математичні науки)

  Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"