Запропоновано узагальнену математичну модель, сформульовану у вигляді векторної задачі покриття графа типовими підграфами. Обгрунтовано оцінки обчислювальної складності різних класів досліджуваної задачі покриття графа типовими підграфами, знайдено новий P-важкий клас в оптимізаційній постановці, установлено важкорозв'язуваність усіх класів однорідних векторних задач покриття графа типовими підграфами у випадку наявності у векторній цільовій функції (ВЦФ) двох критеріїв вигляду MAXSUM. Виділено нові поліноміально розв'язувані підкласи одно- та двокритеріальних задач у класах P-важких та важкорозв'язуваних задач покриття графа зірками та ланцюгами. Розроблено відповідні алгоритми їх розв'язання, обгрунтовано поліноміальні оцінки їх обчислювальної складності. Розвинуто теорію алгоритмів з оцінками стосовно одно- та багатокритеріальних задач покриття графа ланцюгами. Для багатокритеріальної задачі покриття графа ланцюгами двох типів побудовано малотрудомісткий алгоритм та доведено теореми, що встановлюють достатні умови, за яких цей алгоритм майже завжди гарантує знаходження розв'язку, точного за критеріями вагового вигляду та асимптотично точного за критерієм кількості ланцюгів у покритті. У однокритеріальному випадку доведено статистичну ефективність алгоритмів. Побудовано малотрудомісткий алгоритм градієнтного типу для оптимізаційної задачі покриття графа скінченою множиною ланцюгів та доведено теореми про достатні умови його асимптотичної точності. Досліджено випадок задачі покриття зірками з інтервальними даними. Здійснено зведення інтервальної задачі до двокритеріальної з обгрунтуванням оцінки обчислювальної складності. Доведено, що розглянуті задачі покриття графа ланцюгами й зірками з інтервальними вагами не можуть бути розв'язуваними за допомогою алгоритмів лінійної згортки критеріїв.

  Скачати повний текст