Содержание
ВВЕДЕНИЕ 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 Исходные данные
Найти остовное дерево минимальной длины для графа, заданного следующей матрицей весов:
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
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
Вы можете убедиться в качестве данной работы. Часть курсовой представлена ниже: