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

Abstract

Algebraic Bayesian networks (ABN) are probabilistic-logical graphical models of knowledge systems with uncertainty. ABN probabilistic logical inference algorithms pro-cessing considerably depends on its secondary structure, which is usually represented as a join graph. In particular, the graphs cycles prevent the possibility of the mentioned algorithms application. The goal of the work is to analyze secondary structure cycles and to elucidate necessary and sufficient conditions of the minimal join graph cyclicity. The term of clique graph closed from above is defined as a clique graph with the added root (praclique) , half-sibling cycles are defined as cycles on vassals, non-fraternal half-sibling cycles are defined as such half-sibling cycles where intersection of all the vassals that belong to this cycle is empty. The first theorem on cycles that claims the necessary and sufficient condition of a minimal join graph cyclicity is existence of non-fraternal half-sibling cycles in any clique is formulated and proven. The consequence is that all minimal join graphs built under given algebraic Bayesian network primary structure are either cyclic or acyclic simultaneously