Анализ циклов в минимальных графах смежности алгебраических байесовских сетей

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