Есть приложение (Реализация алгоритма поиска кратчайшего пути (алгоритма Дейкстры) в Matlab).
Введение 3
1 Основные сведения о графах 5
2 Математическое описание графов 9
3 Расчет метрических характеристик графа 10
4 Реализация алгоритмов на графе 13
4.1 Нахождение минимального пути (алгоритм Дейкстры) 13
4.2 Построение кратчайшего остовного дерева 18
4.3 Нахождение эйлерова цикла 20
4.4 Раскраска вершин графа 22
Заключение 27
Список использованных источников 28
Приложение 1 29
Спектр применения компьютерной техники в последнее время все более расширяется. Если на заре ее развития вычислительные машины использовались исключительно в научных расчетах в специализированных научных, образовательных и военных учреждениях, то в настоящее время персональный компьютер можно встретить и в организациях (как крупных, так и совсем небольших) и у частных лиц. Причем такой бурный рост распространения компьютерной техники произошел за последние 60-70 лет.
Связано столь бурное распространение компьютеров с совершенствованием технологий, используемых при их производстве. Первые компьютеры представляли собой дорогостоящие сооружения, занимавшие несколько комнат и потребляющие огромное количество электроэнергии. При этом их вычислительная мощность была сравнительно не велика. По мере развития технологий производства элементарной базы для вычислительной техники их размеры и стоимость существенно уменьшились, а вычислительная мощность – увеличилась. Современный персональный компьютер средней производительности стоит около 20000 рублей, легко размещается на письменном столе и позволяет выполнять сложные вычисления, обрабатывать графическую информацию, слушать музыку и смотреть фильмы.
Некоторые из возможностей практического использования персонального компьютера известны практически всем пользователям: обработка текстовых документов, просмотр изображений и видеофильмов. Однако некоторые из сфер применения компьютера не известны широкому кругу пользователей и поэтому представляют особый интерес. К данному кругу задач можно отнести, в частности, решение классических научных задач. Таким образом, рассмотрение возможностей использования персонального компьютера для их решения является достаточно интересной темой и, соответственно, актуальной данной темы не вызывает сомнений.
Целью настоящей курсовой работы как раз и является решение некоторых задач, относящихся к достаточно обширному разделу дискретной математики – теории графов. В рамках теории графов рассматривается целый ряд алгоритмов, которые активно используются при решении большого количества практических задач (поиск оптимального пути между двумя пунктами, построение оптимального маршрута доставки для имеющихся точек и т.д.).
В рамках настоящей курсовой работы будут рассмотрены следующие задачи:
приведены основные сведения и определения, относящиеся к теории графов;
рассмотрены вопросы, связанные с математическим описанием графов;
рассмотрены задачи, связанные с расчетом метрических характеристик графов;
продемонстрированы некоторые алгоритмы, обработки графов.
При решении некоторых из указанных задач будет использован пакет Matlab, представляющий собой мощный инструмент, обеспечивающий возможность выполнения научных расчетов самого широкого предназначения.
Таким образом, объектом исследования в рамках настоящей работы является теория графов. Предмет исследования – изучение вариантов математического описания графов, расчет их метрических характеристик и практическое использование некоторых алгоритмов их обработки.
Для выполнения исследований в настоящей работе использовались классические научные методы: анализ, синтез, дедукция. Теоретической основной выполнения работы послужила литература и электронные источники, содержащие информацию по теории графов и возможностях пакета Matlab.
В настоящей работе были рассмотрены несколько практических задач, использующихся при работе с графами. Как было отмечено в первой главе работы, графы и алгоритмы их обработки активно применяются в самых различных сферах деятельности. Таким образом, знание алгоритмов обработки будет востребовано для специалистов, работающих в самых различных областях.
Следует отметить, что наиболее важным является именно знание самого алгоритма решения той или иной задачи, а не знание принципов реализации данного алгоритма на том или ином языке программирования. В рамках настоящей курсовой работы в ее основной части как раз и приведено описание алгоритмов решения рассматриваемых задач. Тем не менее, в Приложении 1 к настоящей работы рассмотрено решение некоторых задач с использованием пакета Matlab.
Решение задач подобного класса не очень типично для пакета Matlab. Как правило, он используется для решения вычислительных задач различного класса. Однако, в составе пакета Matlab существует возможность использования стандартных алгоритмических конструкций и реализации достаточно сложных программ.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
