Статья: ОЦЕНКИ МОЩНОСТИ МНОЖЕСТВА РЕШЕНИЙ ЗАДАЧ ПОИСКА ПАРЕТО-ОПТИМАЛЬНЫХ ПОДГРАФОВ СВЯЗНОГО ГРАФА

Теория графов составляет существенную часть математических методов, применяемых в экономике для решения самых разнообразных задач. Из этого многообразия следует выделить задачи построения оптимальных подграфов определенного вида в заданном связном графе. В последние десятилетия все более актуальными становятся многокритериальные варианты указанных задач. Однако широкому практическому распространению алгоритмов их решения препятствуют имеющиеся сведения об экспоненциальном росте мощности множества Парето-оптимальных решений с ростом размерности задачи, в результате чего наблюдается преждевременное исчерпание вычислительных ресурсов. Чтобы научиться бороться с этой проблемой, надо получить «хорошую», желательно достижимую оценку мощности множества Парето. Это должно способствовать созданию метода диагностирования неконтролируемого роста числа эффективных решений многокритериальных задач и в дальнейшем помочь в разработке методов борьбы с этим ростом. С практической точки зрения среди эффективных решений наибольший интерес представляет так называемое полное множество альтернатив (ПМА). Поэтому построению оценки мощности именно ПМА посвящена настоящая работа. В результате проведенных исследований были найдены две универсальных оценки мощности ПМА для произвольных подграфов и доказаны теоремы об их корректности. Отдельно были рассмотрены подграфы двух видов - пути и остовные деревья. Для них приведены примеры достижимости одной из оценок в случае двух критериев. Получены асимптотические оценки вычислительной сложности двух алгоритмов поиска Парето-оптимальных путей в графе. Из полученной оценки следует, что при ограниченности значений весов ребер графа эти алгоритмы относятся к классу псевдополиномиальных, т.е. при определенных условиях их вычислительная сложность ниже экспоненциальной.