Степень выпускников: бакалавр

СОЦИАЛЬНО-ЭКОНОМИЧЕСКИЙ

ИНСТИТУТ

Кафедра информатики и вычислительной техники

Теория графов и сетей

Методические указания

По самостоятельной работе студентов

Направлений подготовки

Прикладная информатика

Информатика и вычислительная техника

степень выпускников: бакалавр

Киров

Рассмотрено на заседании кафедры информатики и вычислительной техники, протокол № 2 от 19 октября 2012 г.

Утверждено на заседании учебно-методического совета, протокол № 71 от 19 ноября 2012 г.

Теория графов и сетей: Методические указания / Сост. Т.В. Волченская. – Киров: ВСЭИ, 2012. – 16 с.

Методические указания разработаны в соответствии с учебными программами дисциплины «Теория графов и сетей» и предназначены для студентов, обучающихся по направлениям подготовки 230700.62 Прикладная информатика, 230100.62 Информатика и вычислительная техника (степень выпускников: бакалавр)

© Вятский социально-экономический

институт (ВСЭИ), 2012

1. Цели и задачи курсовой работы

Курсовая работа посвящена изучению методов решения оптимизационных задач на графах и сетях в связи.

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

Задачи курсовой работы:

1. Изучение теоретических вопросов графов и сетей.

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

3. Изучение возможных методов решения задачи, сформулированной в варианте задания.

4. Разработка конкретного алгоритма решения задачи, указанной в варианте.

5. Программирование алгоритма решения задачи.

6. Формирование навыков обработки и анализа результатов, написания заключений и рекомендаций.

2. Требования к результатам курсовой работы

В результате выполнения курсовой работы студент должен:

Знать:

- основные положения теории графов и сетей;

- матричные формы представления информации о графах и сетях;

- основные методы решения задачи.

Уметь:

- представлять исходные данные о моделях исследования;

- составлять алгоритмы решения задач на графах;

- программировать алгоритмы решения графовых задач;

- формулировать выводы и давать рекомендации по результатам исследования.

Владеть:

- навыками самостоятельного решения задач исследования моделей в виде графов и сетей.

3. Объем самостоятельной работы студента

Самостоятельная работа студента составляет 1,5 зачетные единицы по очной форме обучения, 2,5 зачетные единицы по заочной форме обучения, в том числе курсовая работа - 1 зачетная единица.

Выполнение курсовой работы предполагает самостоятельную работу студента по темам учебной программы:

1. Графы и способы их представления.

3. Графы и подграфы.

5. Пути и циклы в графах.

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

Вариант 1

Разработать алгоритм, написать и отладить программу для решения задачи: Граф задается случайным образом. По матрице инциденций определить является ли он симметрическим или антисимметрическим.

Вариант 2

Разработать алгоритм, написать и отладить программу для решения задачи: Граф задается случайным образом. По матрице инциденций определить является ли он двудольным или полным двудольным.

Вариант 3

Разработать алгоритм, написать и отладить программу для решения задачи: Граф задается случайным образом. По матрице инциденций определить является ли он полным или полным симметрическим.

Вариант 4

Разработать алгоритм, написать и отладить программу для решения задачи: Граф задается случайным образом. По матрице инциденций определить является ли он полным или полным антисимметрическим.

Вариант 5

Разработать алгоритм, написать и отладить программу решения задачи: Граф, представленный матрицей смежности, формируется случайным образом.

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

Вариант 6

Разработать алгоритм, написать и отладить программу для решения задачи: Граф задается случайным образом. По матрице инциденций определить является ли он графом типа «дерево».

Вариант 7

Разработать алгоритм, написать и отладить программу для решения задачи: Граф задается случайным образом. Определить является ли он сильно связным графом.

Вариант 8

Разработать алгоритм, написать и отладить программу для решения задачи: Граф задается случайным образом. Определить является ли он одностороннесвязным графом.

Вариант 9

Разработать алгоритм, написать и отладить программу для решения задачи: Граф задается случайным образом. Определить является ли он слабосвязным графом.

Вариант 10

Разработать алгоритм, написать и отладить программу для решения задачи: Граф задан матрицей смежности, сформированной случайным образом. Определить имеется ли в графе Гамильтонов контур.

5. Выполнение и оформление курсовой работы

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

Структура курсовой работы:

1. Титульный лист (наименование учебной дисциплины, специальность, курс, шифр группы, фамилия, имя, отчество автора и т.д.) (см. Приложение 1).

2. Реферат (Приложение 2).

3. Основная часть включает:

Ø постановку задачи (Приложение 3);

Ø математическую формулировку задания;

Ø необходимые теоретические выкладки;

Ø введенные обозначения;

Ø алгоритм решения;

Ø результаты расчетов в виде скриншотов;

Ø выводы.

4. Список использованной литературы.

5. Приложения.

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

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

Тестовые расчеты должны быть сделаны не менее чем на 3 различных наборах данных.

Оформление курсовой работы должно соответствовать требованиям, предъявляемым к выполнению курсовых работ в ВСЭИ.

6. Содержание курсовой работы

Поиск по сайту: