Об одном инварианте в задаче разложения недоопределённых данных | Прикладная дискретная математика. 2018. № 39. DOI: 10.17223/20710410/39/2

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