МАТРОИДНОЕ ПРЕДСТАВЛЕНИЕ СЕМЕЙСТВА ГРАФОВ СМЕЖНОСТИ НАД НАБОРОМ ФРАГМЕНТОВ ЗНАНИЙ

2010 , ТОМ 10, НОМЕР 4 ( ИЮЛЬ-АВГУСТ )

ISSN 2226-1494 (print), ISSN 2500-0373 (online)

Меню

Публикации

Главный редактор

НИКИФОРОВ
Владимир Олегович
д.т.н., профессор

Партнеры

УДК 53.084.2

Аннотация

В работе исследуется одна из задач, возникающих при автоматическом обучении баз фрагментов знаний с неопреде-

ленностью, представленных в виде алгебраических байесовских сетей – построение графа смежности как глобальной

(вторичной) структуры сети по ее первичной структуре. Установлено, что семейство графов смежности при задан-

ной первичной структуре сети характеризуется матроидом специального вида, что влечет ряд других заключений:

множества минимальных и нередуцируемых графов смежности совпадают, минимальный граф смежности допускает

построение с помощью жадного алгоритма, число ребер минимального графа смежности выражается через число

ребер максимального графа смежности и ранг матроида.

Ключевые слова:

базы фрагментов знаний, алгебраические байесовские сети, автоматическое обучение, глобальная структура, матроид, граф смежности