Минимальное остовное дерево. Минимальное вершинное покрытие.

ВВЕДЕНИЕ
Минимальное остовное дерево (МОД) связного взвешенного графа - это его связный подграф, который состоит из всех вершин исходного графа и некоторых его ребер. Сумма весов ребер является наименьшей из возможных. Нахождение такого дерева во многих прикладных задачах, решение этой задачи позволяет минимизировать затраты на подключение компонентов, которые являются вершиной графа. Примером такого рода задач может быть поиск способа соединить города дорогами таким образом, чтобы их общая протяженность или стоимость были сведены к минимуму. Кроме того, задача поиска наименьшего дерева появляется в компьютерной сети, то есть в протоколе STP, который устраняет циклы в сети при выборе наилучшей скорости соединения. Актуальность данной работы заключается в том, что появляются новые области задачи поиска MST, и по графу результатов трудно определить, какой алгоритм наилучшим образом решит эту задачу.
Задача поиска наименьшего связующего дерева обычно решается в аналогичной обстановке: предположим, есть n городов, которые необходимо соединить дорогой, чтобы вы могли добраться из любого города в любой другой город (напрямую или через другие города). Разрешено строить дороги между обозначенными парами городов, и стоимость строительства каждой такой дороги известна. Необходимо решить, какие дороги необходимо построить, чтобы минимизировать общую стоимость строительства.
Эта задача может быть выражена в теории графов как задача нахождения наименьшего связующего дерева в графе с вершиной, представляющей город. Ребра представляют собой парные города, где могут быть проложены прямые дороги, а вес ребер равен стоимости строительства соответствующих дорог. Сетевая модель используется для отображения процесса выполнения проекта в системе SPM и управления им.
Цель исследования: рассмотреть минимальное остовное дерево и минимальное вершинное покрытие.
Исходя из цели сформулированы следующие задачи исследования:
 рассмотреть теорию графов;
 изучить содержание теории остовного дерева;
 рассмотреть минимальное вершинное покрытие;
 изложить алгоритм решения задач.
Объектом исследования выступают сетевые модели планирования.
Предмет исследования – метод минимального остовного дерева и минимального вершинного покрытия.
Теоретической и методологической основой для написания данной работы послужили научные труды российских и зарубежных исследователей в различных научных областях. Структура курсовой работы определяется целями, задачами и характером объекта и темы исследования. Эта работа включает введение, основную часть, заключение и библиографический список


1. МИНИМАЛЬНОЕ ОСТОВНОЕ ДЕРЕВО
1.1. Описание теории графов
В переводе с греческого граф – «Я пишу», «я описываю». В современном мире граф описывает отношения. И наоборот, любые отношения можно описать как графы. Теория графов - это обширный раздел дискретной математики, в котором систематически изучаются свойства графов. Теория графов широко используется в решении экономических и управленческих задач, в программировании, химии, проектировании и изучении электрических цепей, коммуникации, психологии, социологии, лингвистике и других областях. Для чего создаются графы: для отображения взаимосвязей на множествах. По сути, графы помогают визуально представить все виды сложных взаимодействий: аэропорты и рейсы между ними, различные отделы в компании, молекулы в веществе. Теория графов – это область дискретной математики, особенностью которой является геометрический подход к изучению объектов. Теория графов сейчас находится на пике своего развития. Его часто называют топологией (поскольку во многих случаях он учитывает только топологические свойства графов), но он пересекается с различными областями теории множеств, комбинаторной математики, алгебры, геометрии, теории матриц, теории игр, математической логики и многих других математических дисциплин. Ключевым объектом теории графов является граф, а также его обобщение [10].
Рассмотрим пример.
Пусть набор A = {a1, a2, ... кому} - это набор людей, и каждый элемент отображается как точка. Количество B = {b1, b2, ... bm} - множество полос (прямых, дуг или линий). В наборе А мы представляем отношения между людьми из этого набора. Мы строим граф из точек и пучков. Ленты соединяют пары людей, которые знают друг друга.
Количество знакомых одного человека может отличаться от числа других людей, некоторые из них могут быть даже незнакомы (такими элементами являются точки, которые не связаны ни с одним другим). Так появился граф:

Рисунок 1.1 – Граф

В этом случае точки являются вершинами графа, а полосы - ребрами графа. Теория графов не учитывает специфическую природу множеств A и B. Существует множество различных задач, в которых можно временно забыть о содержимом множеств и их элементах. Эта особенность не влияет на ход решения проблемы. Например, вопрос в задании таков: возможно ли добраться из точки А в точку Е, если вы перемещаетесь только по соединительным линиям точки. Когда проблема решена, мы получаем решение, которое применимо ко всему содержимому, которое можно смоделировать как граф.
Неудивительно, что теория графов является одним из самых популярных инструментов для создания искусственного интеллекта: ведь искусственный интеллект может обсуждать с человеком отношения, географию или музыку, решать различные проблемы. Граф - это система объектов произвольной природы (вершин) и пучков (ребер), которые соединяют несколько пар этих объектов.
Пусть V - это (непустой) набор вершин, v ∈ V—элементы являются вершинами. Граф G = G(V) со многими вершинами V Есть семейство пар вида: e = (a, b), где a, b ∈ V указывают, какие вершины