Достаточные условия минимума для одного класса экстремальных комбинаторных задач

Выделяется класс нелинейных задач комбинаторной оптимизации, в которых поведение функционала на всем комбинаторном множестве определяется его поведением в небольшой окрестности. Это позволяет сформулировать эффективные в вычислительном отношении достаточные условия локального и глобального оптимума. В качестве примера рассматривается задача об оптимальном разбиении графа, для которой даются достаточные условия, трудоемкость проверки которых пропорциональна квадрату числа вершин графа.