4.3.2. Построение графа структуры зависимостей по корреляционной матрице.

Как установлено выше, граф G структуры зависимостей нормального вектора строго тяжелее любого дерева, построенного на тех же вершинах и отличающегося от G хотя бы одним ребром ненулевого веса. Поэтому задача нахождения G при известной корреляционной матрице сводится к задаче отыскания среди деревьев, которые можно построить на вершинах с весами, определяемыми дерева наибольшего веса. В теории графов последняя задача решается с помощью алгоритма Крускала [1341, носящего итерационный характер и заключающегося в следующем:

сначала матрица W пополняется весами, отвечающими 0— координате

далее в качестве первого шага выбирается любое из ребер, имеющих в наибольший вес; на шаге — любое из ребер наивысшего веса среди оставшихся и не образующих цикла с ранее выбранными ребрами.

Поскольку всего имеется вершина, в алгоритме Крускала делается шагов, и на каждом из них выбирается ребро, не образующее цикла с ранее выбранными, то в результате его применения возникает дерево (см. теорему 4.1). Работу алгоритма Крускала удобно проиллюстрировать на примере построения дерева для однородной цепи Маркова, описанной в п. 4.1.1. На каждом из первых шагов выбираются ребра вида , на последнем шаге — ребро вида , так как все остальные ребра образуют цикл с ранее выбранными. Если отбросить связь нулевого веса, то получаем дерево, изображенное на рис. 4.1.

Если известна только выборочная корреляционная матрица R, то по ней может быть построена выборочная весовая функция . Результат применения к ней алгоритма Крускала обозначим G. Так как при росте объема выборки (по вероятности), то G также сходится к G в том смысле, что

(4.18)