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

Теория графов

Учебное пособие

по выполнению курсовых работ

«Исследование и программная реализация алгоритмов теории графов»

 

для студентов бакалавриата направлений 09.03.01 «Информатика и вычислительная техника, 09.03.02 «Информационные системы и технологии, 09.03.04 «Программная инженерия» очной, заочной, очно-заочной форм обучения

 

 

Красноярск

2013

УДК 519.6 (075.8)

Т.Н. Иванилова, С.П.Якимов Дискретная математика. Теория графов: Учебное пособие по выполнению курсовых работ «Исследование и программная реализация алгоритмов теории графов» для студентов направлений: 09.03.01 «Информатика и вычислительная техника, 09.03.02 «Информационные системы и технологии, 09.03.04 «Программная инженерия» очной, заочной, очно-заочной форм обучения.- Красноярск: СибГТУ, 2013.-43 с.

 

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

 

 

Одобрено и рекомендовано к печати редакционно-издательским советом СибГТУ _______________________.

 

 

Рецензенты     А.А.Новоселов, к.ф.-м.н., доцент, СФУ

                        Т.Г.Зингель, к.т.н., доцент, РИС СибГТУ

 

 

© Т.Н.Иванилова, С.П.Якимов

© ФГБОУ ВПО «Сибирский государственный

технологический университет», 2013

Содержание

Введение. 4

1 Задания для курсовой работы.. 5

2 Основные понятия и алгоритмы на графах. 10

2.1 Основные понятия теории графов. 10

2.1 Алгоритмы на графах. 12

3 Указания к выполнению курсовой работы.. 18

4 Правила выполнения курсовой работы.. 19

4.1 Структура курсовой работы.. 19

4.2 Требования к содержанию пояснительной записки. 20

4.3 Общие правила оформления конструкторской документации. 20

4.4 Необходимые установки в редакторе WORD для выполнения конструкторского документа. 21

Контрольные вопросы для защиты.. 22

Библиографический список. 23

Приложение A(справочное) 24

Образец выполнения текстовой части курсовой работы с примером выполнения расчетов 24

Приложение B (справочное) 33

Создание оконных интерактивных приложений. Динамические массивы.. 33

Задание на программирование: 33

Инструкция по выполнению.. 34

Приложение С (справочное) 39

Создание графических приложений. 39

Задание на программирование: 39

Инструкция по выполнению.. 39

Введение

Учебное пособие предназначено в первую очередь студентам для выполнения курсовых работ по дисциплине «Дискретная математика». Разделы пособия содержат справочную информацию по понятиям и алгоритмам теории графов, варианты заданий по курсовым работам, приложения.

Перед выполнением задания, которое выдает преподаватель, студент должен овладеть необходимыми знаниями по «Дискретной математике», навыками работы в операционной системе, в текстовом редакторе, в какой-либо среде программирования, позволяющей выполнить требования, предъявляемые к курсовым работам по данной дисциплине.

В указаниях Приложения А к учебному пособию содержится рекомендуемая последовательность действий для правильного выполнения и оформления отчета. Отчет по выполнению курсовой работы должен быть оформлен в соответствии со стандартами СТП.

В Приложениях В, С к учебному пособию приведены справочные материалы и практикумы по программированию, позволяющие реализовывать ввод матриц, работу с матрицами и осуществлять работу с графическими приложениями в Delphi.

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

 

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

1. В горной лесопарковой зоне расположены семь площадок для отдыха, соединенных тропами. Расположение площадок и длины троп указать на рисунке. Найти кратчайший путь из нижней точки до верхней.

2. Спроектировать телефонную сеть с минимальной суммарной длиной линий для баз горноспасательных служб. Расположение баз и расстояние между ними указать на рисунке.

3. Рассмотрим алфавит, состоящий из k букв. Разместить слова длины h в словаре. При размещении слов использовать правила составления стандартного словаря.

4. Для изображения на плоскости фигуры определить, можно ли непрерывным образом нарисовать ее, не проводя дважды по одной и той же линии. Если это можно сделать, то сформировать последовательность рисования.

5. Имеется n городов, соединенных сетью дорог. Заданы длины участков дорог между парами городов. Спроектировать структуру телефонной сети с минимальной стоимостью затрат на ее строительство, если считать, что стоимость участка сети между двумя городами пропорциональна расстоянию между ними.

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

7. Задана карта дорог в некотором городе. На каждом перекрестке пересекаются две дороги. Заданы все расстояния между соседними перекрестками. Построить кратчайший маршрут между двумя заданными пунктами.

8. Вывести путешественников, попавших в лабиринт, к выходу. Лабиринт представляет собой совокупность коридоров и перекрестков. Местом начала пути может быть любой из имеющихся перекрестков.

9. Построить раскраску карты в минимальное число цветов, так чтобы смежные области (имеющие общую границу) не были раскрашены в один цвет.

10. Составить команду космического корабля из трех человек: командира, инженера и врача. На место командира есть четыре кандидата а1, а2, а3, а4, на место инженера - 3 кандидата b1, b2, b3 и на место врача 3 кандидата с1, с2, с3. Проведенная проверка показала, что командир а1 психологически совместим с инженерами b1 и b3 и врачами с2, с3, командир а2 - с инженерами b1 и b2 и всеми врачами, командир а3 - со всеми инженерами и врачом с2. Кроме того, инженер b1 психологически несовместим с врачом с3, инженер b2 - с врачом с1 и инженер b3 - с врачом с2.

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

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

13. Перед Вами топографическая карта местности, на которой переплелись - перепутались реки и их притоки. Известно, что изображенная речная сеть относится к нескольким речным бассейнам. Расклассифицируйте реки и их притоки по речным бассейнам.

14. Двое влюбленных, гуляющих по аллеям парка, не хотят расставаться как можно дольше. Укажите им наиболее длинный путь от входа в парк до выхода.

15. Окажите помощь торговой фирме. Укажите на карте района выгодное расположение торговых точек. Предполагается, что весь район разделен на квадраты.

16. Создайте обучающую программу, предназначенную для студентов, изучающих алгоритм обхода графа в глубину.

17. Создайте обучающую программу, предназначенную для студентов, изучающих алгоритм обхода графа по ширине.

18. Создайте программную реализацию алгоритм Тэрри для нахождения компонент связности графа.

19. Создайте программную реализацию алгоритма ”Фронта волны”, в которой наглядно было бы отражено соответствие названия и сути алгоритма (для неориентированного графа).

20. Создайте программную реализацию алгоритма ”Фронта волны”, в которой наглядно было бы отражено соответствие названия и сути алгоритма (для ориентированного графа).

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

22. Разместить военные базы по территории, так чтобы они контролировали данную местность полностью. Местность поделена на квадраты.

23. Создать программную реализацию алгоритма нахождения остовного дерева графа.

24. Создать программную реализацию нахождения минимального ребра в нагруженном графе.

25. Создать программную реализацию нахождения максимального пути в нагруженном орграфе.

26. Компьютерная фирма, занимающаяся прокладкой кабелей для локальной сети, задумалась над экономией средств - то бишь над уменьшением метража используемого кабеля. Помогите им справиться с этой задачей. Топология сети не ограничивается.

27. Постройте обход шахматной доски nxn конем, формулируя задачу в терминах теории графов.

28. Постройте обход шахматной доски nxn ладьей, формулируя задачу в терминах теории графов.

29. Имеется полный набор костей домино с числами 0,1,...,n. Можно ли выложить их в одну цепочку, соединяя сторонами с одинаковыми числами, чтобы не осталось ни одной не использованной кости? Проверить для n=2,3,4.

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

Реализовать:

31. Алгоритм Тэрри нахождения пути в графе из заданной вершины x в заданную вершину y.

32. Алгоритм Тэрри нахождения компонент связности графа.

33. Алгоритм Фронта волны нахождения минимального пути в графе из заданной вершины x в заданную вершину y.

34. Алгоритм Фронта волны нахождения минимального пути в ориентированном графе из заданной вершины x в заданную вершину y.

35. Алгоритм Форда-Беллмана нахождения минимального пути в графе из заданной вершины x в заданную вершину y.

36. Алгоритм Форда-Беллмана нахождения минимального пути в ориентированном графе из заданной вершины x в заданную вершину y.

37. Алгоритм Форда-Беллмана нахождения минимального пути в графе из заданной вершины x в заданную вершину y, содержащего не более чем k дуг.

38. Алгоритм Форда-Беллмана нахождения максимального пути в ориентированном графе из заданной вершины x в заданную вершину y.

39. Алгоритм нахождения остовного дерева графа.

40. Алгоритм нахождения минимального остовного дерева в графе.

41. Алгоритм обхода графа в ширину.

42. Алгоритм обхода графа в глубину.

43. Алгоритм нахождения компонент связности графа.

44. Алгоритм Форда-Беллмана нахождения минимального пути между всеми вершинами графа.

45. Алгоритм вычисления доминирующего множества.

46. Алгоритм расчета числовых характеристик графа.

47. Алгоритм расчета степеней вершин графа.

48. Алгоритм расчета полустепеней исхода и захода графа.