Категория:Сводимые и регуляризуемые графы

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

Класс сводимых и регуляризуемых графов играет чрезвычайно важную роль в программировании в силу того, что программа, управляющий граф которой принадлежит этому классу, допускает применение более эффективных алгоритмов анализа и оптимизации. Так, задача нахождения минимального множества дуг, удаление которых разрывает все контуры в орграфе, является NP-трудной для графа общего вида, но имеет полиномиальную сложность для сводимых графов.