Читать курсовая по менеджменту: "Различия в распределениях степеней вершин нескольких MST" Страница 1

(Назад) (Cкачать работу)

Введение

В последнее время для анализа фондового рынка используется сетевая модель. Под сетевой моделью понимается полный взвешенный граф, в котором роль вершин исполняют акции, торгующиеся на рынке, а веса ребер высчитываются как коэффициенты корреляций доходностей каждой пары акций. Первой работой в этом направлении является работа Р.Мантегна (1998)[1]. В этой работе на основе сетевой модели обнаружена иерархическая структура. Для обнаружения этой структуры использовано минимальное остовное дерево (MST). MST представляет собой дерево, сумма весов которого минимальна. Каждое такое дерево имеет некоторую топологию.

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

Цель и задачи исследования. Цель - выявить различия в распределениях степеней вершин нескольких MST.

В соответствии с поставленной целью исследования в работе поставлены следующие задачи:

построить и изучить статистическую процедуру проверки многих гипотез о сравнении степеней вершин в MST;

исследовать характеристики процедуры;

применить к реальным данным.

Структура работы: структура работы обусловлена целью и задачами исследования. Работа состоит из введения, двух глав, заключения, списка литературы и приложения.

Глава 1. Теоретическая часть

1.1 Основные понятия теории графов

Граф - упорядоченная пара конечного множества вершин и множества ребер.

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

Связный граф - граф, у которого между двумя любыми вершинами существует просто путь.

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

Для решения задачи о максимальном каркасе известно несколько алгоритмов. Рассмотрим два из них.

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

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

Похожие работы