Основные понятия теории графов
Федеральное агентство связи
Бурятский институт инфокоммуникаций Федерального государственного бюджетного образовательного учреждения высшего образования
«Сибирский государственный университет телекоммуникаций и информатики»
(БИИК СибГУТИ)
| Кафедра | «Информатики и вычислительной техники» | |||||
| Допустить к защите |
|
| ||||
| Зав.каф. |
| Рабданова В. В. | ||||
| КУРСОВАЯ РАБОТА |
| «Задача о нефтепроводе максимальной пропускной способности» |
Пояснительная записка
| Студент |
| /Хомяков Н.Д./ | |||
|
Факультет | Информационных технологий |
Группа | ПОВТ-272 | ||
|
Руководитель |
/Кузнецова Ю.С/ | ||||
Улан-Удэ 2018г.
1.Тема курсовой работы
| Задача о нефтепроводе максимальной пропускной способности |
утверждена приказом СибГУТИ от «25» 05 2018 г. №
2.Срок сдачи студентом законченной работы «25» мая 2018 г.
3.Исходные данные к работе
| 1 Специальная литература |
| 2 Материалы сети интернет |
| 4.Содержание пояснительной записки (перечень подлежащих разработке вопросов) | Сроки выполнения по разделам |
| Введение | 25.02.2018 |
| Теоретические аспекты | |
| Практическая реализация | |
| Заключение | 20.05.2018 |
Дата выдачи задания «25» мая 2018 г.
|
|
|
Руководитель _____________________________________
подпись
Задание принял к исполнению «23» февраля 2018 г.
Студент __________________________________________
подпись
Рецензия
Студента: Хомяков Никита Дмитриевич
По специальности 09.02.03 «Программирование в компьютерных системах»
Тема курсового проекта: Задача о нефтепроводе максимальной пропускной способности
Объем пояснительной записки 25 листов
Заключение о степени соответствия выполненного проекта техническому заданию соответствует полностью
 |
Характеристика выполнения основных разделов проекта, качество расчетов, конструктивных решений, практического подтверждения все разделы курсового проекта логично следуют друг за другом, отражают решение поставленной задачи
Практическая ценность работы состоит в том, что разработанный программный продукт может использоваться в при решении задач на нахождение наикратчайшиего пути в графе
Общая грамотность, качество оформления текста и графической части пояснительной записки и демонстрационных чертежей
Пояснительная записка написана грамотно, текст пояснительной записки оформлен в соответствии с ГОСТ
|
|
|
________________________________________________________________________________________________________________________________________
Перечень положительных качеств работы
Логичность построения работы, достаточность иллюстраций работы и создания информационной системы, актуальность выполненной работы
Основные замечания и недостатки работы:
Существенных замечаний и недостатков не имеется
____________________________________________________________________
Предполагаемая оценка _______________________________________________
Рецензент ___________________________________________________________
(фамилия, должность, подпись, дата)
Оглавление
Введение……………………………………………………………..………….5
1 ТЕОРЕТИЧЕСКАЯ ЧАСТЬ………………………………………….………7
1.1 Основные понятия теоритии графов……… ...……………………………7
1.2 Постановка задачи ………………………………………………..……….11
1.3 Методы решения – алгоритмов Краскала…………………….………….12
1.4 Обоснование выбора языка программирования…………………………14
2 ПРАКТИЧЕСКАЯ Реализация……………………………………..………15
2.1 Описание Программы…………………………………………..…………15
2.2 Тестирование…………………………………………………….………...19
2.3 Листинг программы ………………………………………………………21
|
|
|
Заключение…………………………………………………………………….25
Список литературы……………………………………………………………26
Введение
Современное общество отчасти можно рассматривать как систему сетей, предназначенных для транспортирования, передачи и распределения электроэнергии, товаров и информации. Для решения задач оптимального использования этих систем применяется сетевой анализ. В значительной степени он основан на теории графов. Сетевые модели широко применяются в исследовании операций и могут быть использованы на практике, например, при проектировании вычислительных комплексов, транспортных сетей, теле-трансляционных сетей, систем космической связи.
Ни один проект с использованием крупной сети со сложной топологией в настоящее время не обходится без исчерпывающего моделирования будущей сети. Программы, выполняющие эту задачу, достаточно сложны и дороги. Целью моделирования является определение оптимальной топологии, адекватный выбор сетевого оборудования, определение рабочих характеристик сети и возможных этапов будущего развития. Ведь сеть, слишком точно оптимизированная для решений задач текущего момента, может потребовать серьезных переделок в будущем. Так, в данной курсовой работе будут рассмотрены основные модели теории графов, и методы решения сетевых задач на примере задачи о нефтепроводе.
|
|
|
Сетевой моделью (другие названия: сетевой график, сеть) называется экономико-компьютерная модель, отражающая комплекс работ (операций) и событий, связанных с реализацией некоторого проекта (научно-исследовательского, производственного и др.), в их логической и технологической последовательности и связи. Анализ сетевой модели, представленной в графической или табличной (матричной) форме, позволяет более четко выявить взаимосвязи этапов реализации проекта, а также определить наиболее оптимальный порядок выполнения этих этапов в целях, например, сокращения сроков выполнения всего комплекса работ. Таким образом, методы сетевого моделирования относятся к методам принятия оптимальных решений.
Цель курсовой работы – подобрать теоретический материал по рассматриваемой теме, решить задачу о максимальной пропускной способности нефтепровода методом учета ручным и машинным способом.
Для достижения поставленной цели необходимо выполнить следующие задачи:
1. Анализ предметной области
2. Составление математической модели
3. Обзор методов решения задачи
4. Выбор средств разработки
5. Разработка алгоритма, реализующего выбранный метод
6. Написание программы
7. Тестирование и отладка
Теоретическая часть
Основные понятия теории графов
Графом называется набор точек, соединенных между собой ребрами (или дугами).
Таким образом, ребро определяется парой вершин. Два ребра, у которых есть общая вершина, называются смежными (или соседними).
Граф называется ориентированным (или орграфом), если некоторые ребра имеют направление. Это означает, что в орграфе некоторая вершина может быть соединена с другой вершиной, а обратного соединения нет. Геометрически граф часто изображают точками плоскости, причем соседние вершины соединены дугами (для орграфа некоторые дуги имеют направление, что обычно отмечают стрелкой).
Помимо этого, в теории графов рассматриваются также мульти-графы – это такие графы, в которых могут быть петли (т. е. некоторая вершина соединена сама с собой ребром) или некоторые пары вершины могут быть соединены между собой несколькими ребрами.
Маршрут в графе – это последовательность соседних (смежных) вершин. Ясно, что можно определить маршрут и как последовательность смежных ребер (в этом случае ребра приобретают направление). Заметим, что в маршруте могут повторяться вершины, но не ребра. Маршрут называется циклом, если в нем первая вершина совпадает с последней.
Путь в графе (иногда говорят простой путь) – это маршрут без повторения вершин (а значит, и ребер).
Контур – это цикл без повторения вершин, за исключением первой вершины, совпадающей с последней.
Последовательности вершин (рис. 1): 1–2–3–4–2–5 не простой путь, а маршрут; последовательности 1–2–3–4–7–5 и 1–2–5 – простые пути; 1–2–3–4–2–5–6–1 –это цикл (но не контур); 1–2–5–6–1 – это контур. Если имеется некоторый маршрут из вершины t в вершину s, заданный в виде последовательности ребер, которые в этом случае приобрели направление, и если в этот маршрут входит ребро, соединяющее вершины (i, j), то это ребро по отношению к вершине i называют иногда прямой дугой, а по отношению к вершине j – обратной дугой (или обратным ребром).
Граф называется связным, если любые две его вершины можно соединить маршрутом (или путем). На рис. 1 изображен связный граф.
Ребро, при удалении которого граф перестает быть связным, иногда называют мостом или перешейком.
Рисунок 1. Связный граф
Степень вершины – это число ребер, входящих в эту вершину. Вершина называется висячей, если ее степень равна единице.
Лемма 1. Если степень всех вершин в графе больше или равна двум, то граф обязательно содержит контур.
Доказательство. Действительно, выйдя из некоторой вершины и войдя в другую, всегда можно выйти из нее по другому ребру, так как степень вершины больше или равна двум. Выйти из вершины по новому ребру невозможно только в том случае, если эта вершина уже встречалась, а это означает, что можно выделить контур из вершин этого графа.
Постановка задачи
Дата добавления: 2018-08-06; просмотров: 220; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!