Курсовые, дипломные и контрольные работы.
Готовые и на заказ

Анализ и оценка эффективности алгоритма Краскала – Курсовая

ДисциплинаТехнические
Тип работыКурсовые
Количество страниц18
Год сдачи2017
Номер работы1442

О работе

Предмет – Алгоритм и структура данных. Отчет + программа (Паскаль)

Содержание

ВВЕДЕНИЕ 3
1 ПОСТАНОВКА ЗАДАЧИ 4
1.1 Задание 4
1.2 Исходные данные 4
1.3 Описание алгоритма Краскала 4
1.4 Сложность алгоритма 5
2 РАЗРАБОТКА ПРОЕКТА 6
2.1 Идея решения 6
2.2 Решение 8
2.3 Блок схема программной реализации алгоритма 10
3 ЛИСТИНГ ПРОГРАММНОГО КОДА 14
4 СКРИНШОТЫ РАБОТЫ ПРОГРАММЫ 16
ЗАКЛЮЧЕНИЕ 17
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 18

ВВЕДЕНИЕ
Минимальным остовным деревом (МОД) связного взвешенного графа называется его связный подграф, состоящий из всех вершин исходного дерева и некоторых его ребер, причем сумма весов ребер максимально возможная. Если исходный граф несвязен, то описываемую ниже процедуру можно применять поочередно к каждой его компоненте связности, получая тем самым минимальные остовные деревья для этих компонент.
Задача о нахождении минимального остовного дерева часто встречается в подобной постановке: есть n городов, через которые можно проложить маршрут так, чтобы можно было добраться из любого города в любой другой (напрямую или через другие города). Требуется найти такой маршрут, чтобы стоимость проезда была максимальной.
..............................................................................

1 ПОСТАНОВКА ЗАДАЧИ
1.1 Задание
Пусть имеется связный неориентированный граф G, на ребрах которого задана весовая функция c (e). Связный подграф графа G, являющийся деревом и содержащий все его вершины, называют покрывающим деревом (spanning-tree) этого графа (иногда используют термин остовное дерево или остов). Весом остовного дерева будем считать сумму весов всех его ребер. Тогда возникает задача о нахождении максимального покрывающего дерева, т.е. такого, что его вес наибольший, либо равен весу любого из покрывающих деревьев для данного графа. Будем обозначать наибольшее покрывающее дерево графа G как MAX (G).

1.2 Исходные данные
Найти остовное дерево минимальной длины для графа, заданного следующей матрицей весов:
2.[1]

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
1. Кpистофидес, H. Теоpия гpафов. Алгоритмический подход. М. "Миp", 1978
2. Бондарев В.М., Рублинецкий В.И., Качко Е.Г. Основпрограммирования / Харьков: Фолио; Ростов на Дону: Феникс, 1997. – 368 .
3. Кормен Т. Х., Лейзерсон Ч. И., Ривест Р. Л., Штайн К. Алгоритмы: построение и анализ, 2-е изд. — М.: Вильямс, 2005. — 1296 с.
4. http://www.algolist.manual.ru/links/
5. http://www.devel.vcity.ru/library.tmpl?05344_article_id=8
6. http://www.ergeal.ru/txt/archive/cs/discra/index.htm
7. Hечепуpенко, М.И. Алгоpитмы и пpогpаммы pешения задач на гpафах и сетях. – Hовосибиpск: Hаука, 1990
8. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. – М.: Бином, 2000. – 960с.
9. Липский В. Комбинаторика для программистов: Пер. с польск. – М.: Мир, 1988. – 213 с.
10. Оре О. Теория графов. – М.: Наука, 1980

Вы можете убедиться в качестве данной работы. Часть курсовой представлена ниже:

analiz-i-ocenka-effektivnosti-algoritma-kraskala--kursovaya

analiz-i-ocenka-effektivnosti-algoritma-kraskala--kursovaya 2

690 р.
и получить 100 бонусных руб.
Только проверенные работы
Бонусы
при покупке
Работы по любому предмету на заказ
Способы оплаты: