39

Частное образовательное учреждение СПО

«Колледж права и экономики»

РЕШЕНИЕ ЗАДАЧИ О НАХОЖДЕНИИ КРАТЧАЙШЕГО ПУТИ В ГРАФЕ

КУРСОВАЯ РАБОТА

по дисциплине: «Математические методы»

КПиЭ-К. 230105-00083 15ПЗ

Выполнил:

Cтудент группы П-440

_______Е.С. Ларочкин

___________________

Проверил:

______Ю.В. Курегова

___________________

2011

З А Д А Н И Е

для курсовой работы по дисциплине

«Математические методы»

Студента четвертого курса группы П-440

Колледжа права и экономики

По специальности 230105 «Программное обеспечение вычислительной техники и автоматизированных систем»

Тема проекта: Решение задачи о нахождении кратчайшего пути в графе.

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

Курсовая работа выполняется студентом в следующем объеме: 39 листов.

Пояснительная записка и расчетная часть работы: В теоретической части излагается результат анализа литературы по теме курсовой работы, состояние исследуемой проблемы, теоретический материал по предмету исследования. Теоретическая часть курсовой работы делится на главы. В теоретическая часть выполнена на 39 листах, 10 рисунках и 3 таблицах. В практической части содержится задача на нахождении кратчайшего пути в графе. Решена методом Дейкстры. В заключении подводятся итоги теоретического исследования, делаются выводы содержится оценка результатов исследования, отмечается практическая значимость исследования и даются рекомендации по использованию и внедрению результатов в практическую деятельность. Библиографический список включает исследование отечественных и зарубежных авторов по выбранной теме курсовой работы, расположенные в алфавитном порядке и пронумерованные.

Дата выдачи 1 ноября___________________________________________2011г.

Срок окончания 20 декабря______________________________________2011г.

Руководитель курсовой работы Ю.В Курегова_________________________________________________

Студент Е.С Ларочкин_____________________________________________________________________

Аннотация

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

Во введении автор должен показать актуальность избранной проблемы, степень ее разработанности и сформулировать те задачи, которые будут решаться в работе. Введение должно быть кратким (3-4 страницы).

Во второй части излагается содержание темы. Эту часть рекомендуется разделить на 4-5 вопросов, так как это приведет к их поверхностной разработке или значительному превышению объема курсовой работы. Изложение каждого вопроса надо четко ограничивать с тем, чтобы можно было ясно видеть, где начинается и где кончается их освещение. Основная часть работы может быть изложена на 25-30 страницах стандартного листа.

Выводы, составляющие третью часть, вытекают из материалов курсовой работы и содержат обоснованные предложения. Заключение нужно писать кратко на 1-2 страницах.

В конце курсовой работы прилагается библиографический список, составленный в определенной последовательности.

В теоретической части излагается результат анализа литературы по теме курсовой работы, состояние исследуемой проблемы, теоретический материал по предмету исследования. Теоретическая часть курсовой работы делится на главы. В теоретическая часть выполнена на 39 листах, 10 рисунках и 3 таблицах.

В практической части содержится задача на нахождении кратчайшего пути в графе. Решена методом Дейкстры.

В заключении подводятся итоги теоретического исследования, делаются выводы содержится оценка результатов исследования, отмечается практическая значимость исследования и даются рекомендации по использованию и внедрению результатов в практическую деятельность.

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

Содержание

ВВЕДЕНИЕ…………………………………………………………………….5

1. ТЕОРИЯ ГРАФОВ. ………………………………………………………...7

1.1 Историческая справка………………………….…………..……..7

1.2 Основные термины и теоремы теории графов………….16

2. ЗАДАЧИ НА ГРАФАХ………………………………………………….....25

2.1 Описание различных задач на графах…………………….25

3. НАХОЖДЕНИЕ КРАТЧАЙШИХ ПУТЕЙ В ГРАФЕ…………………...28

3.1 Алгоритм Дейкстера………………………………..…………...…28

3.2 Алгоритм СОРТИРОВКИ: СОРТИРОВКА ШЕЙКЕР………….......29

3. Нахождение кратчайшего пути в графе методом дейкстры……………………………………………………………………32

4. Нахождение кратчайшего пути в графе с помошью программы………………………………………………………………….

ЗАКЛЮЧЕНИЕ ……………………………………………………………...34

СПИСОК ЛИТЕРАТУРЫ………………………………………………….…35

ПРИЛОЖЕНИЕ …………………………………………………………...…36

Введение

Теория графов находит широкое применение в различных областях науки и техники:

Графы и информация

Двоичные деревья играют весьма важную роль в теории информации. Предположим, что определенное число сообщений требуется закодировать в виде конечных последовательностей различной длины, состоящих из нулей и единиц. Если вероятности кодовых слов заданы, то наилучшим считается код, в котором средняя длина слов минимальна по сравнению с прочими распределениями вероятности. Задачу о построении такого оптимального кода позволяет решить алгоритм Хаффмана.

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

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

Графы и химия

Еще А. Кэли рассмотрел задачу о возможных структурах насыщенных (или предельных) углеводородов, молекулы которых задаются формулой:

C_nH_2n+2

Молекула каждого предельного углеводорода представляет собой дерево. Если удалить все атомы водорода, то оставшиеся атомы углеводорода также будут образовывать дерево, каждая вершина которого имеет степень не выше 4. Следовательно, число возможных структур предельных углеводородов, т. е. число гомологов данного вещества, равно числу деревьев с вершинами степени не больше четырех.

Таким образом, подсчет числа гомологов предельных углеводородов также приводит к задаче о перечислении деревьев определенного типа. Эту задачу и ее обобщения рассмотрел Д. Пойа.

Графы и биология

Деревья играют большую роль в биологической теории ветвящихся процессов. Для простоты мы рассмотрим только одну разновидность ветвящихся процессов – размножение бактерий. Предположим, что через определенный промежуток времени каждая бактерия либо делится на две новые, либо погибает. Тогда для потомства одной бактерии мы получим двоичное дерево.

Нас будет интересовать лишь один вопрос: в скольких случаях n-е поколение одной бактерии насчитывает ровно k потомков? Рекуррентное соотношение, обозначающее число необходимых случаев, известно в биологии под названием процесса Гальтона-Ватсона. Его можно рассматривать как частный случай многих общих формул.