Синтез графа смежности с минимальным числом ребер: формализация алгоритма и анализ его корректности

В статье рассматриваются вопросы, связанные с одним из этапов машинного обучения алгебраических байесовских сетей (АБС). Рассматриваются проблемы в организации формальных моделей знаний с неопределенностью на примере алгебраических байесовских сетей (АБС).
Целью работы является построение вторичной структуры АБС в виде графа смежности. На граф накладывается дополнительное ограничение: минимизировать число ребер. В статье приведен алгоритм построения минимального графа смежности, а также анализ его корректности.
В постановке задачи дается определение графа смежности, формализуются входные данные, ограничения и цель, вводится понятие веса вершины. Вводятся понятия нагрузки ребра, а также универсального множества нагрузок. Вводится определение мощности веса, задается порядок на множестве весов вершин.
Приведен листинг алгоритма построения минимального графа смежности (АПМГС), описания используемых обозначений, а также построчный разбор АПМГС.
Сформулирован ряд утверждений, доказывающих корректность АПМГС. Доказывается, что АПМГС строит граф смежности. Затем доказывается минимальность построенного графа.
Установлено, что алгоритм по заданной первичной структуре АБС строит вторичную в виде графа смежности с минимальным числом ребер корректно.