Статья посвящена анализу важных частных случаев задачи коммивояжера и задачи Штейнера. Обе эти задачи являются NP-трудными даже в метрическом случае, т. е. для графов, у которых функция стоимости ребер удовлетворяет неравенству треугольника. Более строгим ограничением является <b>усиленное</b> неравенство треугольника: $ \forall x,y,z \in X \quad c(x,z) \leq \max\{c(x,y), c(y,z)\} $. Метрические функции, удовлетворяющие такому условию, называются <b>ультраметрическими</b>. В статье на основе анализа графов с ультраметрической функцией стоимости ребер разработан алгоритм, позволяющий построить для такого графа гамильтонов цикл минимальной стоимости за время <nobr>$O(n^2)$</nobr>, где <nobr>$n$</nobr> — число вершин графа. Для задачи Штейнера показано, что при ультраметрической функции стоимости ребер минимальное дерево Штейнера содержит только терминальные вершины и поэтому также может быть построено за полиномиальное время как минимальное остовное дерево на подграфе исходного графа.
ультраметрическая функция, усиленное неравенство треугольника, задача коммивояжера, дерево штейнера, полиномиальные алгоритмы