Алгебраические байесовские сети: проверка магистральной связности

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