Структурный анализ систем минимальных графов смежности

Цель работы — исследование структуры минимальных графов смежности и их свойств.
Введены понятия: магистральная связность, значимое сужение, доменная вершина, вассал, владение, феод, оммаж, жила, пучок, моноклика, стероклика, граф обязательных ребер. В частности, граф смежности максимальных фрагментов знаний был определен как граф, любые две вершины которого магистрально связны; граф клик был определен как направленный граф сужений максимального графа смежности на веса вершин; жила была определена как граф, построенный на компонентах связности сужения минимального графа смежности на какой-либо вес вершины; пучок был определен как граф, представляющий собой объединение жил.
Предложенная система терминов позволила структурировать и описать исследуемую область и выявить сходства и различия между минимальными графами смежности, построенными на одном и том же множестве максимальных фрагментов знаний.
Доказаны следующие факты: произвольное значимое сужение минимального графа смежности связно; вес ребер любой жилы значимого слова совпадает со словом; в сужении минимального графа смежности множество ребер веса, совпадающего с весом сужения, образуют жилу; все пучки имеют одинаковое число ребер; если любое значимое сужение графа магистрально связно, то граф является графом смежности.
Выведена и доказана структурная теорема о совпадении множества минимальных графов смежности с множеством пучков, которое может быть представлено как декартово произведение множеств подграфов. Это упрощает как представление, так и последовательный синтез всех элементов структуры. На основе указанной теоремы предложена схема алгоритма построения множества минимальных графов смежности и схема улучшенного алгоритма построения минимальных графов смежности. Также на основе теоремы о минимальных графах смежности сделаны выводы о мощности их множества, равной произведению мощностей множеств жил для каждой из клик, и о том, что число ребер в минимальных графах смежности одинаково.
Приведены две схемы алгоритмов построения множества минимальных графов смежности, которые последовательно строят граф клик, множество жил для веса каждой клики, и объединяют эти жилы в множество пучков, таким образом получая множество минимальных графов смежности.
Полученные теоретические результаты создают основу для корректной алгоритмизации глобального машинного обучения (структурного синтеза) алгебраических байесовских сетей. В частности, в работе приведена схема алгоритма, позволяющего для заданного набора максимальных фрагментов знаний построить множество минимальных графов смежности.