T-неприводимые расширения для многоугольных орграфов

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