Решение задач на тему: Задача Прима-Краскала о телефонной линии

Введение

Многие задачи, с которыми приходится иметь дело в повседневной практике, являются многовариантными. Среди множества возможных вариантов в условиях рыночных отношений приходится отыскивать наилучшие, в некотором смысле при ограничениях, налагаемых на природные, экономические и технологические возможности. В связи с этим возникла необходимость применять для анализа и синтеза экономических ситуаций и систем математические методы и современную вычислительную технику. Такие методы объединяются под общим названием- математическое программирование.

Математическое программирование - область математики, разрабатывающая теорию и численные методы решения многомерных задач.

Как в самой математике, так и в ее приложениях широко используются графы. Теория графов даёт исключительно удобный аппарат для моделирования структурных свойств различных систем и отношений между объектами разной природы, в том числе программных моделей.

Впервые понятие "граф" ввёл в 1936 году венгерский математик Денни Кёниг. Но первая работа по теории графов принадлежала перу великого Леонарда Эйлера и была написана ещё в 1736 году. С помощью графов изображаются схемы различных дорог, линии воздушных сообщений, газопроводов, теплотрасс, электросетей, а также микросхемы, дискретные многошаговые процессы, системы различных бинарных отношений, химические структурные формулы и другие диаграммы и схемы. Применяются графы для решения задач химии, экономики, электротехники и автоматики. Также они широко используются в информатике и строительстве. Без графов сложно анализировать классификации в различных науках.

Теория графов - раздел дискретной математики, особенностью которого является геометрический подход к изучению объектов. Первые задачи теории графов были связаны с решением математических развлекательных задач и головоломок (задача о Кёнингсбергских мостах, задача о расстановке ферзей на шахматной доске, задачи о перевозках, задача о кругосветном путешествии и др.). В общем смысле граф (сеть) G = (V,Е) состоит из конечного, непустого множества m вершин ( m≤1) и конечного множества n неупорядоченных пар элементов [u, v] (n≥0), называемых рёбрами графа G. В строгом определении графом называется такая пара множеств G = {R,V}, где V есть подмножество любого счётного множества, а R - подмножество V*V. Теория графов находит применение, например, в геоинформационных системах (ГИС). Существующие или вновь проектируемые дома, сооружения, кварталы и т. п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередач и т. п. - как рёбра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут.

Графы могут быть представлены в ЭВМ матрицей смежности, инцидентности или матрицей весов. Существуют такие модели задач динамического программирования: модель распределения усилий (инвестиций), модель замены оборудования, поиск кратчайшего пути на графе, задачи календарного планирования, поиск критического пути, вычисление ранних и поздних сроков наступления событий.

Цель курсовой работы - подобрать теоретический материал по рассматриваемой теме, решить задачу о жадном "алгоритме", посвященной нахождению минимальной суммы длин между его вершинами методом Прима- Краскала ручным и машинным способом.

Оглавление

- Введение

- Теоретическая часть

- Понятие графы

- Представление графов в ЭВМ

- Алгоритм Краскала

- Практическая часть

- Решение задачи - теста

- Ручной расчёт задачи

- Машинная реализация метода

- Блок- схема

- Обоснование выбора языка программирования

- Листинг программы

- Анализ полученных результатов Заключение

- Список литературы

- Приложение А

- Замечание

Список литературы

1. Вентцель Е.С. Исследование операций: задачи, принципы, методология. / Е.С. Вентцель. - М.: Высшая школа, 2001. - 487с.

2. Гончаров Г..А., Мочалин А.А. Элементы дискретной математики. /Г..А. Гончаров - М.: Форум - Инфра-М., 2004. - 128с.

3. Иванов Б.Н. Дискретная математика. Алгоритмы и программы./ Б.Н. Иванов - М.: Лаборатория Базовых Знаний, 2002. - 128с.

4. Кремер Н.Ш. Исследование операций в экономике./Н.Ш.Кремер - М.: ЮНИТИ, 2004. - 407с.

5. Кузнецов А.В. и др. Руководство к решению задач по математическому программированию./ А.В. Кузнецов. - Минск: Высшая школа, 2001. - 448 с.

6. Математическое программирование. Сборник задач и упражнений по высшей математике. / Под ред. Кузнецова А.В., Рутковского Р.А. - Минск: Высшая школа, 2002. - 447с.

7. Морозов И.Н., Сухарев Л.Г., Федоров В.В. Исследование операций в задачах и упражнениях. /И.Н Морозов. - М.: Высшая школа, 1986.-504с.

8. Новиков Ф.А. Дискретная математика для программистов. / Ф.А. Новиков. - С.-Петербург: Питер, 2001. - 304с.

9. Партыка Т.Л. Математические методы./ Т.Л.Партыка, И.И. Попов. - М.: ФОРУМ-ИНФРА-М, 2005. - 464с.

10. Советов Б.Я., Яковлев С.А. Моделирование систем. / Б.Я. Советов. - М.: Высшая школа, 2001. - 343с.

11. Чернов В.П., Ивановский В.Б. Теория массового обслуживания./ В.П. Чернов. - М.: Инфра-М, 2000. - 205с.