Основные понятия теории графов. Инструментальные программные средства. Блок-схема алгоритма моделирования. Операционная среда моделирования. Контрольная задача моделирования
Введение
В настоящее время исследования в областях, традиционно относящихся к математике, занимают все более заметное место. Проблема выбора оптимального варианта решения относится к числу наиболее актуальных технико-экономических проблем.
Развитие теории графов в основном обязано большому числу всевозможных приложений. По-видимому, из всех математических объектов графы занимают одно из первых мест в качестве формальных моделей реальных систем.
Графы нашли применение практически во всех отраслях научных знаний: физике, биологии, химии, математике, истории, лингвистике, социальных науках, технике и т.п. Наибольшей популярностью теоретико-графовые модели используются при исследовании коммуникационных сетей, систем информатики, химических и генетических структур, электрических цепей и других систем сетевой структуры.
Цель курсового проекта заключается в закреплении практических умений и навыков в нахождении остова минимального веса с помощью алгоритма Краскала, в разработке программы на языке Delphi для аналитического и графического решений нашей поставленной задачи. Использование компьютерных технологий для решения данных задач сокращает усилия и время человека, а это не мало важно в настоящие время.
Возможно вы искали - Курсовая работа: Теорема Силова
В курсовом проекте в разделе «Постановка задачи» рассматривается теоретический материал по теме «Графовые модели. Остов минимального веса», в разделе «Алгоритм нахождения» рассматриваются алгоритмы нахождения «Остова минимального веса», в разделе «Инструментальные программные средства» выбираются инструментальные средства для разработки программного продукта, в разделе «Операционная среда моделирования» определятся интерфейс программного продукта, в разделе «Контрольная задача моделирования» формулируется задача для ее решения вручную и с помощью программного продукта.
1 Постановка задачи моделирования
1.1Основные понятия теории графов
Графом называется алгоритмическая модель, состоящая из множества вершин (узлов) v и соединяющих их ребер e. Ребро - неупорядоченная пара вершин графа.
Ребра называются смежными, если они имеют общую вершину. Вершины называются смежными, если есть ребро их соединяющее. Ребро, которое соединяет вершины, называется инцидентным этим вершинам, а вершины – инцидентные этому ребру.
Похожий материал - Курсовая работа: Цепи Маркова
Граф G’(v’,e’) является остовом минимального веса графа G(v,e), если v’=v и e’ – есть подмножество ребер минимального веса и количества, соединяющих все вершины. Остовом минимального веса может являться сеть минимальной стоимости, в матрице соединения которой cij=cji.
Граф G=<v, e> называется ориентированным (орграфом), если найдется дуга (a,b)ÎR такая, что (b,a)ÏR.
Если же отношение R симметрично, то есть из (a,b)ÎR следует (b,a)ÎR, то граф G называется неориентированным (неорграфом).
Связный граф - граф, у которого для любых двух различных вершин существует цепь (последовательность смежных вершин), соединяющая их.
Для решения данной задачи моделирования будет использован неориентированный связный граф.
Очень интересно - Дипломная работа: Элективный курс по теме: "Сюжетные задачи"
1.2 Представление графов
Существует четыре базовых представлений графов в памяти машины: матрица инцидентности, матрица смежности, матрица списков смежности и связанные списки смежности. Они различаются скоростью выполнения операций над элементами представления и объемом занимаемой памяти.
Для решения поставленной задачи моделирования больше всего подходит представление графов в памяти машины в виде матрицы смежности, а именно матрица весов.
Матрица смежности - матрица размером 
, элементы которой равны 1, если i-я вершина смежна с j-ой, и 0 в противном случае.
Матрица смежности является симметричной и достаточно просто может использоваться для ввода и обработки на ЭВМ. Для случая взвешенного графа вместо 1 используется значение весовой функции, и такая матрица называется матрицей весов. В поставленной задаче будем использовать матрицу весов.
Вам будет интересно - Курсовая работа: Метод релаксации переменных решения СЛАУ
1.3 Алгоритм нахождения остова минимального
веса во взвешенном графе
Для нахождения остова минимального веса с помощью метода Краскала нужно выполнить следующие шаги:
1.Помечают вершину начала построения остова. Среди ребер, инцидентных помеченной вершине, находят ребро минимального веса для остова. Помечают новую вершину, инцидентную этому ребру. Вершина новая, если к ней ранее не обращались.
2.Смотрят, все ли вершины помечены. Если да, то заканчивают поиск, если нет, то переходят к шагу 3.
Похожий материал - Контрольная работа: Моделирование систем
3.Среди ребер, инцидентных помеченным вершинам, за исключением ребер остова и ребер, образующих в остове цикл, находят ребро минимального веса для остова. Помечают новую вершину, инцидентную этому ребру, и переходят к шагу 2.
4.При изменении вершины начала конфигурация остова минимального веса не измениться. Она может измениться при наличии в графе ребер одинакового минимального веса.
2 Инструментальные программные средства
2.1 Обоснование выбора инструментальных средств