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

ВЯТСКИЙ

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

ИНСТИТУТ

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

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

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

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

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

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

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

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

Киров

2012

Рассмотрено на заседании кафедры информатики и вычислительной техники, протокол № 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. Содержание курсовой работы

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

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

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

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

7. Учебно-методическое обеспечение

А. Основная

1.  , Князьков математика: ч.2. Теория графов: Учеб. пособие. - 2007. – 124 с.-//www. intuit. ru

2.  еория графов: учебник для вузов / Ф. Харари. – М.: УРСС, 2006.

Б. Дополнительная литература

1. Белоусов А. И., Ткачев С. Б. Дискретная математика. – М.: Изд-во МГТУ им , 2001. – 744 с.

2. рафы и их применение: Пер. с англ. - Изд.3-е стереотипное. – М.: КомКнига, 2006.

В. Программное обеспечение

Курсовая работа выполняется с использованием языка программирования Pascal, Delphi или Cи (Borland Pascal, Borland Cи).

Г. Базы данных, информационно-справочные и поисковые системы

Не предусмотрено.

8. Материально-техническое обеспечение курсовой работы

Не предусмотрено.

Приложения

Приложение 1

Пример оформления

ВЯТСКИЙ СОЦИАЛЬНО-ЭКОНОМИЧЕСКИЙ ИНСТИТУТ

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

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовой работе по теме

“Решение оптимизационных задач

на графах и сетях”

Дисциплина: Теория графов и сетей

Группа: ИВТс-23

Разработал студент:

Работа принята c оценкой____________

Руководитель проекта:

Киров, 20__

Приложение 2

РЕФЕРАТ

Пояснительная записка содержит:

47 страниц, 36 таблиц, 2 алгоритма, 4 использованных источника,

2 приложения.

ГРАФ, ПОДГРАФ, МАТРИЦА СМЕЖНОСТИ, МАТРИЦА ИНЦИДЕНЦИЙ, СИММЕТРИЧЕСКИЙ ГРАФ ВЕРШИНА, ДУГА, МАТРИЦА ВЕСОВ РАССТОЯНИЙ, МЕТОД МАЛЬГРАНЖА, ТРАНЗИТИВНЫЕ ЗАМЫКАНИЯ.

Объектом исследования в данной курсовой работе являются графы и сети.

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

В курсовой работе определяется, является ли граф симметрическим. Особенность этой задачи состоит в том, что граф задан матрицей инциденций. Для этого задания написана программа на языке С++.

Во втором задании выполнено поэтапное разбиение графа, заданного матрицей смежности, на максимальные сильно связанные подграфы методом Мальгранжа. Для этого задания также написана программа на языке С++. Разбиение производится, начиная с вершины 7. Строится база по графу, заданному матрицей весов расстояний, используется алгоритм Дэйкстры. База строится относительно вершины 7.

Приложение 3

Матричный метод разбиения графа на максимальные сильно

связные подграфы

Задание:

Выполнить разбиение графа на максимальные сильно связанные подграфы матричным методом.

Общие сведения:

Матричный метод разбиения

Метод разбиения графа на максимальные сильно связные подграфы по матрицам достижимости R и контрдостижимости Q состоит в следующем:

1. По матрице смежности строится матрица достижимости R.

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

2. Находится матрица С ={Сij}, ij = 1,2,3,...n, где n

-  число вершин исходного графа, а каждый элемент

Сij = Rij*Qij, т. е. матрица С получается поэлементным логическим умножением матриц R и Q.

3. Элементы, имeющиe одинаковые строки и столбцы в матрице

С группируются перестановкой строк, получаем (строчeчно диагональную матрицу Св, где каждая группа элементов и есть максимальный сильно связный подграф.

Для нахождения матрицы достижимости определены транзитивные замыкания, представленные на рис.7. Сама матрица достижимости показана на рис.8.

Т+(Хi)

 

Рис. 7

Рис. 8

Используя операцию транспонирования, находится матрица Q, изображённая на рис.9.

Рис. 9

Перемножая логически матрицы R*Q, получена матрица С, изображённая на рис.10.

Рис.10

Элементы, имeющиe одинаковые строки и столбцы в матрице группируются перестановкой строк, получена строчeчно диагональная матрица Св, изображённая на рис.11.

Рис.11

Каждая группа элементов и есть максимальный сильно связный подграф. Итак, получены максимальные сильно связный подграфы:

G1=(X1,A1), Х1={2,4,5,6,7,10,11,14,15,16,17,19,21,22,23,24,25}

G2=(X2,A2), Х2={1,8,12,20}

G3=(X3,A3), Х3={3,8,13,18}

Приложение 4

Приложение 4

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

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

Ответственный за выпуск:

Технический редактор:

Корректор:

Издательский орган ВСЭИ

610000 Киров, Большевиков, 91А

тел./

Подписано в печать «___» __________ 20__ г.

Тираж: ____экз.

Отпечатано на ризографе ВСЭИ