У термінах ізоморфізму графів зформульована загальна задача синтезу надійних мереж. Показано, що ряд відомих задач на графах, таких як задача комівояжера, задача Штейнера, задача синтезу деревоподібних мереж, задача синтезу міцних мереж з різними обмеженнями на зв’язність проектованої мережі, гра Шеннона другого типу на графах . Зформульовано достатні і необхідні умови існування рішення загальної задачі синтезу надійних мереж. Доведено поліноміальну можливість розв'язання деяких класів задач на допустимість. Показано, що оцінні задачі, отримані шляхом лінійної релаксації загальної задачі синтезу надійних мереж, належать до числа – важких задач. Доведено, якщо в заданому графі можна знайти підграф, ізоморфний іншому заданому графові, за поліноміальний час, то оцінні задачі належать класові . Досліджена структура граней багатогранника обмежень задачі синтезу надійних мереж. Показано, що при використанні розрізної нерівності як додаткове обмеження можна зменшити величину розриву двоїстості. Розроблені ефективні алгоритми рішення оцінних задач, що реалізовані мовою C++. Проведено експериментальне дослідження ефективності запропонованого алгоритму на тестових і реальних задачах. Розроблений строго поліноміальний алгоритм для рішення задачі знаходження різних шляхів між джерелом і стоком при виході з ладу одиничного ребра мережі. Розглянуто загальну задачу розміщення, що узагальнює такі відомі задачі як найпростіша задача розміщення, задача розміщення з обмеженнями на потужності підприємств і деяких інших класів задач стандартизації й уніфікації. Запропоновано метод для знаходження точного рішення оцінних задач для загальної задачі розміщення. Запропонований строго поліноміальний алгоритм для знаходження міні-мальних розрізів на параметричній мережі, і показано, що при використанні цього алгоритму для рішення підзадач, виникаючих на кожній ітерації методу рішення загальної задачі розміщення, зменшується трудомісткість ітерації цього методу. Для рішення загальної задачі розміщення на практиці запропонований алгоритм знаходження наближеного її рішення, що реалізований мовою ПЛ-1, за допомогою якого вирішені реальні задачі. Розроблено алгоритми рішення задачі синтезу мережі з заданими числами шляхів і втратами. Ці алгоритми реалізовані мовою C і використані при рішенні задачі проектування інтегрованих цифрових мереж зв'язку (вторинної мережі). Показано, що задача знаходження мінімального розрізу на неорієнтованій мережі, що відокремлює джерело і стік, еквівалентна задачі знаходження мінімуму субмодулярної функції різниць, що є поліматроїдною та модулярною функціями. Запропоновано новий алгоритм типу гріді (greedy) для знаходження мінімального розрізу. Доведено, що існує цілочисельне оптимальне рішення задачі атаки для гіперграфів, а також поліноміальна можливість розв'язання задачі атаки для мережі зі зваженими вершинами. Запропоновано алгоритм синтезу мережі з використанням значень розрізної функції. Доведено, що після лінійної релаксації найпростішої багатоетапної задачі розміщення отримана задача має цілочисельне оптимальне рішення на деревоподібній мережі. Запропонований строго поліноміальний алгоритм її рішення, коли пункти розміщення довільного рівня, а також пункти постачальників розташовані на вершинах деревоподібної мережі. Показано, що задача синтезу мережі не співпадаючих і які не перетинаються, циклів на орієнтованій мережі з двома вагами її дуг зводиться до задачі знаходження двох зроблених паро сполучень, які не перетинаються ребрами, із сумарною мінімальною вагою на повному дводольному графі з двома вагами його ребер. Доведено поліноміальну можливість розв'язання цієї задачі у випадку, коли різницю ваг довільного ребра дводольного графа можна представити як алгебраїчну суму ваг кінцевих його вершин. | 