О мощности множества альтернатив в дискретных многокритериальных задачах

Для многокритериальных постановок известных экстремальных задач (о цепях и паросочетаниях, о коммивояжере и др.) получены нижние оценки мощности паретовского множества и полного множества альтернатив. Дан вероятностный анализ структуры этих множеств и установлено, что эти оценки являются экспоненциальными почти для всех графов.