Алгоритм выявления ацикличности первичной структуры алгебраической байесовской сети по ее четвертичной структуре

Алгебраические байесовские сети (АБС) относятся к классу логико-вероятностных графических моделей систем знаний с неопределенностью, которые позволяются использовать интервальные оценки вероятности для представления неопределенности в знаниях. Одним из наиболее важных условий работы АБС является отсутствие циклов в их вторичной структуре. Первичная структура, над которой можно построить ациклическую АБС, называется ациклической. Цель работы — предложить алгоритм выявления ацикличности первичной структуры на основе анализа четвертичной структуры АБС, а также оценка сложности этого алгоритма. В работе сформулирован алгоритм выявления ацикличности, доказана его корректность, оценена его сложность и предложен ряд способов, направленных на ускорение работы этого алгоритма.