Связность в орграфах.7. Раскраски карт. Планарные графы. Критерии планарности. Формула Эйлера. Геометрически двойственный граф. Правильная раскраска карты. Теорема Хивуда. Теорема о четырѐх красках. 8. Рѐберные раскраски графов. Хроматический индекс. Теорема Кѐнига. Теорема Визинга. 9.Деревья. Двоичные деревья. Код Прюффера. 10. Потоки в сетях. Задача о максимальном потоке. 11. Алгоритмы проверки планарности графов. 12. 13. Связность. Вершинная и реберная связность. Двусвязные графы. Теорема Менгера. Поиск на графе. Независимые множества. Клики. Вершинные покрытия. Паросочетания и реберные покрытия.. Задача почтальона.
Порядок и сроки выдачи заданий на курсовое проектирование - Техническое задание на проектирование, выдаваемое руководителем студенту, является исходным документом для разработки курсового проекта. - Студент обязан в двухнедельный срок после начала семестра получить задание на проектирование. - Задание оформляется на специальном бланке, подписывается руководителем курсового проекта, студентом и заведующим кафедрой. - Задание подшивается в пояснительную записку по курсовому проектированию после титульного листа. Студент не допускается к защите курсового проекта при отсутствии технического задания.
Содержание курсового проекта
В курсовом проекте требуется 1) изучить соответствующий раздел теории графов; 2) разработать и реализовать алгоритм по теме курсового проекта; 3) провести тестирование программы; 4) использовать соответствующий алгоритм при решении практической задачи.
Более подробно остановимся на пункте 4. Рассмотрим пример решения практической задачи.
Далее перечислим некоторые типовые задачи теории графов и их приложения: - Задача о кратчайшей цепи замена оборудования составление расписания движения транспортных средств размещение пунктов скорой помощи размещение телефонных станций
- Задача о максимальном потоке анализ пропускной способности коммуникационной сети организация движения в динамической сети оптимальный подбор интенсивностей выполнения работ синтез двухполюсной сети с заданной структурной надежностью задача о распределении работ
- Задача об упаковках и покрытиях оптимизация структуры ПЗУ размещение диспетчерских пунктов городской транспортной сети
- Раскраска в графах распределение памяти в ЭВМ проектирование сетей телевизионного вещания
- Связность графов и сетей проектирование кратчайшей коммуникационной сети синтез структурно-надежной сети циркуляционной связи анализ надежности стохастических сетей связи
- Изоморфизм графов и сетей структурный синтез линейных избирательных цепей автоматизация контроля при проектировании БИС
- Автоморфизм графов конструктивное перечисление структурных изомеров для производных органических соединений синтез тестов цифровых устройств
Пояснительная записка должна быть оформлена согласно ГОСТ 7.32-2001 и содержать следующие обязательные структурные единицы: - титульный лист - реферат; - содержание; - введение; - основная часть; - заключение; - список использованных источников.
Образец титульного листа пояснительной записки приведен в приложении А. Красным цветом в шифре работы выделен порядковый номер студента в списке группы. Объем пояснительной записки 25-40 страниц машинописного текста без учета приложений.
Основная часть должна обязательно содержать следующие 4 раздела. 1. Постановка задачи курсового проектирования 2. Теоретический анализ 3. Схемы алгоритмов 4. Результаты тестирования 5. Решение практической задачи Основная литература для выполнения курсового проекта 1. Оре, О. Теория графов [Текст] / О. Оре; пер. с англ. И. Н. Врублевской; под ред. Н. Н. Воробьева. - М.: ЛИБРОКОМ, 2009. – 352 с.. 2. Кузнецов, О.П. Дискретная математика для инженера [Текст] / О.П. Кузнецов. – 4-е изд., стер. – СПб.: Лань, 2005. – 394 с. 3. Шапорев, С.Д. Дискретная математика [Текст]: курс лекций и практ. занятий: учеб. пособие для вузов по специальностям 220200 "Автоматизированные системы обработки информации и управления", 071900 "Информационные системы в технике и технологиях" / С.Д. Шапорев. - СПб.: БХВ-Петербург, 2009. - 396 с. (Гриф).. 4. Степанов, В.Н. Дискретная математика: графы и алгоритмы на графах [Текст]: учеб. пособие / В.Н. Степанов; ОмГТУ. – Омск: Изд-во ОмГТУ, 2010. – 118 с. 5. Иванов, Б. Н.. Дискретная математика. Алгоритмы и программы [Текст]: учеб. пособие / Б. Н. Иванов. - М.: Лаб. Базовых Знаний, 2010. - 288 с.
|
