Графовые модели. Остов минимального веса

    Дисциплина: Разное
    Тип работы: Курсовая
    Тема: Графовые модели. Остов минимального веса

    Аннотация
    Данный курсовой проект выполнен на тему «Графовые модели. Остов минимального веса». Проект содержит разработку программной модели поиска остова минимального веса во взвешенном
    неориентированном графе с выводом промежуточных результатов и их иллюстрацией.
    Данный документ содержит 23 листа, 17 рисунков и 1 таблицы.
    Содержание
    Введение......................................................................................4
    1 Постановка задачи...................................................................5
    1.1Основные понятия теории графов……………….....5
    1.2 Представление графов...............................................5
    1.3 Алгоритм нахождения остова минимального
    веса во взвешенном графе……………………..…….....6
    2 Инструментальные программные средства..........................7
    2.1 Обоснование выбора инструментальных
    средств…………...………………………………...……7
    3 Блок-схема алгоритма моделирования................................10
    3.1 Описание блок-схемы алгоритма задачи
    моделирования……………………………………..….10
    4 Операционная среда моделирования………………...........13
    4.1 Описание операционной среды моделирования...13
    4.2 Аппаратная среда моделирования…………………14
    4.3 Руководство оператора……………………………..14
    4.4 Лицензионное соглашение…………………………17
    5 Контрольная задача моделирования………………………19
    Заключение
    ................................................................................26
    Литература
    .................................................................................27
    Приложение А: листинг программы
    .......................................28
    Приложение Б: исходные файлы
    .............................................39
    Введение
    В настоящее время исследования в областях, традиционно относящихся к математике, занимают все более заметное место. Проблема выбора оптимального варианта решения относится к
    числу наиболее актуальных технико-экономиче­ских проблем.
    Развитие теории графов в основном обязано большому числу всевозмож­ных приложений. По-видимому, из всех математических объектов графы зани­мают одно из первых мест в качестве
    формальных моделей реальных систем.
    Графы нашли применение практически во всех отраслях научных знаний: физике, биологии, химии, математике, истории, лингвистике, социальных науках, технике и т.п. Наибольшей
    популярностью теоретико-графовые модели исполь­зуются при исследовании коммуникационных сетей, систем информатики, хими­ческих и генетических структур, электрических цепей и других
    систем сетевой структуры.
    Цель курсового проекта заключается в закреплении практических умений и навыков в нахождении остова минимального веса с помощью алгоритма Крас­кала, в разработке программы на
    языке
    Delphi
    для аналитического и графического
    решений нашей поставленной задачи. Использование компьютерных технологий
    для решения данных задач сокращает усилия и время человека, а это не мало важно в настоящие время.
    В курсовом проекте в разделе «Постановка задачи» рассматривается тео­ретический материал по теме «Графовые модели. Остов минимального веса», в разделе «Алгоритм нахождения»
    рассматриваются алгоритмы нахождения «Ос­това минимального веса», в разделе «Инструментальные программные средства» выбираются инструментальные средства для разработки программного
    продукта, в разделе «Операционная среда моделирования» определятся интерфейс про­граммного продукта, в разделе «Контрольная задача моделирования» формулиру­ется задача для ее решения
    вручную и с помощью программного продукта.
    1 Постановка задачи моделирования
    1.1Основные понятия теории графов
    Графом называется алгоритмическая модель, состоящая из множества вершин (узлов) v и соединяющих их ребер e.
    Ребро - неупорядоченная пара вер­шин графа.
    Ребра называются смежными, если они имеют общую вершину. Вершины называются смежными, если есть ребро их соединяющее. Ребро, которое соеди­няет вершины, называется инцидентным
    этим вершинам, а вершины – инцидент­ные этому ребру.
    Граф G’(v’,e’) является остовом минимального веса графа G(v,e), если v’=v и e’ – есть подмножество ребер минимального веса и количества, соединяющих все вершины. Остовом
    минимального веса может являться сеть минимальной стоимости, в матрице соединения которой cij=cji.
    Граф G= называется ориентированным (орграфом), если найдется дуга (a,b)
    R такая, что (b,a)
    Если же отношение R симметрично, то есть из (a,b)
    R следует (b,a)
    R, то граф G называется неориентированным (неорграфом).
    Связный граф - граф, у которого для любых двух различных вершин суще­ствует цепь (последовательность смежных вершин), соединяющая их.
    Для решения данной задачи моделирования будет использован неориенти­рованный связный
    граф.
    1.2 Представление графов
    Существует четыре базовых представлений графов в памяти машины: мат­рица инцидентности, матрица смежности, матрица списков смежности и связан­ные списки смежности. Они
    различаются скоростью выполнения операций над элементами представления и объемом занимаемой памяти.
    Для решения поставленной задачи моделирования больше всего подходит представление графов в памяти машины в виде матрицы смежности, а именно матрица весов.
    Матрица смежности
    - матрица размером
    Матрица смежности является симметричной и достаточно просто мо­жет использоваться для ввода и обработки на
    ЭВМ. Для случая взвешенного графа вместо 1 используется значение весовой функции, и такая матрица называ­ется матрицей весов. В поставленной задаче будем использовать матрицу
    весов.
    1.3 Алгоритм нахождения остова минимального
    веса во взвешенном графе
    Для нахождения остова минимального веса с помощью метода Краскала нужно выполнить следующие шаги:
    1.Помечают вершину начала построения остова. Среди ребер, инци­дентных помеченной вершине, находят ребро
    минимального веса для остова. По­мечают новую вершину, инцидентную этому ребру. Вершина новая, если к ней ранее не обращались.
    2.Смотрят, все ли вершины помечены. Если да, то заканчивают по­иск, если нет, то переходят к шагу 3.
    3.Среди ребер, инцидентных помеченным вершинам, за исключением ребер остова и ребер, образующих в остове
    цикл, находят ребро минимального веса для остова. Помечают новую вершину, инцидентную этому ребру, и перехо­дят к шагу 2.
    4.При изменении вершины начала конфигурация остова минимального веса не измениться. Она может измениться при наличии в графе ребер одинако­вого минимального веса.
    2 Инструментальные программные средства
    2.1 Обоснование выбора инструментальных средств
    При выборе программных средств для разработки программы «Поиск ос­това минимального веса во взвешенном графе» необходимо учитывать
    возмож­ности графического отображения графа и остова в программе, определение моду­лей в программе и связи между ними, оценки развитости аппарата структур и ти­пов
    данных, наличие специальных функций осуществления вычислений, возмож­ность сохранения промежуточных
    результатов. Кроме того, программа должна позволять пользователю возвращаться к предыдущим этапам вычислений и со­хранять выходные данные на жестком диске.
    Учет этих возможностей позволит реализовать основные функции разраба­тываемой программы, сделать ее легкодоступной для использования, предупре­дить возникновение логических
    ошибок, обеспечить надежность программного обеспечения и его модифицируемость.
    Выбор того или иного программного средства определяется как специфи­кой разработки программного обеспечения и его популярностью, так и финансо­выми возможностями
    разработчика.
    В настоящее время наиболее распространенной средой является Delphi.
    Delphi – пакет средств быстрой разработки приложений. К достоинствам относятся удобный интерфейс, высокая скорость работы, большое количество библиотек компонентов,
    эффективность создаваемых программ. Кроме того, строгая типизированность языка Object Pascal позволяет компилятору уже на этапе компиляции обнаружить многие ошибки, а также
    возможность работать с указателями.
    По сравнению с другими системами визуального проектирования среда Delphi проста и эффективна, а написанные с помощью нее программы имеют не­большие размеры и высокую
    производительность. Так же в Delphi существует большая библиотека компонентов (командные кнопки, поля редактирования, пе­реключатели и т.д.). С помощью компонентов обеспечиваются
    удобство интер­фейса, наглядность работы программ, работа по созданию интерфейса сокраща­ется до расстановки компонентов на форме.
    Кроме того, в Delphi имеются развитые средства для работы с графи­ческими возможностями Windows. В стандартном графическом
    интерфейсе Windows основой для рисования служит дескриптор контекста устройства нос и связанные с ним шрифт, перо и кисть. В состав входят объектно-ориентирован­ные надстройки над
    последними, назначением которых является удобный доступ к свойствам инструментов и прозрачная для пользователя обработка всех их из­менений. Поэтому использование класса TCanvas,
    являющегося основой графиче­ской системы Delphi, позволяет выполнить одну из основных функций разрабаты­ваемой программы – наглядное представление графа. Delphi также дает
    возмож­ность использовать традиционный набор функций работы с файлами, унаследо­ванный от Turbo Pascal. Что позволяет сохранять результаты работы программы в файлы на жестком диске.
    Кроме того, в данной среде имеется возможность, на­ряду с обычными массивами, создавать динамические массивы, которые будут играть роль матрицы весов ребер графа. Хотя по большей
    части на представление графа в памяти машины выбор инструментальных средств особого значения не имеет.
    Программа CorelDRAW 11, составляющая основу современного набора программных средств фирмы Corel, была выпущена в августе 2002 г. Она пред­ставляет собой результат
    двенадцатилетней эволюции, обладает удивительной универсальностью и мощностью, будучи в равной степени полезной и в промыш­ленном дизайне, и в разработке рекламной продукции, и в
    подготовке публика­ций, и в создании изображений для web-страниц, также в создании блок-схем ал­горитмов. Несмотря на то, что мировым лидером программ для работы с вектор­ной графикой
    сегодня я...

    Забрать файл

    Похожие материалы:


ПИШЕМ УНИКАЛЬНЫЕ РАБОТЫ
Заказывайте напрямую у исполнителя!


© 2006-2016 Все права защищены