close

Вход

Забыли?

вход по аккаунту

- kafedra

код для вставкиСкачать
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ
РОССИЙСКОЙ ФЕДЕРАЦИИ
СЕВЕРО-КАВКАЗСКИЙ ГОРНО-МЕТАЛЛУРГИЧЕСКИЙ
ИНСТИТУТ
КАФЕДРА АВТОМАТИЗИРОВАННОЙ
ОБРАБОТКИ ИНФОРМАЦИИ
Методические указания
к курсовой работе
по дисциплине: Основы теории графов
Составитель: Гроппен В.О.
Владикавказ
2012
Методические указания составлены в соответствии с рабочей
программой курса " Теория графов " для студентов направлений
«Информатика и вычислительная техника»
Цель курсовой работы состоит в углубленном изучении теории
графов и приобретении практических навыков в решении задач
этой теории на персональных ЭВМ.
Ниже, в Приложении, приводится тематика курсовых работ,
основные принципиальные положения их содержания.
ВВЕДЕНИЕ
Целью курсовой работы является закрепление основ и углубление
знаний по теории графов, а также получение практических
навыков в создании и исследовании программных продуктов,
предназначенных для решения задач теории графов. При
выполнении курсовой работы студент самостоятельно осваивает
все этапы создания программного комплекса от постановки
задачи до практической реализации и исследования созданного
программного обеспечения.
1. ТЕМАТИКА КУРСОВЫХ РАБОТ
Тематика курсовой работы выбирается студентом самостоятельно
из предлагаемого в Приложении списка. При этом студенту
необходимо
самостоятельно
определить
структуру
и
характеристики значений вводимых и используемых в программе
данных, с учетом требований, предъявляемых в задании к
выводимой информации. Каждое задание на курсовую работу
уточняется на консультации с преподавателем.
2. СОДЕРЖАНИЕ ПОЯСНИТЕЛЬНОЙ ЗАПИСКИ
Пояснительная записка к курсовой работе должна содержать следующие
обязательные компоненты:
1. Титульный лист.
2. Содержательную постановку задачи и ее приложения.
3. Список используемых обозначений.
4. Формальную постановку задачи.
5. Описание используемого для решения задачи алгоритма (блок-схема
или описание по шагам).
6. Листинг программы на языке высокого уровня.
7. Пример решения задачи «вручную» и с помощью созданного
программного продукта, содержащий результаты промежуточных
расчетов.
8. Описание постановки и результатов эксперимента по проверке
эффективности созданного программного продукта:
• График зависимости времени счета от числа вершин графа.
• График зависимости времени счета от числа дуг (ребер) графа
при фиксированном числе вершин (строится для разного числа
вершин).
9. Список используемой при выполнении курсовой работы литературы.
Дополнительные требования к курсовой работе уточняет преподаватель.
3. Литература.
Приводится список литературных источников, включающий печатные
материалы и адреса в Интернете. На все приводимые в списке литературы
источники должны быть ссылки в тексте курсовой работы.
№
1
1
2
3
4
5
6
7
8
9
10
Тема курсовой работы по теории графов
2
Пользуясь алгоритмом Прима, написать и
исследовать
программу,
определяющую
минимальный связный суграф на взвешенном
неориентированном графе.
Пользуясь методом потенциалов, написать и
исследовать программу поиска кратчайшего
пути из одной заданной вершины в другую на
взвешенном ориентированном графе.
Пользуясь методом потенциалов, написать и
исследовать
программу
поиска
максимального однородного потока из
заданной вершины в заданную на взвешенном
ориентированном графе.
Пользуясь методом полного перебора,
написать и исследовать программу поиска
минимального разреза для потока, идущего из
заданной вершины в заданную на взвешенном
ориентированном графе с использованием
булевых переменных.
Пользуясь симплекс-методом написать и
исследовать
программу
определения
максимальной циркуляции на взвешенном
ориентированном графе
Написать и исследовать программу поиска
всех простых контуров на ориентированном
графе.
Пользуясь
методом
полного
перебора
написать
и
исследовать
программу
определения минимального подмножества
дуг, удаление которых разрывает все контуры
на орграфе с использованием булевых
переменных.
Написать
и
исследовать
программу,
осуществляющую поиск полным перебором
минимального покрывающего подмножества
вершин на неориентированном графе с
использованием булевых переменных.
Написать
программу,
использующую
обращение
к
симплекс-алгоритму,
позволяющую определить неоднородный
(многопродуктовый)
поток
заданной
величины
на
графе,
стоимость
транспортировки которого минимальна.
Написать
и
исследовать
программу,
осуществляющую
поиск
минимального
разреза на сильносвязном графе методом типа
ветвей и границ, осуществляющим поиск с
возвратом
с
использованием
булевых
переменных.
Группа
3
Студент
4
1
11
12
13
14
15
16
17
18
19
20
21
2
Написать
и
исследовать
программу,
осуществляющую распределение полным
перебором n работ между n рабочими,
минимизирующее затраты на их выполнение с
использованием булевых переменных.
Написать и исследовать программу решения
задачи о назначениях полным перебором,
целью которой является минимизация
времени выполнения плана при ограничении
на ресурсы с использованием булевых
переменных.
Написать и исследовать программу решения
задачи о назначениях полным перебором,
целью которой является минимизация
суммарных затрат при условии, что время
выполнения плана не превышает Т с
использованием булевых переменных.
Написать и исследовать программу решения
задачи коммивояжера с аддитивной целевой
функцией
полным
перебором
с
использованием булевых переменных.
Написать и исследовать программу решения
минимаксной задачи коммивояжера полным
перебором с использованием булевых
переменных.
Написать и исследовать программу поиска
минимальной базы дуг полным перебором с
использованием булевых переменных.
Написать и исследовать программу поиска
минимаксной базы дуг полным перебором с
использованием булевых переменных.
Написать и исследовать программу поиска
минимального каркаса с корнем в заданной
вершине полным перебором на взвешенном
ориентированном графе с использованием
булевых переменных.
Написать и исследовать программу поиска
минимаксного
каркаса на взвешенном
орграфе
с
использованием
булевых
переменных.
Написать
и
исследовать
программу,
использующую
симплекс-метод,
предназначенную для поиска максимального
неоднородного потока при условии, что
транспортные
суммарные
расходы
не
превышают заданной величины.
Написать и исследовать программу поиска
минимаксного разреза для потока из одной
заданной вершины в другую на взвешенном
орграфе
с
использованием
булевых
переменных полным перебором.
3
4
1
22
23
24
25
26
27
28
2
Написать и исследовать программу поиска
минимаксного разреза в бисвязном орграфе
полным перебором с использованием булевых
переменных.
Написать и исследовать программу поиска
минимаксного пути на взвешенном орграфе
из одной заданной вершины в другую полным
перебором с использованием булевых
переменных.
Написать и исследовать программу поиска
локально оптимального решения замкнутой
задачи коммивояжера на множестве соседних
планов,
расстояние
Хемминга
между
которыми
не
превышает
двух
с
использованием булевых переменных.
Написать и исследовать программу поиска
локально
оптимального
разреза
на
сильносвязном
взвешенном
графе
на
множестве соседних планов, расстояние
между которыми не превышает единицы (по
Хеммингу) с использованием булевых
переменных.
Программа поиска решения замкнутой задачи
коммивояжера методом типа ветвей и границ
с фронтальным спуском по дереву ветвлений
с использованием булевых переменных.
Входные данные – размерность взвешенного
ориентированного
графа и его матрица
смежности вершин, выходные – оптимальный
порядок обхода вершин и соответствующий
суммарный вес дуг.
Программа поиска решения замкнутой задачи
коммивояжера методом прямого перебора с
использованием булевых переменных.
Входные данные – размерность взвешенного
ориентированного
графа и его матрица
смежности вершин, выходные – оптимальный
порядок обхода вершин и соответствующий
суммарный вес дуг.
Программа поиска глобально оптимального
решения замкнутой задачи коммивояжера
методом
типа
ветвей
и
границ,
осуществляющим поиск с возвратом с
использованием булевых переменных.
Входные данные – размерность взвешенного
ориентированного
графа и его матрица
смежности вершин, выходные – оптимальный
порядок обхода вершин и соответствующий
суммарный вес дуг.
3
4
1
29
30
31
32
33
2
Программа поиска локально оптимального
решения замкнутой задачи коммивояжера
детерминированным методом поиска на
полных соседних планах с использованием
булевых переменных. Входные данные –
размерность взвешенного ориентированного
графа, начальный план и матрица смежности
вершин графа, выходные – оптимальный
порядок обхода вершин и соответствующий
суммарный вес дуг.
Программа поиска локально оптимального
решения замкнутой задачи коммивояжера
рандомизированным методом поиска на
полных соседних планах. Входные данные –
размерность взвешенного ориентированного
графа, начальный план, число итераций и
матрица смежности вершин графа, выходные
– оптимальный порядок обхода вершин и
соответствующий суммарный вес дуг.
Программа поиска локально оптимального
решения замкнутой задачи коммивояжера
рандомизированным методом поиска на
частичных планах с заданной степенью
доверия оценке.
Входные данные – размерность взвешенного
ориентированного графа, начальный план,
число итераций и матрица смежности вершин
графа, выходные – оптимальный порядок
обхода
вершин
и
соответствующий
суммарный вес дуг.
Программа поиска локально оптимального
решения замкнутой задачи коммивояжера
детерминированным методом поиска на
частичных планах (спуск по дереву
ветвлений).
Входные данные – размерность взвешенного
ориентированного
графа, и
матрица
смежности вершин графа, выходные –
оптимальный порядок обхода вершин и
соответствующий суммарный вес дуг.
Программа решения задачи о минимальном
разрезе
во
взвешенном
орграфе
с
бикомпонентами. Решается методом типа
ветвей и границ с фронтальным спуском по
дереву
ветвлений.Входные
данные
–
размерность взвешенного ориентированного
графа и его матрица смежности вершин,
выходные – значения булевых переменных,
определяющие
принадлежность
дуг
к
минимальному разрезу, и соответствующий
суммарный вес выбранных дуг.
3
4
1
34
35
36
37
2
Программа решения задачи о минимальном
разрезе
во
взвешенном
орграфе
с
бикомпонентами. Решается методом типа
ветвей и границ, осуществляющим спуск с
возвратом по дереву ветвлений.
Входные данные – размерность взвешенного
ориентированного
графа и его матрица
смежности вершин, выходные – значения
булевых
переменных,
определяющие
принадлежность дуг к минимальному разрезу,
и
соответствующий
суммарный
вес
выбранных дуг.
Программа решения задачи о минимальном
разрезе
во
взвешенном
орграфе
с
бикомпонентами.
Решается
рандомизированным методом поиска на
полных соседних планах.
Входные данные – размерность взвешенного
ориентированного графа, стартовый план,
число итераций и матрица смежности вершин
графа, выходные – значения булевых
переменных, определяющие принадлежность
дуг графа к минимальному разрезу, и
соответствующий суммарный вес выбранных
дуг.
Программа решения задачи о минимальном
разрезе во взвешенном орграфе с
бикомпонентами. Решается
детерминированным методом поиска на
частичных планах (спуск по дереву
ветвлений) с использованием булевых
переменных.
Входные данные – размерность взвешенного
ориентированного
графа и
матрица
смежности вершин графа, выходные –
значения
булевых
переменных,
определяющие принадлежность дуг графа к
минимальному разрезу и соответствующий
суммарный вес дуг.
Программа решения задачи о минимальной
базе дуг на взвешенном орграфе. Решается
методом типа ветвей и границ с фронтальным
спуском по дереву ветвлений с
использованием булевых переменных.
Входные данные – размерность взвешенного
ориентированного
графа и его матрица
смежности вершин, выходные – значения
булевых
переменных,
определяющие
принадлежность дуг к минимальному разрезу,
и
соответствующий
суммарный
вес
выбранных дуг.
3
4
1
38
39
40
41
2
Программа решения задачи о минимальной
базе дуг на взвешенном орграфе. Решается
методом типа ветвей и границ,
осуществляющим спуск с возвратом по
дереву ветвлений.
Входные данные – размерность взвешенного
ориентированного графа и его матрица
смежности вершин, выходные – значения
булевых переменных, определяющие
принадлежность дуг к минимальному разрезу,
и соответствующий суммарный вес
выбранных дуг.
Программа решения задачи о минимальной
базе дуг на взвешенном орграфе с
бикомпонентами. Решается
рандомизированным методом поиска на
полных соседних планах с использованием
булевых переменных.
Входные данные – размерность взвешенного
ориентированного графа, стартовый план,
число итераций и матрица смежности вершин
графа, выходные – значения булевых
переменных, определяющие принадлежность
дуг графа к минимальному разрезу, и
соответствующий суммарный вес выбранных
дуг.
Программа решения задачи о минимальной
базе дуг на взвешенном орграфе. Решается
детерминированным методом поиска на
частичных планах (спуск по дереву ветвлений
в лучшем направлении) с использованием
булевых переменных.
Входные данные – размерность взвешенного
ориентированного графа и матрица
смежности вершин графа, выходные –
значения булевых переменных,
определяющие принадлежность дуг графа к
минимальному разрезу и соответствующий
суммарный вес дуг.
Написать и исследовать программу,
осуществляющую поиск методом типа ветвей
и границ минимального покрывающего
подмножества вершин на неориентированном
графе. Входные данные – размерность
взвешенного неориентированного графа и
матрица смежности вершин графа, выходные
– значения булевых переменных,
определяющие принадлежность вершин графа
к минимальному покрывающему множеству.
3
4
1
42
43
2
Написать и исследовать программу,
осуществляющую поиск на множестве
соседних планов локально оптимального
минимального покрывающего подмножества
вершин на неориентированном графе с
использованием булевых переменных.
Входные данные – размерность взвешенного
неориентированного графа и матрица
смежности вершин графа, стартовое
покрывающее множество вершин, выходные –
значения булевых переменных,
определяющие принадлежность вершин графа
к минимальному покрывающему множеству.
Написать и исследовать программу,
осуществляющую спуском по дереву
ветвлений в лучшем направлении поиск
локально оптимального минимального
покрывающего подмножества вершин на
неориентированном графе с использованием
булевых переменных. Входные данные –
размерность взвешенного
неориентированного графа и матрица
смежности вершин графа, выходные –
значения булевых переменных,
определяющие принадлежность вершин графа
к минимальному покрывающему множеству.
44
Написать и исследовать программу,
осуществляющую рандомизированным
спуском по дереву ветвлений поиск локально
оптимального минимального покрывающего
подмножества вершин на неориентированном
графе с использованием булевых переменных.
Входные данные – размерность взвешенного
неориентированного графа и матрица
смежности вершин графа, последовательность
«случайных» чисел и их количество,
выходные – значения булевых переменных,
определяющие принадлежность вершин графа
к минимальному покрывающему множеству и
число этих вершин.
45
Написать и исследовать программу,
решающую задачу о назначениях, как задачу
оптимального упорядочения вершин
двудольного графа полным перебором всех
перестановок. Входные данные – размерность
взвешенного графа и матрица смежности
вершин графа, выходные – значения
переменных, определяющие оптимальную
перестановку вершин графа.
3
4
1
46
47
48
2
Написать и исследовать программу,
решающую замкнутую минимаксную задачу
коммивояжера, как задачу оптимального
упорядочения вершин орграфа полным
перебором всех перестановок. Входные
данные – размерность взвешенного графа и
матрица смежности вершин графа, выходные
– значения переменных, определяющие
оптимальную перестановку вершин графа.
Написать и исследовать программу,
решающую задачу о минимальном каркасе с
корнем в заданной вершине на орграфе, как
задачу оптимального упорядочения вершин
полным перебором всех перестановок.
Входные данные – размерность взвешенного
графа и матрица смежности вершин графа,
выходные – значения переменных,
определяющие оптимальную перестановку
вершин графа.
Написать и исследовать программу,
решающую задачу о поиске минимаксного
пути из одной заданной вершины в другую,
как задачу оптимального упорядочения
вершин взвешенного орграфа полным
перебором всех перестановок. Входные
данные – размерность взвешенного графа и
матрица смежности вершин графа, выходные
– значения переменных, определяющие
оптимальную перестановку вершин графа.
49
Написать и исследовать программу,
решающую задачу о поиске кратчайшего пути
из одной заданной вершины в другую, как
задачу оптимального упорядочения вершин
взвешенного орграфа полным перебором всех
перестановок. Входные данные – размерность
взвешенного графа и матрица смежности
вершин графа, выходные – значения
переменных, определяющие оптимальную
перестановку вершин графа.
50
Написать и исследовать программу,
решающую задачу о минимаксном разрезе в
сильносвязном орграфе, как задачу
оптимального упорядочения вершин полным
перебором всех перестановок. Входные
данные – размерность взвешенного графа и
матрица смежности вершин графа, выходные
– значения переменных, определяющие
оптимальную перестановку вершин графа.
3
4
1
51
52
2
Написать и исследовать программу,
решающую разомкнутую задачу
коммивояжера, как задачу оптимального
упорядочения вершин орграфа перебором
всех перестановок вершин. Входные данные –
размерность взвешенного графа и матрица
смежности вершин графа, выходные –
значения переменных, определяющие
оптимальную перестановку вершин графа.
Написать и исследовать программу,
решающую задачу о минимальном разрезе в
бисвязном взвешенном орграфе, как задачу
оптимального упорядочения вершин орграфа
методом перебора всех перестановок вершин.
Входные данные – размерность взвешенного
графа и матрица смежности вершин графа,
выходные – значения переменных,
определяющие оптимальную перестановку
вершин графа.
53
Написать и исследовать программу,
осуществляющую проверку наличия
бисвязных компонент на ориентированном
графе. Входные данные – размерность
взвешенного графа и матрица смежности
вершин графа, выходные – одно из
утверждений: «Бикомпоненты отсутствуют»
или «Бикомпоненты присутствуют».
54
Написать и исследовать программу,
осуществляющую ранжирование вершин на
ориентированном графе без контуров по
отношению к вершине-источнику. Входные
данные – размерность взвешенного графа и
матрица смежности вершин графа, выходные
– перестановка вершин графа.
55
Написать и исследовать программу,
осуществляющую ранжирование вершин на
ориентированном графе без контуров по
отношению к вершине-стоку. Входные
данные – размерность взвешенного графа и
матрица смежности вершин графа, выходные
– перестановка вершин графа.
56
Пользуясь симплекс методом, написать и
исследовать программу поиска
максимального однородного потока из любой
заданной вершины в любую заданную на
взвешенном ориентированном графе.
3
4
1
57
2
Написать и исследовать программу,
осуществляющую перебор всех простых
путей (т.е. путей без самопересечений) с
заданным числом дуг на ориентированном
графе. Входные данные – размерность
взвешенного графа и матрица смежности
вершин графа, выходные – перестановки
вершин графа, отвечающие найденным путям
и их длина (суммарный вес дуг каждого пути).
58
Написать и исследовать программу,
осуществляющую перебор всех простых не
гамильтоновых контуров (т.е. контуров без
самопересечений, содержащих менее n дуг,
где n - число вершин графа) на
ориентированном графе. Входные данные –
размерность взвешенного графа и матрица
смежности вершин графа, выходные –
перестановки вершин графа, отвечающие
найденным контурам и суммарный вес дуг
каждого контура.
59
Написать и исследовать программу,
проверяющую условия достижимости вершин
из любой заданной вершины
ориентированного графа. Входные данные –
размерность взвешенного графа и матрица
смежности вершин графа, выходные –
пометка «вершина… достижима из заданной»
либо «вершина… не достижима из заданной»
применительно ко всем вершинам графа.
60
Написать и исследовать программу,
проверяющую планарность графа. Входные
данные – размерность графа и матрица
смежности вершин графа, выходные – одно из
утверждений: «граф является планарным»
либо «граф не является планарным».
61
Написать и исследовать программу,
осуществляющую распределение полным
перебором n работ между n рабочими,
минимизирующую верхнюю границу затрат
на их выполнение каждым рабочим с
использованием булевых переменных.
62
Написать и исследовать программу,
осуществляющую поиск максимального
потока из заданной вершины
ориентированного графа в заданное
подмножество вершин того же графа.
3
4
1
63
64
65
66
67
68
2
Программа решения задачи о минимаксной
базе дуг на взвешенном орграфе. Решается
полным перебором с использованием булевых
переменных.
Входные данные – размерность взвешенного
ориентированного графа и его матрица
смежности вершин, выходные – значения
булевых переменных, определяющие
принадлежность дуг к минимальному разрезу,
и соответствующий суммарный вес
выбранных дуг.
Программа решения задачи о минимаксной
базе дуг на взвешенном орграфе. Решается
дихотомией упорядоченного множества дуг с
использованием булевых переменных.
Входные данные – размерность взвешенного
ориентированного графа и его матрица
смежности вершин, выходные – значения
булевых переменных, определяющие
принадлежность дуг к минимальному разрезу,
и соответствующий суммарный вес
выбранных дуг.
Написать и исследовать программу,
осуществляющую поиск полным перебором
минимаксной версии задачи Прима. Входные
данные –неориентированный граф, заданный
матрицей, выходные – подмножество ребер,
образующих связный граф с минимаксным
весом.
Написать и исследовать программу,
осуществляющую поиск полным перебором
минимаксного пути из заданной вершины в
заданную. Входные данные: взвешенный
орграф, заданный матрицей М и индексы
вершины-источника и вершины-стока.
Выходные данные: дуги и вершины,
определяющие минимаксный путь.
Написать и исследовать программу,
осуществляющую поиск полным перебором
минимаксной базы дуг на взвешенном
орграфе. Входные данные: взвешенный
орграф, заданный матрицей М. Выходные
данные: дуги и вершины, определяющие
минимаксную.
Написать и исследовать программу,
осуществляющую определение числа
бисвязных подграфов на взвешенном орграфе.
Входные данные: взвешенный орграф,
заданный матрицей М. Выходные данные:
число бисвязных подграфов.
3
4
1/--страниц
Пожаловаться на содержимое документа